Tagged Questions
3
votes
1answer
196 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
6answers
1k 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 ...
1
vote
2answers
80 views
Max and min value of $7x+8y$ in a given half-plane limited by straight lines?
So, there are four inequalities:
$$\begin{eqnarray*}
y &\geq &-3x+15; \\
y &\leq &-11/3x+56/3; \\
x &\geq &0; \\
y &\geq &0.
\end{eqnarray*}$$
If we draw all those ...
1
vote
2answers
133 views
How can I infer a result using primal feasibility, dual feasibility, and complementary slackness?
I am trying to find the minimum of $-x_1$ with restrictions $\bar g\leq\bar 0$ so that
$$\bar g=\begin{pmatrix}
(x_1+2)^2+(x_2-4)^2-20\\
(x_1+2)^2+x_2^2-20\\
-x_1\end{pmatrix}\leq ...
3
votes
1answer
154 views
What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?
EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
1
vote
2answers
272 views
Sign restriction on the Lagrange multiplier? Why?
Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints ...
1
vote
1answer
92 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?
1
vote
1answer
2k 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 ...
1
vote
1answer
210 views
Sudoku mathematically, MILP?
My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
1
vote
1answer
183 views
Questions about weak duality theorem
Following are some corollaries regarding the weak duality theorem.
Consider a constrained problem,
$\min_{x \in X} f(x),$ subject to
$g(x) \leq 0$ and $h(x) =0$.
Its dual problem is $\sup_{u \geq ...
1
vote
3answers
2k 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 ...
0
votes
1answer
172 views
Underlying assumption in a Primal/Dual table
I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144.
...
