# Questions tagged [linear-programming]

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

235 questions
Filter by
Sorted by
Tagged with
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 ...
4k 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 ...
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 ...
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 ...
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 ...
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 ...
2k views

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?
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 ...
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-...
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 ...
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 ...
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 ...
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

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 ...
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 ...
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 ...
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 ...
83 views

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 ...
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 ...
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 ...
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 ...