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

48 questions
Filter by
Sorted by
Tagged with
1 vote
66 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 ...
95 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 "...
61 views

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

I aim to solve the following Bellman equation: \begin{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}^{'} | \...
81 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}\\&...
113 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.}&\...
208 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 ...
51 views

### Dual of the alternative solutions

Suppose we have two alternative solutions for a linear program. Are their corresponding dual solutions the same? (in terms of the values for each dual variable)
543 views

### "Partial" Lagrangian Dual in LP

Consider the optimization problem \begin{align}\label{opt-lp}\tag{Primal} \begin{array}{cl} \underset{x \in \mathbb{R}^n}{\text{minimize}} & c^\top x \\ \text{subject to} & Ax = a \\ & Bx =...
545 views

### What is the relation between dual variables and reduced costs?

My background: Pure math current Undergrad, learned the theory of Operations Research, but pretty basic. All we covered have been dealing with problems that have only 1 constraint matrix. I have dealt ...
81 views