Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
22
votes
5answers
24k views

Why maximum/minimum of linear programming occurs at a vertex?

I'm in high-school and I'm told that the maximum/minimum of a linear programming occurs at the vertex.For more info see the chapter here. For convinience I'm putting relevant excerpt here: Now, we ...
5
votes
1answer
4k views

Duality. Is this the correct Dual to this Primal L.P.?

Given a problem: Find the dual: $$ Primal =\begin{Bmatrix} max \ \ \ \ 5x_1 - 6x_2 \\ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ ...
6
votes
0answers
851 views

Maximum and minimum of an integral under integral constraints.

Find the maximum and minimum of the following integral in terms of $f(x),a,C$: \begin{align}I=\int_{0}^{a} \frac{x}{f(x)}p(x)dx \end{align} s.t.: 1) $\int_{0}^{a} p(x)dx=1$ 2) $\int_{0}^{a} f(x)p(x)...
10
votes
6answers
41k views

Converting absolute value program into linear program

I have the generic optimization problem: $$ \max c^T|x|$$ $$ \text{s.t. } Ax \le b $$ $x$ is unrestricted How do I convert it into a linear programming problem? Online I read something about ...
26
votes
8answers
20k views

Linear Programming Books

Do you know of a good book on linear programming? To be more specific, i am taking linear optimization class and my textbook sucks. Teacher is not too involved in this class so can't get too much help ...
3
votes
1answer
4k views

Prove optimal solution to dual is not unique if optimal solution to the primal is degenerate and unique.

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique? What I tried: Let the primal be $$\max z=cx$$ subject to $$Ax \le ...
4
votes
2answers
4k views

Simplex method : Duality by Bazaraa

I use great textbook (Linear Programming and Network Flows by Bazaraa II ed) On the page 240 the author states that for every primal problem, regardless of it's type (canonical or standard), dual ...
8
votes
3answers
11k views

Primal- degenerate optimal, Dual - unique optimal

Simple question- Is it possible for a linear programming optimization problem possible to have a degenerate optimal solution whereas the dual has a unique optimal solution? I can't find a scenario ...
4
votes
0answers
17k views

How to find all basic feasible solutions of a linear system?

I'm trying to solve this problem but need some help getting started. The problem asks to find all the basic feasible solutions of the following system: \begin{equation} -4x_2+x_3=6 \end{equation} \...
13
votes
3answers
1k views

Variable leaving basis in linear programming - when does it happen?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
6
votes
2answers
170 views

Transform an optimisation problem into a linearly-constrained quadratic program?

I would like your help with a minimisation problem. The minimisation problem would be a linearly-constrained quadratic program if a specific constraint was not included. I would like to know whether ...
1
vote
1answer
443 views

Travelling salesman problem as an integer linear program

So the travelling salesman problem is a problem wherein a salesman has to travel through all cities in a way that the total travelling distance is minimal. You can rewrite this as an integer linear ...
0
votes
1answer
2k views

Reduced cost vector in the phase I of the Two-phase simplex?

I am trying to understand the part in red. The left is the standard form problem and the right is the auxiliary problem. Now I can understand until the red i.e. $\bar c =(-1,-1,-3,-1,-2,0,0,0)$. The $...
5
votes
3answers
890 views

How to check whether a convex polyhedron is contained in another convex polyhedron?

Suppose we have two convex polyhedra $$P_1=\{x\in \mathbb{R}^n \mid A_1 x \geq b_1 \}$$ $$P_2=\{x\in \mathbb{R}^n \mid A_2 x \geq b_2 \}$$ Is there a way to check whether $P_1 \subseteq P_2$? I ...
1
vote
1answer
129 views

Consider the following LP. Apply surplus variables & initial tableau. Then use revised simplex method to obtain the tableau for basic variables

Consider this LP problem. \begin{array}{cccll} \min & Z= & 8x & +10y+25z & \\ \text{s.t.} & & 2x & \phantom{+10y}+ 2z & \ge 60 \\ ...
1
vote
1answer
2k views

travelling salesman understanding constraints

I am trying to program TSP problem in R. From wikipedia page section "Integer linear programming formulation", I was able to understand all the constraints except the last one. Need help to ...
1
vote
1answer
130 views

Verify my simple linear program formulation

Let $x_a$ denote amount of feed A and $x_b$ denote amount of feed B. Minimize $10x_a+12x_b$ subject to $4x_a+2x_b \ge 12$ $4x_a+8x_b \ge 24$ $8x_b \ge 8$ Have I got the numbers right? Also to ...
30
votes
1answer
146k views

