The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [duality]

For questions on duals of (primal) mathematical programs that optimize the complementary bound. When minimizing, for example, primal solutions are upper bounds, and dual solutions lower bounds on the optimal value.

Filter by
Sorted by
Tagged with
14
votes
1answer
308 views

Duality in mixed integer linear programs

I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
13
votes
1answer
116 views

Robust counterpart: why is dual reformulation not working?

I am trying to solve robust optimisation problems, but I am getting nonsensical solutions most of the time… Here is a very simplified example: \begin{alignat}{2}\max&\quad x+z&\\\text{s.t.}&...
17
votes
2answers
262 views

Tool to get dual problem from any linear optimization problem (.lp)

Is there a tool that reads any linear optimization problem (for example an .lp or .mps file), converts it to the dual problem and prints the dual problem?
11
votes
1answer
124 views

How to relate dual values of valid inequality to the dual values of the original problem?

I have a given formulation that looks like this (just for the constraints): $$\sum_i \beta_{i,j} \geq \alpha_j,\qquad\forall j$$ $$\alpha_j \geq \sum_i f_{i,j},\qquad\forall j$$ $$\alpha_j \geq 0, ...
11
votes
1answer
168 views

Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences

My question concerns recovering a primal optimal solution while performing dual sub gradient ascent. Denoting by $y_i$ the dual multiplier in the $i^{\text{th}}$ iteration, let \begin{equation} x_i = ...
12
votes
2answers
244 views

Correct way to get a dual extreme ray for an infeasible LP in CPLEX / C++

We are coding a Benders decomposition using CPLEX/Concert (C++) and we are having some troubles to generate a feasibility cut because we are not sure how to get an extreme ray of the dual for a primal ...
16
votes
3answers
122 views

How to take the dual of a conic optimization problem?

Given a conic problem $$\min \{c^\top x \mid Ax \succeq_\mathit{C} b\}$$ for an arbitrary cone $C$, how can I construct the dual to the problem? Moreover, in Linear Programming one constructs the ...
19
votes
4answers
206 views

How can I remember the rules for taking the dual of a linear program (LP)?

When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?...