# Questions tagged [linear-programming]

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

4,479 questions
Filter by
Sorted by
Tagged with
2k views

### Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
162k 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 ...
26k 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 ...
34k views

### Why does the 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 ...
60k 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 ...
22k 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 (...
19k views

### What are the advantages of studying the dual problem in linear programming?

I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
13k views

### Good software for linear/integer programming

I never did any linear/integer programming so I am wondering the following two things What are some efficient free linear programming solvers? What are some efficient commercial linear programming ...
31k views

### Optimum solution to a Linear programming problem

If we have a feasible space for a given LPP (linear programming problem), how is it that its optimum solution lies on one of the corner points of the graphical solution? (I am here concerned only with ...
234 views

### How low can the approval rating of a majority candidate be?

“Ostrogorski's paradox” describes a strange situation in which voters decide on candidates based on issues in platforms, but on each issue of the platform, the majority of voters disapprove of the ...
2k views

### What is linear programming?

I asked this question on Stack Overflow but it was closed as "not programming related". So I think this is probably the best place for it... I read over the wikipedia article, but it seems to be ...
15k views

### How can not-equals be expressed as an inequality for a linear programming model

I have this linear programming model I'm building but one of the constraints needs to specify that the solution's basic variables need to all be different from one another. This is an integer linear ...
3k 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 ...
574 views

### Fitting a parabola to separate two classes of points in the plane

Suppose we have a set of points $(x,y)$ in the plane where each point is either boy or a girl. Does there exists a randomized linear-time algorithm to determine if we can fit a parabola (given by a ...
417 views

### Polygons with 2 diagonals of fixed length (part two)

In this question of mine Polygons with two diagonals of fixed length I've presented the following particular polygon $P$ and I've asked the following question: is it possible to shorten one or ...
19k views

960 views

### Maximize the trace of a matrix by permuting its rows

I have been struggling with a combinatorial problem that eventually translates to the following: Given an $n \times n$ nonnegative matrix, find a permutation of the rows that maximizes the trace. ...
6k views

### What is the computational complexity of linear programming?

What is the computational complexity of solving a linear program with $m$ constraints in $n$ variables?
3k views

### Linear programming with one quadratic equality constraint

I have a problem that can be formulated as a linear program with one quadratic equality constraint: where variable $x$ is an $n$-dimensional vector and $H$ is a positive semidefinite $n \times n$ ...
7k views

### Strict inequalities in LP

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

### Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$\left \{ x | Ax = b, x \geq 0 \right \}$$ (a) Suppose that two different bases lead to ...
714 views

### Is there a connection between duality in linear programming and duality in functional analysis?

In linear programming we optimize a linear function which is constrained by linear inequalities or linear equalities. Under some conditions you can rewrite the problem to the dual problem, so that you ...
3k views

### Farkas Lemma proof

I am trying to prove the Farkas Lemma using the Fourier-Motzkin elimination algorithm. From Wikipedia: Let A be an $m \times n$ matrix and $b$ an $m$-dimensional vector. Then, exactly one of the ...
3k views

### Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
1k views

### Blotto game variation

My smart friend ZWX challenged me to solve the "brainteaser" below, but to my surprise, the problem seems highly nontrivial as I took a closer look. Anyway, the question goes: In a game, both you ...
18k views

### How Can ${L}_{1}$ Norm Minimization with Linear Equality Constraints (Basis Pursuit / Sparse Representation) Be Formulated as Linear Programming?

Problem Statement Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form ...
4k 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$...
21k views

### Simplex algorithm — primal or dual?

As far as I know there are two simplex algorithms – primal and dual. They have different halting criteria etc. Before using simplex I have to make a standardization of the LP. So, when do I use primal,...
10k views

### Linear programming: Maximize minimum of linear functions

For a project I need something solved, it screams linear programming. If I get the problem in "standard" form I should be able to solve it using the simplex method. But I don't see how to get it in ...
37k views

### What is the standard form of a linear programming (LP) problem?

According to Bertsimas' text, the standard form of a LP problem is: According to Vanderbei's text, the standard form of a LP problem is: So, what is the standard form of a linear programming (LP) ...
14k 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 ...
12k views

### How to covert min min problem to linear programming problem?

I have the following problem: set $P=\{1,2,3...,n\}$ for index $i$, set $K=\{1,2,3,...,m\}$ for index $k$. Value $B_i^k$ is indexed by both $i$ and $k$, while value $l_i$ is indexed by only $i$. Here ...
4k views

### How to formulate Unique value constraint in Integer Programming?

Given the following integer programming formulation, how can I specify that the variables are unique and none of them has the same value as the other one. basically ...
6k views

6k views

### Find a matrix with given row and column sums

Please forgive my intrusion. I've been working for days on this problem and it's vexing me. It doesn't seem to have a solution and I could really use some help. I have a "math square" (not a magic ...
33k views

### Basic and non basic variables in linear programming

I dont understand what are Basic and non basic variables,why we are talking them specially, what they have got to do with the rank of the coefficient matrix and augmented matrix ,and some deal with ...
11k views

### Construct a linear programming problem for which both the primal and the dual problem has no feasible solution

Construct (that is, find its coefficients) a linear programming problem with at most two variables and two restrictions, for which both the primal and the dual problem has no feasible solution. For a ...
620 views

### What is the use/significance of Farkas' lemma?

I worked on an exercise to prove Farkas' lemma, which states that for $A \in \mathbb{R}^{m,n}$ and $b \in \mathbb{R}^n$ exactly one of the following is true: There exists $x \ge 0$ such that $Ax=b$. ...
7k views

13k 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 ...
7k views

3k 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 ...
Your friend will pick a $4$-letter word and you will make guesses in order to find it. -A word can contain only the letters $A, B, C,\:\text {and} \:D$, and they can be used more than once. \$(AAAA-...