Shadow prices in linear programming

I am quite confused about the meaning of shadow price from explanations on the internet. It can be understood as the value of a change in revenue if the constraint is relaxed, or how much you would ...
20
votes
4answers
20k views

How the dual LP solves the primal LP

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual." I know that both the primal LP and its dual must have the same optimal objective value (...
11
votes
2answers
18k views

Primal and dual solution to linear programming

Lets say we are given a primal linear programming problem: $\begin{array}{ccc} \text{minimize } & c^{T}x & &\\ \text{subject to: } & Ax & \ge & b \\ & x & \ge & ...
6
votes
2answers
3k views

Multiple solutions for both primal and dual

If matrix $A$ in an LP (or $A^T$ in its dual) has full row (column- in dual) rank, is it possible that both primal and dual have multiple solutions?
5
votes
3answers
10k views

How to find out whether linear programming problem is infeasible using simplex algorithm

So in http://econweb.ucsd.edu/~jsobel/172aw02/notes3.pdf, there is a mention about finding out whether linear programming (LP) problem is infeasible by simplex algorithm, but it does not actually go ...
2
votes
1answer
344 views

Is it possible to check polytope containment by only checking the feasibility of an LP?

This is NOT a question about whether or not we can use LP to check polytope containment, which is already answered by existing posts on this website. Suppose we have two convex polytopes in their H-...
2
votes
1answer
12k views

What to do about equality constraints in the Simplex Tableau method

The question I've got is: Maximise $$2x-y+3z$$ subject to $$2y+z \leq 2$$ $$x+y+z=4$$ $$x-2y+z \geq 3$$ $$x,y,z \geq 0$$ Using the Simplex Tableau method. I know that for $\leq$ constraints you need ...
1
vote
1answer
861 views

Linear Programming - Preventing Staff Scheduling Shift Overlap?

I am relatively new to linear programming, and I'm particularly interested in applying it to scheduling problems (transportation, staffing, etc). I've Googled for several hours looking at articles ...
1
vote
1answer
284 views

On a condition in real linear programming

For me $a,c\in[0,1]$ and $\epsilon>0$ is small (say $0.01$). Is it possible to set this condition $$c\leq\max\bigg(\frac{(a-\epsilon)}{(1-\epsilon)}, 0\bigg)$$ in real linear program? This does ...
9
votes
5answers
3k views

Finding nonnegative solutions to an underdetermined linear system

Here's the environment of my problem: I have a linear system of 4 equations in 8 unknowns (i.e. $Ax = b$, where $A$ is $4 \times 8$, $x$ is $8 \times 1$, and $b$ is $4 \times 1$, with $A$ given and $b$...
5
votes
1answer
1k views

Determining quickly whether this Integer Linear Program has any solution at all

I've got an integer linear program of the form $$ \begin{aligned} \text{Minimize}&& c &= x_1 + \cdots + x_m \\ \text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\ \text{where} &...
5
votes
1answer
376 views

weak duality theorem

Studying duality theory I have not found clear this point considering the primal a minimize problem, if $x$ and $p$ are feasible solution to the primal and to the dual then $p^tb \leq c^tx$ for ...
4
votes
5answers
2k views

Find a nonnegative basis of a matrix nullspace / kernel

I have a matrix $S$ and need to find a set of basis vectors $\{\mathbf{x_i}\}$ such that $S\mathbf{x_i}=0$ and $\mathbf{x_i} \ge \mathbf{0}$ (component-wise, i.e. $x_i^k \ge 0$). This problem comes ...
4
votes
1answer
163 views

Exercise 2.27 from Bazaraa (LP)

Consider the system $Ax=b$ where $A=[a_1,a_2,...,a_n]$ is an $m \times n$ matrix of rank $m$. Let $x$ be any solution of this system. Starting with $x$, construct a basic solution. There is a hint ...
3
votes
1answer
226 views

Bases are looping using simplex method

The question is: Maximize $x_1 − 2x_2 − 3x_3 − x_4$ subject to the constraints $x_j ≥ 0$ for all $j$ and \begin{align} x_1 − x_2 − 2x_3 − x_4 \le& 4 \\ 2x_1 + x_3 − 4x_4 \le& 2 \\ −2x_1 + ...
2
votes
1answer
50 views

Finding an optimal solution to a linear program among solutions of another

I had the following question on my last Algorithms test which I didn't know how to solve, and the the professor didn't agree to publish the solution. I would like to know the solution though, since it'...
2
votes
2answers
791 views

