37
votes
Accepted
How can I remember the rules for taking the dual of a linear program (LP)?
There sure is! It's called the SOB Method, originally proposed by A.T. Benjamin.
In the SOB method, we classify each variable and each constraint as either sensible, odd, or bizarre (hence the name ...
- 2,117
26
votes
Dual bounds of integer programming problems
The notions of dual bound and primal bound originate a bit more generally, I think. We typically call an (iterative optimization) algorithm primal when it maintains a feasible solution in every ...
- 5,949
26
votes
Is there any relationship between KKT and duality?
KKT and duality are indeed closely related. To demonstrate this, I will look at a convex minimization problem in which all functions are convex and smooth. I will make use of Lagrange duality. Linear ...
- 6,362
19
votes
How can I remember the rules for taking the dual of a linear program (LP)?
I have always, for some reason, had troubles remembering those rules. In the book by Bertsimas and Tsitsiklis there is even a nice little table showing the conversion from a primal to a dual in a nice ...
- 6,667
16
votes
Accepted
Duality in mixed integer linear programs
It is a difference whether one can dualize (or not) or that a duality theory holds (or not). Formally, you can formulate a dual of any integer program, e.g., by considering the linear relaxation, ...
- 5,949
15
votes
How to take the dual of a conic optimization problem?
$\newcommand{\Rbar}{\overline{\mathbb{R}}}\newcommand{\R}{\mathbb{R}}\newcommand{\minimize}{\operatorname{Minimize}}$Another way to derive the dual for any convex problem is to use Fenchel duality.
...
14
votes
Accepted
Column generation for a linear optimization problem
TL;DR: column generation on the dual problem is 100% equivalent to cutting plane on the primal problem.
Equivalence between primal and dual form
Consider the (primal) LP problem
\begin{align}
(P) \...
- 4,268
13
votes
Accepted
How to take the dual of a conic optimization problem?
In Linear Programming (LP) one chooses a vector $\lambda \geq 0$ to obtain $\lambda^\top Ax \geq \lambda^\top b$ and whenever we find such a $\lambda \geq 0$ with $A^\top\lambda =c$ we obtain a lower ...
- 2,033
12
votes
Accepted
Robust counterpart: why is dual reformulation not working?
I think there are two small mistakes in your formulation:
In the final formulation, the roles of $x$ and $z$ should be reversed.
Except for the first constraint and for the non-negativity of the ...
- 6,362
11
votes
How can I remember the rules for taking the dual of a linear program (LP)?
Here is a simple rule I use. Assume you are minimizing and
$$
A x \leq b
$$
So the dual value $(y)$ tells you how the objective value change if you increase b. Now if you increase b, then you relax ...
- 3,216
10
votes
"Partial" Lagrangian Dual in LP
This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.
- 33.6k
9
votes
Accepted
Can we have all reduced costs (strictly) positive?
This may depend on how you define "reduced costs". If you mean reduced costs as computed by the simplex algorithm, then no, it is not possible that all are strictly positive due to the mechanics of ...
- 40.1k
9
votes
How to take the dual of a conic optimization problem?
Succinct and (freely) accessible references, which include general "theory". Also, solved examples,. for instance for Second Order Cones (SOCP) and Linear Semidefinite cones (LMI, i.e., Linear SDP):
...
- 13.8k
9
votes
Accepted
How to relate dual values of valid inequality to the dual values of the original problem?
For simplicity, I will
replace $\sum_i \beta_{i,j}$, $ \sum_i f_{i,j}$, and $\alpha_j$ by $x$, $y$, and $z$, respectively.
assume that $x$, $y$, and $z$ are defined to be non-negative.
assume that $x$...
- 6,362
9
votes
Accepted
"Partial" Lagrangian Dual in LP
Based on the mentioned references, suppose the primal problem is:
\begin{align}
\begin{array}{cl}
\underset{}{\text{minimize}} & c x \\
\text{subject to} & Ax = a \\
& Dx \leq e \\
& x ...
- 9,283
8
votes
Tool to get dual problem from any linear optimization problem (.lp)
I recommend having a look at the most recent developments around JuMP. They have developed two interesting packages this year:
MathOptFormat.jl, that allows to import/export optimization problem in ...
- 1,511
8
votes
Accepted
Finding Dual Objective
For each variable, you need to define a constraint in the dual problem and likewise, for each constraint in the primal problem, you will have a dual variable.
\begin{align}\min&\quad\overline X\...
- 8,677
8
votes
Existence of extreme points in primal and dual LP
Besides useful comment and answer, let's depict out the feasible space of the linear problem and its equivalent dual in some simple examples.
1) When the primal problem has an optimal solution:
\begin{...
- 9,283
7
votes
Does strong duality hold when I dualize only a subset of the constraints?
If strong duality holds, then it also holds when only a subset of the constraints is dualized.
We define the following three problems: the original, the partially dualized, and the dual.
Problem (P1):
...
- 6,362
7
votes
Accepted
Simple nonlinear programming using convexity analysis and KKT
You should use the KKT conditions (turning the sign restrictions on $x$ into constraints), but it turns out they will not affect the results. First, let me point out that $\partial L/\partial x_1$ is ...
- 40.1k
7
votes
Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences
In general, nonlinear optimization algorithms implemented in finite precision floating point software don't converge exactly to an optimal solution exactly satisfying the optimality conditions. ...
- 13.8k
7
votes
Accepted
Correct way to get a dual extreme ray for an infeasible LP in CPLEX / C++
Can you elaborate a bit on what you mean when you say you are getting "Strange values"? One possible explanation is that if you call getDuals() on a model that ...
- 161
6
votes
Tool to get dual problem from any linear optimization problem (.lp)
The link includes an online converter from primal to dual linear programs. The downside is you need to input all the coefficients and variables into the pre-defined form on the webpage.
- 8,677
6
votes
Is the iteration-limited Simplex dual solution of a MIP node useful?
It is common practice for MIP solvers to solve node LPs (other than at the root node) via dual simplex. I can't say with certainty that they terminate dual simplex prematurely if the objective value ...
- 40.1k
6
votes
Is the iteration-limited Simplex dual solution of a MIP node useful?
Yes, you can solve the dual and use that as a (weaker) bound than the optimal solution of the LP. This leads to the trade off between faster processing nodes vs processing more nodes. This approach is ...
- 6,667
6
votes
Accepted
What is the relation between dual variables and reduced costs?
First, as a note, your formulation (minimizing with $\le$ constraints) will produce nonpositive shadow prices. It might be easier to understand if you use $\ge$ constraints (nonnegative shadow prices)....
- 40.1k
6
votes
What is the relation between dual variables and reduced costs?
If you interpret $$A= \begin{pmatrix}G \\ H\end{pmatrix}$$ then $$\pi^TA_j = \mu^T G_j + \lambda^T H_j$$ (where $\pi,\mu,\lambda$ are the corresponding duals) is not a surprise.
- 2,865
6
votes
How do you get the primal solution of an LP from the dual solution?
The duals or shadow prices of the dual model give you a primal solution. See http://yetanothermathprogrammingconsultant.blogspot.com/2022/08/primal-dual-and-equilibrium-format-of.html for a simple ...
- 2,865
6
votes
Simple OLS problem can only be solved in SCS. Is the dual infeasible?
Mosek does not fail. Mosek says the problem is dual infeasible which means if the problem has solution, then it is unbounded. In fact Mosek has a quite good certificate for that.
Since your problem ...
- 3,216
5
votes
Accepted
Physical Interpretation of a dual of an LP
The dual variables represent the marginal effect on the primal objective (total units purchased) per unit change in each primal constraint limit. So increasing (decreasing) the required amount $A_m$ ...
- 40.1k
Only top scored, non community-wiki answers of a minimum length are eligible