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
0
votes
0
answers
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
1
answer
73
views
About the mathematical proof of shadow price
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
0
votes
2
answers
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 ...
3
votes
2
answers
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
1
answer
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
0
votes
0
answers
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
1
answer
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 ...
- 111
2
votes
1
answer
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 ...
- 89
0
votes
0
answers
61
views
Dual stabilization doesnt work properly
I am currently trying to speed up my column generation approach to reduce the tailing-off effect. I have modified my master problem as follows. For this I have introduced $\phi_{ts}^+,\phi_{ts}^-,\...
- 139
2
votes
1
answer
143
views
How to improve a column generation algorithm
I have been busy the last few weeks implementing this model with Column Generation in Gurobi and then solving it. The whole thing is now working quite well and I have also run a few calculation ...
- 139
0
votes
1
answer
67
views
Does strong duality hold for this semidefinite program?
$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP)
$$
\begin{aligned}
\max_V \quad & \Tr(V) \\
\textrm{s.t.} \quad & \...
- 639
0
votes
0
answers
44
views
Lagrange Duality in Robust Optimization
I am learning Robust Optimization and been stuck on this example. I've brushed up on my knowledge of Lagrange duality and referred to a couple of textbooks on Linear Programming but not able to ...
1
vote
0
answers
61
views
Quadratic conic program duality
I am working on a problem relating to what is known as the "Good Deal risk measure" for production valuation in incomplete markets. I have created the following primal optimization problem, ...
0
votes
1
answer
59
views
Lagrange multiplier associated to an active inequality constraint
Why is the Lagrange multiplier associated to an active inequality constraint is positive.
How can we see this from the KKT conditions?
- 419
0
votes
0
answers
32
views
Unclear points in derivation of Lagrange duality for a quadratic optimization problem
Problem0:
$\displaystyle \min_{\mathbf{u} \in \mathbf{R}^L}\frac{1}{2}\mathbf{u}^TQ\mathbf{u}+\mathbf{p}^T\mathbf{u}$
$\,$ subject to $\,$ $\mathbf{a}^T\mathbf{u} \ge c$
Problem1:
$\displaystyle \...
- 419
0
votes
1
answer
98
views
Dual of second order cone programming with both equality and inequality constraints
How to derive the dual of a second order cone programming with both equality and inequality constraints?
Here is the optimization problem I want to handle:
$$
\begin{array}{rl}\min_{\mathbf{x},\mathbf{...
3
votes
1
answer
62
views
Is there a way to find out which original constraints are violated when a feasibility cut is generated in benders?
I've been dealing with Benders Decomposition and I've been wondering, if I have an unbounded solution of the dual subproblem, is it possible to find out which constraint from the original problem is ...
- 327
2
votes
1
answer
82
views
Reducing optimality to feasibility in non-linear programs
It is well-known that, given a linear program: minimize $c^T x$ such that $A x\leq b$, it is possible to reduce the program to deciding feasibility of the following set of constraints:
$Ax \leq b, A^T ...
- 1,015
1
vote
0
answers
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....
- 76
1
vote
1
answer
1k
views
Question about Pricing Problem in Column Generation
In column generation, we need to solve the following pricing problem :
$$\min c_j-\bf{c}^T_B\bf{B}^{-1}\bf{N}_j$$
In the book, I saw authors say that according to duality theory, $\bf{y}^T = \bf{c}^...
- 25
1
vote
1
answer
172
views
Primal-Dual Simplex Algorithm
Are there any recommended textbooks or notes to learn the details about the primal-dual simplex algorithm?
- 25
1
vote
1
answer
99
views
how do I find the dual when a variable has an upper bound?
What is the dual of this primal LP?
$$
max~c^Tx
$$
$$
s.t.~Ax=0
$$
$$
0 \leq x \leq d,~d \in \mathbb{R}_+^n
$$
- 950
2
votes
0
answers
87
views
Approximating an LP with an exponential number of variables and an almost-separation-oracle to its dual
Problem settings:
we have $n$ agents and a set $\mathcal{S}$ of possible world-states, where the size of $\mathcal{S}$ is exponential with respect to $n$.
Each agent $j$ has a utility function $u_j\...
- 73
1
vote
2
answers
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
2
votes
1
answer
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
4
votes
1
answer
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 ...
3
votes
1
answer
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
1
answer
160
views
Equivalent condition for indicator function
We have the following two conditions:
$C1.$ $l(x) \geq 0$ for all $x\in \mathbb{R}^n$,
$C2.$ $l(x) \geq 1$ for all $x\in \mathbb{R}^n$ such that $a+b^Tx \leq 0.$
Here $l(x) = \begin{bmatrix} x^T 1 \...
- 111
0
votes
0
answers
43
views
Dual prices remain stable but negative in column generation
I arrive at an objective function value that I know to be optimal. However, dual prices remain negative (which leads me to believe another pattern can be added, but when I do, the dual prices don't ...
5
votes
2
answers
520
views
Simple OLS problem can only be solved in SCS. Is the dual infeasible?
Essentially, I am trying to solve a simple orthogonal least-squares (OLS) problem with some constraints — the coefficients must sum to $1$, no coefficient can be less than $0$, and no coefficient can ...
4
votes
2
answers
480
views
What happens to the dual and primal feasibility when a constraint is removed after finding an optimal solution?
Assuming I had solved the a problem to optimality, I want to remove a constraint.
What happens to primal feasibility?
What happens to dual feasibility?
How to solve this new problem efficiently?
My ...
- 253
4
votes
3
answers
386
views
Existence of extreme points in primal and dual LP
If the nonempty feasible set of a primal LP has extreme points does its dual also have extreme points? I know that a standard form LP (nonempty) always has extreme points. But I am not sure if we can ...
- 97
3
votes
2
answers
154
views
Partial Lagrangian in the Max-Flow problem
In the question:
"Partial" Lagrangian Dual in LP
It is argued that considering a partial Lagrangian $L_{partial}$, where we Dualize only some of the constraints, results in a tighter ...
- 143
6
votes
1
answer
464
views
Dantzig-Wolfe vs Benders Decomposition on the dual problem - Computational differences
My question is a follow-up to this one: Relationship between Benders’ decomposition and Dantzig-Wolfe decomposition. Here what is being discussed is the relationship between the two methods, and it is ...
- 650
1
vote
2
answers
70
views
Number of solutions to geometric program
Is it possible to determine if a Geometric Program (GP) has one, none, or infinite (primal) solutions by its structure (e.g., in terms of the number of variables, constraints, or product terms ...
- 215
3
votes
0
answers
136
views
How to find robust counterpart of sum of logit functions?
Suppose function $\mu_i(y):\mathbb{R} \rightarrow \mathbb{R}$ is a logit function, $\mu_i(y)=1/(1+\exp(-y))$. Also, we assume that $\mathbf{x}_i\in \mathbb{R}^d$ and $\theta \in \mathbb{R}^d$. I am ...
- 2,160
2
votes
1
answer
111
views
How do you recover dual variables for a minimum weight bipartite perfect matching problem?
I feel like I must be missing something obvious but this is confusing me. Let's say I have an optimal solution $x^*$ to a minimum-weight perfect bipartite matching problem on $2n$ nodes, $$\min\sum_i\...
- 173
4
votes
3
answers
2k
views
How do you get the primal solution of an LP from the dual solution?
I am new to Optimization so I think the following question may be very easy, but I'm not sure how to solve it.
The dual of an LP is an LP. If we solve the dual LP, we can get the optimal value for the ...
- 141
3
votes
2
answers
287
views
Related to Lagrangian dual
In my research class our professor discuss a paper wherein the solution is obtained via a Lagrangian duality. The original problem is given below:
minimize $t$
subject to $\sum_{j \in \mathcal{M_i}}\...
- 33
4
votes
2
answers
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
3
votes
1
answer
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}{...
- 39
1
vote
1
answer
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
0
answers
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
1
answer
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
6
votes
1
answer
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
5
votes
0
answers
77
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}^{'} | \...
- 615
2
votes
1
answer
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
4
votes
1
answer
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
6
votes
0
answers
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
3
votes
0
answers
68
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)
- 400