Solving a dual linear program using complementary slackness if primal constraints are tight

I have a doubt in the following question: Consider the linear program $\min\ \ 5x_1+12x_2 + 4x_3\ \ $, $\ \ $subject to $x_1+2x_2+x_3 = 10$ $2x_1-x_2+3x_3=8$ $x_1,x_2,x_3 \geq ...
2
votes
3answers
350 views

Linear Programming optimization with multiple optimal solutions

I am trying to solve the following optimization problem using linear programming (deterministic operations research). According to the book, there are multiple optimal solutions, I don't understand ...
1
vote
1answer
489 views

Why is it a requirement that we follow the central path in the interior point method?

I have been studying some of the interior point methods recently, and there is one in particular that I find most intuitive: The path-following method method. In this method, we put the inequality ...
1
vote
2answers
2k views

$\ell_0$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min:\|x\|_0$ subject to:$Ax=b$. $\|x\|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time has ...
0
votes
1answer
246 views

conditional constraint: if $x \in [a,b] => z=1$

I have an optimization problem in which a constraint should hold if the variable $x$ is inside the interval $[a,b]$. I assume you can model it by introducing a binary variable $z$ with $z=1$ if $x \in ...
0
votes
0answers
466 views

Linear programming - Maximizing negative objective function

How can I turn this into canonical form and then use the two-phase simplex method to solve it? Would I need to add slack variable AND surplus variables? $$\max\quad -2x_1-x_2-x_3 \\ \text{subject to: ...
3
votes
1answer
2k views

Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
2
votes
1answer
1k views

Why do we need to check both primal and dual feasibility in LP programs?

In in interior point method (and in fact in many practical optimization methods), a large part of the algorithm for finding the minimum is to follow a path called the central path while minimizing a ...
2
votes
1answer
312 views

How to use the simplex method for linear programs?

I believe to be missing something important in the Simplex algorithm, because I can't get it to work. From what I gather, there are three steps per iteration, given a matrix for a linear program in ...
2
votes
1answer
418 views

Characterize polytopes resulting from cutting a convex polytope by a hyperplane

We have a convex polytope $P$ for which we know its set of vertices. Using this set we characterize the H-representation of $P$ as: $\mathbf{A}\mathbf{x} < \mathbf{b}$. If a hyperplane defined by ...
1
vote
1answer
83 views

Rewrite the constraint $ p(x)=0 \Rightarrow q(x)=0 $ in an optimization problem

I am trying to reformulate an optimisation problem with unknown $x$ into a mixed-integer program. In this respect, I would like your help to rewrite the following constraint $$ p(x)=0 \Rightarrow q(x)=...
1
vote
1answer
119 views

Jordan Exchange/Pivot Operation formula for non pivot rows and columns?

I'm really confused with the Jordan Exchange (or pivot operation) for non pivot rows and columns. I apologize if this seems to be easily googled, but I've been struggling and I'm not sure what I'm ...
1
vote
0answers
3k views

Find all basic feasible solutions & find optimal solution for the given linear programming problem

Consider the problem: $$\text{min}\,x_{1}+2x_{2}+x_{3} \\ \text{subject to}\, \\ -x_{1}+x_{2}+x_{3} = 3 \\ 2x_{1} +x_{2} - x_{3} = 1, \\ x_{1},x_{2},x_{3} \geq 0 $$ I need to find all basic feasible ...
1
vote
1answer
2k views

Linear Programming 3 decision variables (past exam paper question)

This is an exam question I was practising. I have the general understanding of Linear programming, but how would you go about finding the Decision Variables, Objective function and Constraints for ...
1
vote
1answer
307 views

Confusion about definition of KKT conditions

In this link https://www.cs.cmu.edu/~ggordon/10725-F12/slides/16-kkt.pdf you can find this: And in the Nonlinear programming book by Bazaraa page 207 you can find this: My question is Are those ...
1
vote
0answers
213 views

Linear optimization problem. [closed]

Given a $m$ x $n$ matrix $A$, $m$-vectors $b$ and $y$, and $n$-vectors $c$ and $x$. Write the dual $LP$ problems $P$ and $P^d$ in the standard form. Whether $x$ (respectively, $y$) is a feasible ...
1
vote
1answer
110 views

If the solution set of linear programming problem is unbounded, can you find that out in finite steps?

Let $(P) \max\left\{c^T \cdot x \mid A \cdot x \leq b, x \geq 0\right\}$ be an arbitrary linear programming problem and $M$ its solution set. Is it possible to find out if $M$ is unbounded (in ...