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

learn more… | top users | synonyms

14
votes
1answer
168 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 ...
14
votes
0answers
360 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 ...
12
votes
1answer
74k views

shadow price 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 ...
12
votes
3answers
16k 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 ...
12
votes
3answers
289 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 ...
12
votes
1answer
176 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 ...
11
votes
6answers
8k 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 ...
11
votes
2answers
8k 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 (...
10
votes
5answers
6k 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 ...
9
votes
2answers
3k 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 ...
8
votes
1answer
1k 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 ...
7
votes
2answers
10k views

Primal and dual solution to linear programming

Lets say we are given a primal linear programming problem: $\begin{array}{ccc} \text{minimize } & c^{T}x & &\\ \text{subject to: } & Ax & \ge & b \\ & x & \ge & ...
7
votes
3answers
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 ...
7
votes
1answer
2k views

Linear Programming: More variables or more constraints; which one is better?

This is more of a practical question, rather than Math question. I have an LP which has $n$ variables and $m$ constrains, where $ n << m $. If I convert this into its dual form, I will have $...
7
votes
1answer
9k 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 ...
7
votes
1answer
234 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-...
7
votes
2answers
551 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$ [...
7
votes
1answer
252 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 ...
6
votes
3answers
5k 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 ...
6
votes
4answers
1k 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$...
6
votes
2answers
2k 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/...
6
votes
1answer
601 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 ...
6
votes
1answer
245 views

Difficulties in Writing the Dual of a Primal Program

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}$, ...
6
votes
1answer
134 views

Why is there n-1 different objects in a n by n matrix game like Bejeweled?

For games that consists of a grid, and is similar to the concept like bejeweled: has an n by n matrix and n-1 different objects. What is the reason for this? Why not have more than n-1 different ...
6
votes
1answer
101 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 $\...
6
votes
1answer
475 views

What is graph theory interpretation of this linear programming problem?

So, I am looking at a paper by Rosenfeld, "On a problem of C.E. Shannon in graph theory", where he gives necessary and sufficient conditions for a graph $H$ to satisfy $$\alpha(G \boxtimes H) = \alpha(...
6
votes
1answer
644 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
6
votes
1answer
4k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
6
votes
1answer
160 views

Under what conditions minimax is equivalent to maximin?

Under what conditions $$ \min_{x} \max_{y} f(x,y) = \max_y \min_x f(x,y) $$ ?
6
votes
2answers
684 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?
6
votes
0answers
98 views

Does the Hirsch conjecture hold for $n < 2d$?

The Hirsch conjecture states that the graph (i.e. $1$-skeleton) of a $d$-dimensional polytope with $n$ facets has diameter at most $n - d$. It was known for a long time that it sufficed to prove it ...
5
votes
5answers
14k 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 ...
5
votes
1answer
772 views

Duality. Is this the correct Dual to this Primal L.P.?

Given a problem: Find the dual: $$ Primal =\begin{Bmatrix} max \ \ \ \ 5x_1 - 6x_2 \\ s.t. \ \ \ \ 2x_1 -x_2 = 1\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1 +3x_2 \leq9\\ ...
5
votes
1answer
2k views

Finding all n×n permutation matrices

If I have a doubly stochastic matrix, how can I find the set of all basic feasible solutions? Here's Wikipedia on doubly stochastic matrices.
5
votes
2answers
160 views

Almost a linear program. How to solve efficiently?

How can one go about solving this optimization problem efficiently? Unfortunately it is a maximization instead of a minimization, which stymied my attempts at converting it into an LP. $$ \mbox{...
5
votes
2answers
4k 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 ...
5
votes
2answers
656 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 ...
5
votes
1answer
3k views

simplex method : Entering Variable

In the Simplex method, a variable that enters the basis, cannot depart the basis in the very next iteration. Please explain..why so ?
5
votes
2answers
3k views

Understanding proof of Farkas Lemma

I've attached an image of my book (Theorem 4.4.1 is at the bottom of the image). I need help understanding what this book is saying. In the first sentence on p.113: "If (I) holds, then the ...
5
votes
2answers
792 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 ...
5
votes
1answer
655 views

Determining quickly whether this Integer Linear Program has any solution at all

I've got an integer linear program of the form $$ \begin{aligned} \text{Minimize}&& c &= x_1 + \cdots + x_m \\ \text{subject to}&& A\mathbf{x} &\geq \mathbf{b} \\ \text{where} &...
5
votes
1answer
679 views

How does multiplying a primal constraint by a constant change the dual solution?

Suppose we have the problem $\min c^T x$, subject to $Ax=b, x \geq 0$. Suppose that this program and its dual are feasible. Let $\lambda$ be the optimal solution of the dual. If the $k$th constraint ...
5
votes
2answers
227 views

Convert a piecewise linear non-convex function into a linear optimisation problem.

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, &...
5
votes
1answer
226 views

Easy elementary proof of Farkas Lemma?

Is there any elementary proof of Farkas lemma which does not use convex analysis and hyperplane separation theorem? What about special case below: If the Matrix $A$ is invertible, then there is ...
5
votes
0answers
43 views

Optimizing value of discrete harmonic function at a given point

Let $n>0$, and let $S_n$ denote the discrete square $S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
5
votes
1answer
4k views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ x_1&&&-&x_3&...
5
votes
0answers
664 views

Maximum and minimum of an integral under integral constraints.

Find the maximum and minimum of the following integral in terms of $f(x),a,C$: \begin{align}I=\int_{0}^{a} \frac{x}{f(x)}p(x)dx \end{align} s.t.: 1) $\int_{0}^{a} p(x)dx=1$ 2) $\int_{0}^{a} f(x)p(x)...
4
votes
5answers
6k 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 ...
4
votes
5answers
101 views

Feasible point of a system of linear inequalities

Let $P$ denote $(x,y,z)\in \mathbb R^3$, which satisfies the inequalities: $$-2x+y+z\leq 4$$ $$x \geq 1$$ $$y\geq2$$ $$ z \geq 3 $$ $$x-2y+z \leq 1$$ $$ 2x+2y-z \leq 5$$ How do I find an interior ...
4
votes
5answers
921 views

Find a convex combination of scalars given a point within them.

I've been banging my head on this one all day! I'm going to do my best to explain the problem, but bear with me. Given a set of numbers $S = \{X_1, X_2, \dots, X_n\}$ and a scalar $T$, where it is ...