# Questions tagged [linear-programming]

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

3,588 questions
Filter by
Sorted by
Tagged with
149 views

### Feasibility checking

I have a question regarding feasibility checking. I need to check whether the system $\{ x: Ax=b , x \geq 0 \}$ has a feasible solution. What is the best worst case running time for this decision ...
4k views

### Percentages - Find Maximum value.

3 candidates A,B and C contest an election. A gets at least 40% of all the votes. B gets at least 20% of the number of votes that A gets and cannot get more than 80% of number of votes that c gets. ...
797 views

### LP unboundedness

Does there exist a way to check if a linear programming problem is unbounded without solving it directly? In other words, How the unboundedness of an LP can be realized from its structure. Assume the ...
6k views

### Strict inequalities in LP

How should we deal with strict inequalities in a linear programming problem? For example: inequalities such as $ax< b$;
835 views

### Solving geometric problems using Linear Programming

Is it possible to find an LP formulation to test whether $n$ points in the plane are in convex position?
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 ...
216 views

### Simplex method with zero value constraints

The usual problem is to maximize some linear function $f(x_0, x_1 ... x_n)$ subject to linear constraints $g_i(x_0, x_1 ... x_n) \leq b_i$. My question is: What happens when all (or most) of the $b_i$...
870 views

### Book recommendation on Applied Integer Programming/Combinatorial Optimization/OR

Having some very basic and theoretical knowledge about these topics from my study, I'm looking for a book (or other good sources) that explains the stuff from a practical point of view. On the one ...
290 views

### Totally Uni-modular Matrices

A matrix is totally uni-modular if the determinant of any (square) sub-matrix is {+1, 0, -1}. My question is, "Is there a way to transform(linear or non) a general matrix into a totally uni-modular ...
6k views

### Simplex: outgoing variable cannot re-enter the basis next iteration

How can I prove that in the simplex method, a variable that has just left the basis cannot re-enter the basis on the very next iteration? The pivoting rule is Dantzig's.
643 views

391 views

### Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $$F(x) = \sum_{i=1}^{M}\left\|x_{i+1} - x_i - K\left(\frac{x_{i+1} + x_i}{2}\right)\right\|^2 + \|x_1-c_1\|^2 + \|x_N-c_2\|^2,$$ where $x$ is a vector of $N$ scalars, ...
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 ...
77 views

### primal simplex procedure

Minimize $-2x_1-x_2+2x_3$ subject to $x_1 +x_3 = 4$, $-2x_1 +x_2 = 8$ s.t. $x_1,x_2,x_3\geq 0$. In my book, the augmented matrix is defined as $[A : 0 : b; -c^T : 1 :0]$ (where : separates columns ...
84 views

### Chaotic solutions to mixed integer linear problems

Is there a way to get the branch and bound algorithm to converge to a solution "close" to an initial value? One way I can think of, is to adding a "distance from initial value" term to the cost ...
49 views

### How do I solve a LP problem when constrains have different inequalties?

How can I solve this LP problem: Maximize p=x subject to : x+y <=30 x-2y <= 0 2x+y >=30 x>=0 , y>=0 using simplex method?
915 views

### Convex hull of sets defined by (in)equalities

If you define the convex hull of a set $X$ as the set of all convex combinations of elements of $X$, it becomes difficult to decide if a given element $w$ belongs or not to $conv(X)$ (You have to ...
1k views

my question is about gradient algorithms. Lets have function f like: $f(x) = \|Ax-b\|^2$ and i want to find its minimum (according to x). So i can use some gradient method, for instance gradient ...
57 views

### Assume $x\in \operatorname{cone}\{a_1, a_2,\ldots, a_m\}$. Is there a systematic way to find out the coefficients of $x$ with respect to $a_i$'s?

Assume $x\in \operatorname{cone}\{a_1, a_2,\ldots, a_m\}$. Is there a systematic way to find out the coefficients of $x$ with respect to $a_i$'s? When $a_i$'s are independent, it should easy. What ...
557 views

### Techniques for (upper-)bounding LP maximization

I have a huge maximization linear program (variables grow as a factorial of a parameter). I would like to bound the objective function from above. I know that looking at the dual bounds the objective ...
272 views

I am trying to load a CPLEX LP file in to CPLEX using the "read" command. I believe that in this problem, I have a set of constraints that are quadratic. But, from what I understand CPLEX will still ...
924 views

235 views

### Efficiently solving a special integer linear programming with simple structure and known feasible solution

Consider an ILP of the following form: Minimize $\sum_{k=1}^N s_i$ where $\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of non-...
444 views

### Need help with a Linear Programming homework.

Please help with the problem: A polyhedron P in $R^n$ is given by the system of m linear inequalities (of n variables). Furthermore, let P have k vertices (that is, k vectors satisfying all m ...
171 views

### Casting a linear (in)equality into a linear program problem

Suppose I have the systems $$S_1: Ax \leq b$$ where $A \in \mathbb{R}^{n\times m}$, $x \in \mathbb{R}^m$ and $b \in \mathbb{R}^n$, and $$S_2 : y^{\intercal}A=0,\\ y \geq 0,\\ y^{\intercal}b < 0$$ ...
172 views

### Linear optimization, homework problem. [duplicate]

Please help with the following problem: Given a $m \times 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. ...
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 ...