# Questions tagged [linear-programming]

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

3,561 questions
Filter by
Sorted by
Tagged with
1k 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 ...
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 ...
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 ...
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 ...
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 (...
206 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 ...
10k 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 ...
28k 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 ...
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 ...
514 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 ...
394 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 ...
14k views

### What are the advantages of dual of a problem

I am studying linear programming and I came across primal-dual algorithm in Linear Programming. I understood it but I am unable ...
1k 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 ...
18k views

18k 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 standarization of the LP. So when do I use primal,...
13k 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 ...
28k 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) ...
274 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$. ...
Update: Problem and solution found here (p. 17, 61), although my prof's solution (formulation) is different. Convert $$\min z = f(x)$$ where $$f(x) = \left\{\begin{matrix} 1-x, & ... 2answers 119 views ### Rotating Kindergartners at Tables Monthly My wife teaches AM and PM kindergarten classes. AM has 14 students and PM 11. At the beginning of each month, she puts out a new seating chart where she rotates students in such a way that they (... 1answer 991 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 ... 1answer 8k 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 ... 3answers 3k 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 ... 2answers 945 views ### Linear programming for combinatorics/graph theory I just went to a graph theory talk talking about various fractional graph parameters (but focusing on one). These were defined using linear programming. A question was asked, "How can we learn more ... 4answers 10k 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 ... 2answers 2k views ### Linear programming algorithm that minimizes number of non-zero variables? I have real world problems I'm trying to programmatically solve in the form of$$Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_nSubject to \begin{align} & a_{11} x_1 + a_{21} x_2 + \cdots + a_{n1} =... 1answer 297 views ### What is the minimum number of guesses in order to guarantee to win the prize? 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-... 1answer 243 views ### Bounding the number of nonzero coefficients in a conic combination I'm looking for a proof for the following statement in order to understand a proof about integer programming I'm reading. Given vectors x_1, \ldots, x_s \in \mathbb R^n, nonnegative coefficients \... 2answers 1k views ### Finding the payoff matrix of a game A two player zero-sum game can be represented by a m\times n payoff matrix M having m rows and n columns with values in [0,1]. The value M(x,y) represent the payoff given to player 1 [... 2answers 8k views ### Linearization of a product of two decision variables I am trying to solve a problem that involves constraints in which products of two decision variables appear. So far, I read that such products can be reformulated to a difference of two quadratic ... 2answers 7k 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 ... 2answers 5k views ### Berlin Airlift Linear Optimization Problem I am trying to learn more about the Berlin Airlift transport problem. Two links I could find are here: http://drmohdzamani.com/notes/file/Simplex%20Method.pdf http://www.cabrillo.edu/~mladdon/math13/... 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? 2answers 8k views ### Solving Ax=b under L_1 |Ax-b| minimization I would like to solve a linear system Ax = b under the L_1 norm constraint \min(|Ax-b|). All that I can find about L_1 minimization is a way to minimize |x|_1 subject to Ax=b. I wanted to ... 1answer 88 views ### What is the advantage of adding \log Barrier to solve a Linear program? Let A \in \mathbb{R}^{n \times m}, b \in \mathbb{R}^{n}, and x \in \mathbb{R}^{m}. Let Ax \leq b be the set of linear inequalities which can be written as a_i^Tx-b_i \leq 0 \,\,\,\,\forall i=... 2answers 201 views ### Why is BB^T always invertible? In Karmarkar’s method, we use[I - B^T(BB^T)^{-1}B]v$$Why does BB^T always have an inverse? Karmarkar’s method is applied to an LP in the following form: \min z = cx subject to AX=0 x_1 ... 1answer 8k 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 ... 2answers 25k 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 ... 2answers 5k views ### why in Phase I of the simplex method, if artificial variable become nonbasic, it never become basic? Does anybody has idea how to solve this problem ? "Show that in Phase I of the simplex method, if an articial variable becomes nonbasic, it need never again become basic. Thus, when an articial ... 1answer 978 views ### Minimal set of inequalities I have a set of m linear inequalities in R^n, of the form$$ A x \leq b  These are automatically generated from the specification of my problem. Many of them could be removed because they are ...
I am a student and I am studying the following problem during my spare time. Your comments and suggestions would be helpful. Given the following primal program: (Decision variables are $\xi_{v}$, ...