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

learn more… | top users | synonyms

13
votes
1answer
145 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 ...
11
votes
0answers
212 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 ...
10
votes
3answers
8k 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 ...
8
votes
6answers
4k 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 ...
8
votes
1answer
37k 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 ...
7
votes
5answers
4k 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 ...
7
votes
2answers
326 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$ ...
6
votes
2answers
6k 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 & ...
6
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 ...
6
votes
1answer
833 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 ...
6
votes
1answer
203 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
93 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
81 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
351 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) = ...
6
votes
2answers
532 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
802 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 ...
6
votes
0answers
90 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
3answers
4k 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 ...
5
votes
1answer
3k 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 ...
5
votes
2answers
1k 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 ...
5
votes
2answers
146 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. $$ ...
5
votes
2answers
2k 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 ...
5
votes
1answer
2k 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
1answer
380 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 ...
5
votes
1answer
6k 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 ...
5
votes
1answer
70 views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, ...
5
votes
1answer
125 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) $$ ?
5
votes
0answers
546 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} ...
4
votes
5answers
1k 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
584 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 ...
4
votes
1answer
436 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\\ ...
4
votes
1answer
1k 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.
4
votes
2answers
221 views

Wolves and chicks puzzle

This problem is from the handheld video game, Professor Layton and the Curious Village. I think the solution is very cool, but more than that, I want to know how to show that the minimum number of ...
4
votes
1answer
477 views

How to determine whether a system of linear inequalities has a POSITIVE solution or not?

The question I'd like to ask is as in the title: How to determine whether a system of linear inequalities has a POSITIVE solution or not? Is there any poly-time algorithm to do this? Or the best ...
4
votes
2answers
58 views

Very symmetric convex polytope

Let $C_n$ be the convex polytope in ${\mathbb R}^n$ defined by the inequalities (in $n$ variables $x_1,x_2, \ldots ,x_n$) : $$ x_i \geq 0, x_i+x_j \leq 1 $$ (for any indices $i<j$). Denote by ...
4
votes
2answers
2k 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 ...
4
votes
1answer
177 views

Writing a linear program in standard form

Usually I have been asked to write problems in standard form that have inequalities involved. However, this problem has none and I was wondering if anyone had insight on how to go about solving it. ...
4
votes
1answer
334 views

Is the inverse of an invertible totally unimodular matrix also totally unimodular?

My question is learned from here. Let me restate it as follows: A unimodular matrix $M$ is a square integer matrix having determinant $+1$ or $−1$. A totally unimodular matrix (TU matrix) is a matrix ...
4
votes
1answer
378 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} ...
4
votes
1answer
471 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 ...
4
votes
2answers
404 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 ...
4
votes
1answer
388 views

Confused about linear programming exercise solution in my textbook

please see this simple linear programming exercise and its solution from my textbook. The task is to convert the prose and matrix to a formal linear programming problem. My answer matched theirs ...
4
votes
2answers
174 views

Help with formulating a linear programming problem

I have the following linear programming problem I would like to be verified: I have sketched the problem in the following picture: Here is my attempted solution: I figured that I have ten ...
4
votes
1answer
770 views

Proving Helly's theorem

The problem is to prove Helly's theorem for the case, when the convex bodies are polytopes, by using linear programming duality. Helly's theorem Let $B_{1},...,B_{m}$ be a collection of convex ...
4
votes
1answer
108 views

Membership problem for convex cones

Does anyone have a reference for the most efficient or some simple reasonably efficient algorithm for the membership problem for convex cones: Given a finite set of vectors $v_1, ..., v_n$ and a ...
4
votes
2answers
263 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 ...
4
votes
1answer
63 views

How can the formula be found for this problem?

We have a truck that we need to completely fill up with merchandise. We have an infinite supply of merchandise of dimension $1\times1\times1, 2\times2\times2, 4\times4\times4, 8\times8\times8, ...
4
votes
1answer
653 views

How to solve system of equations with multiple constraints?

I have a system of equations that looks like this: $$\begin{array}{rl} a_1 b_1 c_1+a_2 b_2 c_2+a_3 b_3 c_3&=1000\\ a_1+a_2+a_3&=1\\ a_2&=0.6 \,a_1\\ b_1+b_2+b_3&=500 \end{array}$$ ...
4
votes
1answer
816 views

Regarding complementary slackness condition

I have a question regarding complementary slackness, the answer should be true of false. The complementary slackness conditions connect pairs of optimal basic feasible solution of primal and dual ...
4
votes
1answer
212 views

Book on advanced topics of Network Flows

I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...