Questions tagged [linear-programming]

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

228 questions
Filter by
Sorted by
Tagged with
23k 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 ...
3k views

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 ...
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} \...
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 ...
169 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 ...
419 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 ...
2k views

2k 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?
10k 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 ...
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 ...
11k 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 ...
800 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 ...
241 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 ...
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$...
1k views

232 views

406 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 ...
275 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 ...
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 ...
212 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 ...
91 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 ...
114 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 ...
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 ...
82 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)=...
261 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 ...