Hot answers tagged

32 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 ...
user avatar
  • 1,967
24 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 ...
user avatar
24 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 ...
user avatar
15 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, ...
user avatar
15 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 ...
user avatar
  • 5,377
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. ...
user avatar
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 ...
user avatar
  • 1,913
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 ...
user avatar
12 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) \...
user avatar
  • 3,283
10 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 ...
user avatar
  • 2,451
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): ...
user avatar
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$...
user avatar
9 votes

"Partial" Lagrangian Dual in LP

This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.
user avatar
  • 22.2k
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 ...
user avatar
  • 1,381
8 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 ...
user avatar
  • 29.7k
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\...
user avatar
  • 8,290
8 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 ...
user avatar
  • 5,833
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): ...
user avatar
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. ...
user avatar
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 ...
user avatar
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.
user avatar
  • 8,290
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 ...
user avatar
  • 29.7k
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 ...
user avatar
  • 5,377
6 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 ...
user avatar
  • 29.7k
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.
user avatar
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$ ...
user avatar
  • 29.7k
5 votes
Accepted

Following code doesn't work in matlab with CVX

Use CVX's entr function. $\sum_{i=1}^ 4x_i\ln(x_i)$ can be entered as -sum(entr(x)) ...
user avatar
5 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)....
user avatar
  • 29.7k
4 votes
Accepted

Derive "true" shadow price for degenerated LPs using commercial solvers (e.g. Gurobi)

I find the phrase "true shadow prices" misleading, and the use of "falsified" even more so, since the shadow prices any reputable solver returns are valid shadow prices ... ...
user avatar
  • 29.7k
4 votes
Accepted

When using column generation, can I delete a node with negative reduced cost from my subproblem?

If your sub-problem is a shortest path problem on a complete graph, without resource constraints, you can delete vertices which don't decrease the reduced cost. Indeed, for any path containing such a ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible