Questions on linear programming, the optimization of a linear function subject to linear constraints.

learn more… | top users | synonyms

1
vote
2answers
29 views

Formulating an optimisation problem into a mixed-integer problem

I'm not sure if I understand this question and was wondering if anyone could provide any insight to an answer. The only thing I can think of adding is a constraint: "x2 = integer", so I'm clearly ...
0
votes
0answers
23 views

How to linearize a double sum of product of binary variables?

I have a double summation of the form $$ x_{kn}\sum_{k'\in K}\sum_{n'\in N} x_{k'n'} A_{k'n}\leq B_{kn},\quad\forall\; k\in K,n\in N $$ where $x_{kn}$ is a binary variable. How to linearize this ...
0
votes
1answer
26 views

When modeling a multi-objective problem, is there a simple way of choosing to fully minimize one function, then to go on and minimize the second?

I am modelling a problem where I have two objectives. My goal is to fully minimize the first objective function, then choose among the solutions that fully minimized the first objective function to ...
0
votes
0answers
12 views

Ray between vertex and point inside a polytope

Let $P$ be a polytope, let $v \in P$ be a vertex of $P$, and let $x \in P$ such that $x$ is not a vertex. Consider the ray $$\forall t>0, \phi(t)=v+t(x-v).$$ Let $t_0$ be the maximal $t$ such that ...
1
vote
1answer
44 views

Show that exactly one of the following two systems has a solution.

Let A be a $m \times n$ matrix, $\mathbf{c}$ an $n$-dimensional ector and $\mathbf{b} \ge \mathbf{0}$ an $m$-dimensional vector. Show that exactly one of the following two systems has a solution: $\...
0
votes
0answers
16 views

Maximizing the total viewership of the posters using Dynamic Programming

You must advertise your sorority’s big party along an M foot-long corridor. There are bulletin boards at positions x1,x2, . . . ,xn along this corridor (in sorted order from north ...
0
votes
0answers
12 views

Reduced cost in linear programming maximization sensitivity analysis?

My sensitivity report of maximization problem shows negative reduced cost although my optimal values of variables are not zero. So, what does it mean by the negative values of reduced cost? Here is ...
0
votes
1answer
20 views

LP problem: Giving variables the same value or 0

If I have the following objective function: $$\min X_1 + X_2 + X_3 + X_4$$ How could I ensure that the variables $X_1, X_2, X_3$ and $X_4$ either have the value of 0 or they could have a random ...
1
vote
1answer
26 views

How to minimize a linear function over a halfspace efficiently and intuitively

Consider the following fundamental problem: Two methods: By duality: ($\lambda, b \in R$) $L(x,\lambda)=c^Tx+\lambda(a^Tx-b)=x^T(c+\lambda a)-\lambda b \ \ $. Therefore, $g(\lambda)=-\...
1
vote
1answer
37 views

Conditions for uniqueness of solution to a linear system of equation

Consider a $n\times n$ M-Matrix $\mathbf{A}$ and a $n\times n$ non-negative and non-zero matrix $\mathbf{B}$. Also, let $\mathbf{x}$ and $\mathbf{b}$ be two (non-zero) n-column vectors. I am looking ...
2
votes
1answer
64 views

Minimize absolute difference of two integers

I have 4 known positive variables - $p$, $q$, $r$ and $s$ and two unknown positive variables $x$ and $y$. How can I choose $x$ and $y$ such that absolute difference of $(p+x \cdot r)$ and $(q+y \cdot ...
3
votes
0answers
63 views

Convexity in oriented matroid theory: proof on closure operator?

I would like to try to solve the following problems. Problem from the Oriented Matroids book by Bjorner, Las Vergnas, Sturmfels, White, and Ziegler. It is problem 3.9 on page 152. Attempt ...
4
votes
0answers
67 views

I'm walking towards my car - when should I try the remote, in an optimal sense?

I'm interested to learn about how discrete/'event' based elements are incorporated into optimisation problems. Hopefully this is an interesting problem in its own regard, it's inspired by a daily ...
0
votes
0answers
35 views

Solution of diophantine equation with lowest c

Lets say I have a diophantine equation , aX - bY = c Now, for some (a,b,c) I may not have any integer solution at all. But lets say , I write the equation in this way , aX - bY = c + p p is an ...
1
vote
1answer
60 views

On the injection of exactly two artificial variables into the Phase I of a two-phase simplex

I am relatively new still to linear optimization and as I understand it, the two phase method is a common practice for finding the bfs before using the simplex or a simplex like solver (a solver ...
0
votes
1answer
24 views

GLPK/Linear Programming - if conditions

Imagine that I have two variables fw (>= 0) and a (binary) and my objective function is to minimize: fw. In the constraints part, I want to ensure (among other ...
0
votes
1answer
40 views

Minimize linear function with $\ell_1$ norm regularization and positive semidefinite constraint

I am running into the problem like this: $\underset{\mathbf{X}\succ0}{\text{minimize }} vec(\mathbf{A})^{\top}vec(\mathbf{X}) + \lambda ||\mathbf{X}||_1$ I am think about maybe one can minimize a ...
1
vote
3answers
45 views

Easier way of finding out whether a given linear programming problem has optimal solution or not

I have the linear program $$\begin{array}{ll} \text{minimize} & -2x-5y\\ \text{subject to} & 3x + 4y \geq 5\\ & x, y \geq 0\end{array}$$ I can solve it using Simplex algorithm, but I ...
0
votes
0answers
14 views

Solving Binary Linear Programming Problem Using KKT

Execuse me, I know that if I searched a lot I could find the answer, However I have already did my research and I am running out of time. I need the detailed solution of the following linear problem (...
1
vote
0answers
5 views

Complementary Facets of Pointed Cone

I am looking at a particular full-dimensional pointed cone $C \subset R^{11}$ with $14$ generators. In matrix form, with each column being a generator, I have the matrix \begin{pmatrix} 1 & 1 &...
1
vote
1answer
31 views

Dual form of $L_1$ norm approximation as a linear programming problem

According to my text: Given an overdetermined system, the residual vector is: $$\textbf{r} = \textbf{Ca} - \textbf{f}$$ The $L_1$ norm approximation seeks to minimize the residual r: $$\text{...
1
vote
0answers
22 views

How can I show the corresponding dual solution is unique when the given primal solution is nondegenerate, basic feasible?

the given problem is to show that if $x_1,...,x_n$ is a nondegenerate basic feasible solution of the primal LP max $\sum_{j=1}^{n}c_jx_j$ s.t. $\sum_{j=1}^na_{ij}x_j\leq b_i, \forall i\in\{1,...,...
0
votes
0answers
43 views

Linear system equations

I need to get, preferably by a numerical method, a solutions of: $$\left\{\begin{array}{lll} 2\sum_{i=1}^n b_{ik}x_i+x_{n+1}=0&\text{for}& k=1,2\ldots,n\\ \sum_{i=1}^n x_i=0 \end{array}\right.$...
3
votes
3answers
46 views

Maximize system of linear equations

Suppose you have the system $$ \begin{bmatrix} 4 & 3\\ 1 & 7\\ 5 & 9\\ 2 & 4\\ \end{bmatrix} \begin{bmatrix} x\\y\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\b_3\\b_4\end{bmatrix} $$ How ...
1
vote
2answers
40 views

Trying to sell the most batches of animals using linear programming

I'm trying to sell the most batches of animals... Let's say I have 200 dogs, 100 cats, and 100 ferrets. ...
0
votes
0answers
19 views

AMPL - Step by Step mode

Is there a way to solve a problem using AMPL in a step by step(or a verbose, or a debug) mode? Preferably showing all basis exchanges? The manuals of AMPL make reference to script development, but i ...
2
votes
2answers
152 views

Why can/should we use 5 instead of 10?

Problem: A pharmacy has a uniform annual demand for 200 bottles of a certain antibiotic. It costs \$10 per year for a storage place for one bottle, and $40 to place an order. How many times during ...
1
vote
0answers
23 views

Enlarging a rectangle around its origin, to fit a containing rectangle, but the rectangle must be moved

EDIT: The math was easy/as expected. The bug was in a programming error related to HTML/CSS. Sorry everyone, thank you. I am coding a mobile UI where there is a view of a small card. When clicked, ...
5
votes
2answers
227 views

Convert a piecewise linear non-convex function into a linear optimisation problem.

Update: Problem and solution found here (p. 17, 61), although my prof's solution (formulation) is different. Convert $$\min z = f(x)$$ where $$f(x) = \left\{\begin{matrix} 1-x, &...
3
votes
0answers
32 views

How to reduce the number of (overlapping) constraints in a linear program?

I am trying to solve a linear program with more than 7 million constraints which could not be solved on my computer (In total around 5000 variables). In the constraints there is a overlap between them....
1
vote
1answer
39 views

How to convert a non-linear constraint to a linear constraint for integer programming?

I have non-linear scheduling model and I want to convert it to a linear model. But I have no idea about how can I do it. The nonlinear constraint is: For each $i, i'\in I$ and $j, j' \in J$ and $q, ...
0
votes
1answer
28 views

ILP Problem to minimize two functions one after the other

I am working with a ILP problem. In the problem I would like to minimize f(x0+..+xn) and then if multiple optimal solutions exist, minimize ...
1
vote
1answer
15 views

Linear programming.

In the given diagram the co-ordinates of B and C are $(-2,-1)$ and $(-2,8)$ respectively. The shaded region inside the $\triangle ABC$ represented by three inequalities. One of these is $x + y <=6$....
0
votes
1answer
49 views

How to linearize the following constraint on abs terms with coefficients of mixed signs

I am implementing an optimization program on 2 variables with a constraint of the form: 2*|x1| + 3*|x2| <= 2.25 * (|x1| + |x2|) Given that the effective coefficients on the two abs terms are + ...
0
votes
0answers
12 views

incremental knapsack

Is there a way to compute the knapsack problem incrementally? Any approximation algorithm? I am trying to solve the problem in the following scenario. Let D be my data set which is not ordered and ...
-1
votes
1answer
39 views

Knapsack problem

Knapsack problem we can solve several methods: dynamic programming branch and bound greedy method genetic algorithm Brute force Heuristic by the value / size Which of these methods gives ...
1
vote
1answer
37 views

Linear Programming, with slack variables [closed]

I'm trying to prove the following statement Show that the set ${\{(x,w) \in \mathbb R^n\times \mathbb R^m \mid Ax \leq0, c^T x >0,w^TA=c, w\geq0 \}}$ is empty, where $A\in \mathbb R^{m\times n}$...
4
votes
2answers
37 views
2
votes
1answer
28 views

Existence of direction for polyhedral set

I refer to Lemma 4.42 of this lecture notes on linear programming, about the relationship between the boundedness of a polyhedral set and its directions. Let $P$ be a non-empty polyhedral set. ...
1
vote
1answer
295 views

Representation of a point in terms of extreme points and extreme directions in a LP feasible region

We know that every point in a feasible region $(X)$ of a Linear Program can be represented as a convex combination of the extreme points of $X$ plus a non-negative combination of the extreme ...
0
votes
0answers
35 views

Linear Programming - Complementary Slackness

I just can't understand the question below: This question is presented in Exercise 5.2 from Jon Lee, "A First Course in Linear Optimization", Second Edition (Version 2.1), Reex Press, 2013/4/5. ...
0
votes
0answers
14 views

Linear Programming - Constraints

I am trying to encode this (a small part of a project that I am trying to do by self-learning) to linear programming: For each package p we know its length (xDimp) and width (yDimp). Also, we have ...
3
votes
2answers
278 views

Prove $\exists\bar{b}$ s.t. every solution in polyhedron $P = \{x | Ax \ge \bar{b}\}$ is nondegenerate

I'm doing an exercise in the book "Introduction to Linear Optimization" and be stuck in this problem. Can anyone here help me solve this. I really appreciate all your help. Consider a ...
2
votes
3answers
26 views

How to draw the graph of the optimised function in linear programming

Ok, I don't know if I am just over thinking this, but I have been tearing my hair out trying to think about this. I have looked at plenty of linear programming examples and solutions online and I can'...
0
votes
0answers
13 views

Existence of solutions for a scaled integer linear inequality

Assume that I know there exist non-negative integer solutions to a linear system of integer equations (with coefficients from $\{-1,0,1\}$ and non-negative constant terms in my case). Is there any ...
0
votes
0answers
18 views

Optimize matrix multiplication when one matrix is the same.

I have a situation where I will be multiplying $AB\vec{x}$ together frequently. $A$ is a 4x4 matrix that won't change from problem to problem. $B$ is a 4x4 matrix that will change occasionally, and $\...
2
votes
2answers
346 views

Simplex method - multiple optimal solutions?

I have to solve this optimization problem: $$\begin{array}{ll}\text{minimize} & z= x_1 - x_2 + 3x_3\\\\ \text{subject to} &x_1-x_2+x_3-x_4=2\\ & 2x_1-2x_2-x_3+x_5=0\\ & x_1, x_2, x_3, ...
0
votes
1answer
19 views

Linear equation system to standard form

So I have this linear equation system: $inf \{3x_1 - x_2 - 2x_3 + x_4\}$ $x_1 + 4x_2 - x_3 - 3x_4 ≤ 3$ $-2x_1 + x_2 + 2x_3 - x_4 ≥ -1$ $5x_1 - 3x_2 + x_3 + 2x_4 ≤ 4$ $x_1 ≥ 0, x_2 ∈ R, x_3 ≤ 0, x_4 ...
3
votes
1answer
31 views

Transforming a $0$-$1$ knapsack problem into the standard form

I have the following $0$-$1$knapsack problem: $$\begin{align*} &\mathrm{Max} : \quad z= 3x_1 -4x_2+5x_3+7x_4-6x_5+x_6\\ & \mathrm{subject\ to}: -2x_1 +x_2 +10x_3 +3x_4 -5x_5+12x_6 \leq 4 \...
1
vote
0answers
40 views

Transform an assignment problem to use the Hungarian algorithm

I have this assignement problem: There are three machines to perform four tasks. The costs of assigning to a machine each of the tasks are given by the following matrix: $$\begin{pmatrix} ...