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

learn more… | top users | synonyms

1
vote
1answer
542 views

Weak duality theorem and false corollary

Let $A\in\mathbb{R}^{m\times n}, \ c\in \mathbb{R}^n, \ b\in\mathbb{R}^m$ and consider the linear program $$\max \{ c^Tx : Ax\le b\} \ (1)$$ Its dual is $$\min \{ b^Ty : A^Ty=c, \ y\ge 0\} \ (2)$$ The ...
1
vote
1answer
776 views

How to set up a linear programming problem?

I'm not 100% sure if I set up the following problem right. Once I have the problem set up I know how to solve it. (this is a homework problem) The problem goes like this:"A company can use plastic, ...
3
votes
1answer
1k 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 ...
0
votes
1answer
116 views

binary variable question

I need to make a constraint for the following condition: Student 1 can only be on the team if students 2, 3, 4, and 5 are also on the team. I'm not sure how to model this using equations. The ...
1
vote
2answers
2k views

Help with binary variable

I need to make a constraint for the following condition: Among students 1, 2, 3, and 4, at least two of them must be on the team, if there are any on the team at all. I have defined Y1, Y2, Y3, and ...
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 & ...
2
votes
2answers
4k views

Can a non-degenerate LP have multiple optimal solutions?

In linear programming, an LP can have multiple optimal solutions if it contains degenerate vertices, i.e. where one of the base-variables is 0. Can an LP also have multiple optimal solutions if it ...
1
vote
1answer
115 views

Basic linear problem solving

I have some LP problem and I'm willing to solve it (this is an exercise from some optimization-related book). Now, Mathematica tells me that the problem is unbounded and I want to make a generic ...
0
votes
1answer
45 views

How can I adapt my problem so that it is amenable to the simplex algorithm?

According to the Wikipedia article, the Simplex algorithm depends on constraining all the unknowns to be >= 0. I have a problem where one of my variables is highly likely to be negative in many ...
3
votes
0answers
245 views

Bender's Decomposition for Mixed Integer Programs

Say I have 2 LPs, LP_1 and LP_2 which have real and integer variables and a staircase structure (i.e. the solution and feasible region of LP_2 depends on the solution of LP_1). $LP_1$ has the form ...
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 ...
2
votes
1answer
466 views

In linear optimization, what does “AP” stand for?

I am learning algorithms, and there is a chapter which uses linear optimization methods to solve a matching problem. This is the problem definition: I find the abbreviations AP for the constraints ...
2
votes
0answers
130 views

Mathematical Programming Community

Is there a good online community for discussing optimization models? The ones I have found don't seem to have a critical mass for active discussions.
1
vote
1answer
177 views

Use duality to find a strong alternative

Find a necessary and sufficient condition for the linear equation Ax = b to have no solution. (hint: Use duality to find a strong alternative to Ax = b).
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 ...
3
votes
1answer
97 views

Determine which of 8 points make up the 4 corners of a cube's face

I am working on a game program. I have an array of 8 points in 3d space $(X,Y,Z)$ that are the 8 corners of a cube whose $W=H=D$. The 8 points are listed in no particular order. For the sake of ...
3
votes
1answer
236 views

Prove property of dual Linear Programming problem

If i have a standard LP problem: $$\min \mathbf{d}^T \mathbf{x}$$ subject to $$\mathbf{B}\mathbf{x}=\mathbf{f},\qquad \mathbf{x} \geq 0$$ $\mathbf{y}$ is the optimal solution and $\mathbf{z}$ is ...
2
votes
1answer
467 views

Linear optimization constrained by cost function

Suppose I have an optimization problem of the form: $$\min \mathbf{d}^{T}\mathbf{y}$$ subject to $$\mathbf{M}\mathbf{y} \geq \mathbf{d}, \qquad \mathbf{y} \geq 0$$ If a solution $\mathbf{s}$ ...
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.
3
votes
1answer
95 views

Simplex - 2 different points with the same cost?

Is it possible to have 2 different points (non-degenerate) in $n$-dimensions for any value of $n$ where $n>1$, share the same cost and both be visited by the simplex method?
0
votes
1answer
323 views

Convert linear programming problem

Suppose x is the solution to a standard linear programming problem ($Ax=b$, $x>=0$) and the set $S$ is every $i$ where $x_{i} = 0$. How can I show this is optimal only where minimize $c'f$ subject ...
2
votes
1answer
433 views

Prove feasible direction

If $x$ is an element in a standard convex linear optimization set constrained by $Ax = b, x \geq 0$, then how can I prove $d$ is a feasible direction only if $Ad=0$ and $di \geq 0$ for every $i$ where ...
0
votes
1answer
1k views

How to show a set is convex

Looking for a hint on show to show convexity in a set.... Let $f\colon \mathbb{R}^n \rightarrow \mathbb{R}$ be a convex function and let $c$ be some constant. Show that the set $s=\{x \in ...
3
votes
4answers
2k views

Karush-Kuhn-Tucker condition - Lagrange multiplier

I was maths student but now I'm a software engineer and almost all my knowledge about maths formulas is perished. One of my client wants to calculate optimal price for perishable products. He has ...
4
votes
0answers
470 views

How to Minimize A Function Where The Number of Variables is Unknown

I have a standard linear programming problems I want to solve: $$ \min_x f^T x \text{ such that } \left\{ \begin{aligned} A\cdot x &\le b, \\ A_{eq}\cdot x &= b_{eq}, \\ lb \le x &\le ub. ...
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 ...