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

91 questions
Filter by
Sorted by
Tagged with
30 views

### Regarding Benders Decomposition for Master Problem with Binary Variables and Sub-problem with Integers (Not Continuous Variables) [duplicate]

I have a question on Benders Decomposition (BD). I have a MILP model which can be decomposed into a master problem (MP) comprising only binary variables and a subproblem (SP) though containing only ...
• 793
1 vote
73 views

I have a LP problem like: \begin{align} \min &\quad z = c^T x \\ s.t. &\quad Ax\le b \\ &\quad x\ge 0 \end{align} Assume the optimal solution of this problem is $x^*$ and the dual optimal ...
• 13
77 views

### General questions concering column generation

I have a basic question about the Dantig-Wolfe reformulation. How do I know which constraints go into the master problem and which into the subproblem(s)? As I understand it, constraints that connect ...
834 views

### Why does multiple pricing work?

Adding multiple columns with negative reduced costs instead of only the one with the most negative reduced column (also called multiple pricing) is essential for solving some problems with column ...
• 650
1 vote
135 views

### Graphical understanding of the primal and dual problem

I have a relatively simple question. Assuming we have a simple numerical example of an LP with two decision variables and two constraints (non-negativity excluded), how can I visualize the graphical ...
• 11
59 views

### What's the dual of an LP in its general form?

For an LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ &l^{x}\leq x \leq u^{x} \end{align} how can we get its dual ...
• 77
1 vote
111 views

### Economic interpretation of shadow/dual variables in LP

I have recently read a text which deals with the dual variables attached to constraints. In an economic sense, one can interpret them as shadow variables indicating market clearing for resource ...
75 views

### How to implement self-adjusting smoothing in column generation?

I am currently trying to implement the "Smoothing with a Self-Adjusting Parameter" methodology (on the right in Table 1) from Pessoa et. al (2018) in my MILP. Unfortunately, I am not quite ...
61 views

• 1,015
1 vote
58 views

### Distributionally Robust Stochastic Programming - Help with derivation

I've been working through this book on robust optimization of electric energy systems, and in particular chapter 4 on distributionally robust optimization. In following the derivation of section 4.2.1....
1 vote
1k views

1 vote
140 views

### Persisting Subproblem Infeasibility Benders Decomposition

I'm currently working on an optimization problem where I'm using Benders decomposition to solve a complex problem involving the installation of charging stations. The master problem determines the ...
• 21
239 views

### How do you derive the Benders feasibility cuts?

starting off with a MIP that I want to solve using Benders. so in Benders Decomposition, you add feasibility cuts in the following form: $v^j (b - Ax) \geq 0$ with $j \in J$ being the set of extreme ...
• 327
84 views

### Can dual values smoothing lead to generating duplicate columns?

When using smoothing for dual values stabilization in column generation, the duals used in the subproblem lie on the segment joining the stability center (inside the dual feasible region) and the ...
105 views

### Dual norm definition: adding new constraints

For some $c >0$ and $z \in \mathbb{R}^n$, the optimal value of \begin{align} \begin{array}{cl} \sup_{x \in \mathbb{R}^n}& z^\top x \\\text{s.t.}& \lVert x \rVert \leq c \end{array} \end{...
• 4,020
1 vote
160 views

• 33
310 views

### Phase I of the simplex method and Farkas certificates

Phase I of the simplex method solves an auxiliary optimization problem to determine an initial basic feasible solution, or concludes that no such exists. Is there a way to use the solution of this ...
• 223
201 views

### Convex optimization with linear constraints. Can I solve it analytically?

I have a constrained convex optimization problem with linear equality and inequality constraints. \begin{align} \label{eq:costf} \text{minimize}\ \ &f(x_1,\dots,x_m) = \sum_{i=1}^m \frac{1}{...
1 vote
179 views

### Dual solution when solving a primal degenerate LP with the interior point algorithm

Say, we're working with an LP that is primal degenerate (optimal solution is at a vertex but with multiple bases) and not dual degenerate (optimal solution is not at a face). If we were to solve it ...
• 173
1 vote
73 views

### Dual of a quadratic constraint

This is my model. \begin{align} \min_x&\quad\sum_{e\in E} X_e p_e \\ \text{s.t.}&\quad\sum_{e \in E: T(e)=i} X_e - \sum_{e \in E: H(e)=i} X_e = \begin{cases}1, \;\text{if}\;i=s\\-1,\;\text{if}...
• 517
1 vote
162 views

### Help with dual of a problem

Could anyone confirm me if I write the correct dual for my problem? The different sets confuse me a lot. $s$ is the source node and $t$ the sink node. I'm uncertain if the last dual constraint in ...
• 517
156 views

### Light weight proof of strong duality in linear programming

For teaching purposes, I believe it can be good to use very light-weight proofs of deep results, as it often answers the question "why is it true" better than other types of proofs. By "...
• 6,667
77 views

### Linear programming approach to dynamic programming - an initial pair of state-decisions

I aim to solve the following Bellman equation: v(\vec{s}) = \min_{\vec{x} \in \Xi_{\vec{s}}} \big\{c(\vec{s}, \vec{x}) + \lambda \times \sum_{\vec{s}^{'}\in S} p(\vec{s}^{'} | \...
• 615
189 views

### What is the dual of this LP?

Here is my simple LP problem for a constant symmetric positive matrix $d$ and continuous decision variables $x$: \begin{align}\max&\quad\sum{x_i}\\\text{s.t.}&\quad x_i + x_j \leq d_{ij}\\&...
• 950
213 views

### min max inside a linear program

Although this sounds like a standard minimax problem, I'm not sure how to deal with feasibility issues. Consider a maximin linear program \begin{align}\max_x\min_y&\quad c^\top y\\\text{s.t.}&\...
• 179
227 views

### Airline revenue management re-solving problem

I am considering a bid prices (shadow price of the capacity constraint) problem (from Chen, L. and Homem-de Mello, T. (2009)., page 14) where the acceptable classes for booking requests for ...
• 165