Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
263 views

Operations Research - Optimal Transport Routes

I have a problem in which there are 4 vessels available to transport people from 3 different bases back to a main base. Vessel 1 has a capacity of 50, can make 6 round trips and is allowed to visit ...
2
votes
2answers
2k views

Invertability of submatrix?

If I have a matrix $A \in R^{(m \times n)}$ with $m \leq n$. All rows in matrix a are linearly independent and therefore $A$ has a full row rank. I can decompose matrix $A$ such that $A = [B|N]$ with $...
2
votes
1answer
648 views

Find the minimum value of C subject to the given constraints.

C=2x+5y Constraints: x+y>=2 2x-3y<=-6 3x-2y>=6 A-42 B-4 C-49 D-10 I encountered this question while doing the Systems of Linear Equations and Inequalities test at http://www.classzone.com/books/...
2
votes
1answer
2k views

L1 minimization linear programming

So suppose we want to minimize the sum of the absolute errors $\sum\limits_{i=1}^m |b_i - \sum\limits_{j=1}^n a_{ij}x_j|$ with respect to $x_k$ where $k=1,...,n$ So to formulate this as a linear ...
2
votes
2answers
3k views

Optimality conditions and Directions in Simplex method

I am trying to understand the optimality conditions in Simplex -method, more in the chat here -- more precisely the terms such as "reduced cost" i.e. $\bar{c}_j=c_j-\bf{c}'_B \bf{B}^{-1} \bf{A}_j$ and ...
2
votes
2answers
51 views

If $P$ is an unbounded polyhedron, there exists a point $c \in P$ and a vector $d \neq 0 $ such that $ \forall \lambda \geq 0$, $c+ \lambda d \in P$

If $P$ is an unbounded polyhedron, there exists a point $c \in P$ and a vector $d \neq 0 $ such that $ \forall \lambda \geq 0$, $c+ \lambda d \in P$. Hi so I dont know if this is true or not, ...
2
votes
1answer
488 views

vertex cover , linear program extreme point

Consider the vertex cover problem. How can I prove that any extreme point of the linear program \begin{aligned} \min & & \sum_{i \in V} w_i x_i \\ \text{s.t.} & & x_i + x_j &\ge ...
2
votes
1answer
203 views

Dual of Unbounded Linear Program

For an LP of the form \begin{equation*} \begin{aligned} & \underset{\textbf{x}}{\text{minimize}} & & \textbf{c}^T \textbf{x} \\ & \text{subject to} & & \textbf{A} \textbf{x} \...
2
votes
1answer
190 views

Formulating an LP problem with vectors

We have $m$ vectors $v_1,v_2,\dots,v_m\in\mathbb{R}^n$ and $m$ numbers $t_1,t_2,\dots,t_m\in\mathbb{R}$ and we want to find a vector $y\in\mathbb{R}^n$ such that $$|v_i^Ty-t_i|\leq D$$ for $i=1,\...
2
votes
1answer
15k views

Degenerate solution in linear programming

How can I determine if a solution in a linear programming problem is degenerate without I use any software or the graphical display of the solution; For example in the model: $$\max\{2x_1 + 4x_2\}\\\...
2
votes
0answers
730 views

Comparing two probability distributions

In my research I have to find two discrete probability distributions by solving two separate linear programs. The domain of optimization is the probability space of $m^n$ atomic events, where $n$ is ...
2
votes
2answers
607 views

Write a linear optimization problem to find a hyperplane that strictly separates two disjoint polyhedra.

Let $P_{1}=\left\{x\:|\: Ax\leq b\right\}$ and $P_{2}=\left\{x\:|\: Cx\leq d\right\}$ be two disjoint polyhedra. Write a linear optimization problem to find a hyperplane that strictly separates $P_{1}$...
2
votes
1answer
3k views

Minimized sum of the distances with street distance

This exercise comes from Bazaraa Linear Programming and Network Flows book : Consider the problem of locating a new machine to an existing layout consisting of four machines. These machines are ...
1
vote
1answer
275 views

Minimize the maximum positive entry of $Ax-b$

As per title: I have a convex payoff (finance) to approximate with available instruments traded. I want to minimize $Ax-b$ s.t. $x>0$ and $Ax\ge b$ $A$ is a $n \times k$ matrix $b$ is a $n \...
1
vote
1answer
154 views

KKT conditions holds true under Cottles's constraint qualifications?

Exercise Solution: Could someone please explain why the reached contradiction solves the exercise? I can understand the solution but I don't know how does that implies that $\overline x$ is ...
1
vote
1answer
190 views

Find the nearest integer solution to a linear equation

I am interested in calculating the maximum number of strings of a fixed length that can be generated by a regular expression. If I have the regular expression ...
1
vote
1answer
39 views

