# Tag Info

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 ...

### 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 ...

### 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 ...

### 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 ...
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, ...

### 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. ...
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 ...
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) \...
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 ...

### 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 ...

### 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): ...
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$...

### "Partial" Lagrangian Dual in LP

This is called Lagrangian relaxation, no matter what subset of constraints you choose to dualize.
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 ...

### 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 ...
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 ...
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\...

### 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{...

### 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): ...

### 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. ...
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 ...

### 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.

### 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 ...

### 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 ...
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 ...

### 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.

### 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 ...

### 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 ...
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$ ...
Use CVX's entr function. $\sum_{i=1}^ 4x_i\ln(x_i)$ can be entered as -sum(entr(x)) ...