State a system as a canonical minimum problem

Suppose we have a linear system $$Ax=b,\,\,x\ge0,$$ where $A$ is a $m\times n$ matrix and $b$ is a given $n\times 1$ column vector. Def: We say a problem is a canonical minimum problem if the problem ...
1
vote
2answers
4k views

How can the infinity norm minimization problem be rewritten as a linear program?

I have been trying to solve the infinity norm minimization problem and after quite a bit of reading I have found out that infinity norm minimization problem can be re-written as linear optimization ...
1
vote
1answer
164 views

Linear programming duality theorem

As far as I know, there are 2 versions of this theorem: 1) $\max \{xc^T: xA \le b, x \ge 0, x \in R^n\} = \min \{by^T: Ay^T \ge c^T, y \ge 0, y \in R^m\}$ 2) $\max \{xc^T: xA \ge b, x \in R^n\} = \...
1
vote
1answer
69 views

Simplex Methods and P problems

I know that there are cases in which the simplex methods, in linear programming, needs exponential time to calculate the solution. So why is simplex method considered a P problem ?
1
vote
1answer
425 views

Find set of extreme points and recession cone for a non-convex set

I have already shown the set $$\mathcal{B}=\{(x_{1},x_{2})\in \mathbb{R}^{2}: x_{2}\leq (x_{1})^{2}\}$$ to be non-convex, closed, and not bounded. Now, I need to find the set of extreme points of $\...
1
vote
0answers
957 views

Showing a dual LP solves a primal LP

I originally asked this question: How the dual LP solves the primal LP It was answered using an example of how the primal and dual solve each other (because of knowledge from strong duality). ...
1
vote
2answers
54 views

Corresponding LP problems to zero sum games

Given a zero sum game like this one : \begin{array}{c|rrrr} & A & B \\\hline X & 10 & 3 \\ Y & 5 & 9 \\ \end{array} how do you find an equivalent linear program ? I think ...
1
vote
0answers
69 views

A question about $n\times n$ matrix [duplicate]

Possible Duplicate: For every matrix $A\in M_{2}( \mathbb{C}) $ there's $X\in M_{2}( \mathbb{C})$ such that $X^2=A$? Square root of a matrix Let $A$ be $n\times n$ matrix on $\mathbb C $. ...
1
vote
1answer
628 views

Proving that Unit Intersection is NP-complete

I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem: Unit Intersection: Let X = {1, 2,...,n}. ...
1
vote
2answers
845 views

Sign restriction on the Lagrange multiplier? Why?

Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints ...
1
vote
1answer
52 views

How can we solve this simple linear program?

Let $$a:=\begin{pmatrix}.2&.1\\.7&.05\end{pmatrix}$$ and $$b:=\begin{pmatrix}.01&.9\\.4&.3\end{pmatrix}.$$ I want to maximize $$\sum_{ij}a_{ij}\min(x_i,b_{ij}y_j)$$ subject to $x_1,x_2,...
1
vote
1answer
136 views

Use duality to solve LPP

I have some confusion regarding the solution of LPP by solving its dual. I have drawn the following table to indicate possibility/possibilities. I have made an attempt to correlate the two columns but ...
1
vote
2answers
5k views

How do you find redundant constraints for a feasible region?

I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm only trying to find the non-redundant constraints that define a feasible region (i.e. I ...
1
vote
1answer
325 views

To show a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays.

I want to show that a closed convex set $S \subseteq R^n$ is bounded if and only if $S$ contains no rays. Where $r \in S$ is a ray of $S$ if $x \in S$ implies that $x+\mu r \in S$ for all $\mu \in R_{...
1
vote
1answer
61 views

Derivative of the solution of a linear program

Let $x^\star$ be a solution of the linear program \begin{align} \text{maximize} &\quad c \cdot x \\ \text{subject to} &\quad A \cdot x \leq b \end{align} How can one compute the derivatives of ...
1
vote
0answers
17 views

A “lifting property” for linear maps on cubes?

Let $L : \mathbb{R}^n \twoheadrightarrow \mathbb{R}^m$ be a linear map that is surjective. Let $[0,1]^n$ denote the unit cube in $\mathbb{R}^n$, and let $Z := L([0,1]^n) \hspace{5pt}$ ($Z$ is a ...
1
vote
1answer
46 views

Derivate the $3$ equations system from a linear model

I am asked to "derivate" (or find) the 3 equations system associated with the unique (and optimal) solution of a linear programming model. This is the model: $\min z = -5a - 3b - 4c$ Subject to $...
1
vote
1answer
74 views

Disprove that the given strategy pair is a solution to the game.

Problem: For the following matrix game, prove or disprove that the given strategy pair is a solution to the game. \begin{align} A &= \begin{bmatrix} -1 & 2 & -3 \\ 3 & -4 & 2 \\ ...
1
vote
3answers
1k views

Conditional Constraints in Linear Programming

My variables are [$x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8$]. All are continuous variables within the range of $[0,1]$. I want to impose a conditional constraint which is as follows: if $x_6 \gt 0$ then ...
1
vote
2answers
325 views

Checking the existence of a solution for a set of linear equality and ineaulity equations

I would like to know if there is a method to check the existence of the solution for a given set of linear equations composed with both equalities and inequalities? I'm not interested in the solution, ...
1
vote
1answer
172 views

Reformulation in linear programming with $\max_i \ a_i^Tx + b_i$

I was reading about the following trick in convex analysis. Consider the (not obvious) LP $$p = \max_i \ a_i^Tx + b_i$$ but apparently it can be equivalently reformulated as an LP: $$ \min_{x,t} \ ...
1
vote
1answer
337 views

Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 &+6x_2&+5x_3&-2x_4&+...
1
vote
2answers
224 views

Linear dependence in Carathéodory's theorem (convex hull)

I don't get this step in proof of Carathéodory's theorem (convex hull) Why: Suppose k > d + 1 (otherwise, there is nothing to prove). Then, the points $x_2 − x_1, ..., x_k − x_1$ are linearly ...
1
vote
1answer
173 views

Linear Optimization/Linear Programming - Vending Machine Problem

I have a question about the formulation of a LP involving fulfilling orders of a vending machine. We have a vending machine which dispenses medicine to its patients. We assume that we have a list of ...
1
vote
2answers
1k views

Minimization of log-sum-exponential function subject to constraints.

I would like to minimize the following function: $f(x)=log(e^{-x_1}+..+e^{-x_n})$ Subject to: $\sum_{i=1}^{n}{x_i}=1$ $0 \leq x_i \leq 1$ So far I have discovered the following: If all the $x_i$'...
1
vote
1answer
70 views

Real linear combinations of intervals

Given intervals at $i\in\{0,1\}$ $I_i=[-a_i,a_i]$ where $0<a_0<a_1<1$ and a third interval $I=[-a,a]$ where $0<a<{1}$, when is there an $\alpha,\beta\in\Bbb R$ such that $\alpha I_0 +\...
1
vote
1answer
5k views

linear programming set a variable the max between two another variables

i'm having problems with this. Suppose i have two real variables, A and B, and another one C. I want to store the max between A and B in C for a problem im modeling. I can't use a max function, ...
1
vote
1answer
649 views

Questions about weak duality theorem

Following are some corollaries regarding the weak duality theorem. Consider a constrained problem, $\min_{x \in X} f(x),$ subject to $g(x) \leq 0$ and $h(x) =0$. Its dual problem is $\sup_{u \geq 0, ...
1
vote
0answers
1k views

Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
1
vote
1answer
499 views

Meaning of the bar over $\bf{c}'$ in $\bf{\bar{c}}'=\bf c' -\bf c'_B \bf B^{-1} \bf A\geq \bf 0$?

I am trying to understand the page 87 Bertimas about Linear Programming. The author uses bolding and bars -- now I am starting to think that the bar means something else to vector, bolding apparently ...
0
votes
1answer
163 views

Selection of Pivotal Elements in SIMPLEX method

I want to solve the following LP problem by using the simplex method $Maximize$ $ p = x + y +3z $ subject to $$x + y +z \leq 15$$ $$x + 3y +2z \leq 45$$ $$2x- y -z \leq 15$$ $$2x + y +z = 12$$ $$4x ...
0
votes
1answer
97 views

Trying to set up a linear programming problem

Attempt Let $x_1$ be the number of hours to produce product 1 during assembly and $x_2$ be the number of hours to produce product 1 during finishing. Notice that $\frac{1}{2} x_1 + x_2 $ is the ...
0
votes
2answers
119 views

Find an optimal solution to a linear program in $O ( n \log n )$

Problem: Given $c \in \mathbb { R } _ { + } ^ { n } , a \in \mathbb { R } _ { + } ^ { n }$ and $\gamma \in \mathbb { R } _ { + } ,$ design an algorithm which, in $O ( n \log n )$ operations, computes ...
0
votes
2answers
43 views

After Farkas Lemma, transforming $(A, -A)x = b$ into $Ax=b$

Let $A \in \mathbb R^{m\times n}$ and $c \in \mathbb R^{m}$ Show that either (i) $Ax=c$ has a solution or (ii) $c^{T}y=1$ with $A^{T}y = 0$ has a solution. My proof: Let (ii) be satisfied iff ...