17
votes
Accepted
Column generation stabilisation
Stabilization methods are tricky. Dual optimal inequalities are you best chance to obtain significant speed ups. Basically they prevent a bunch of useless dual values by exploiting problem-specific ...
- 1,549
9
votes
Column generation stabilisation
Has anyone performed a benchmark of the various stabilization techniques in column generation? ... implemented in SCIP ...
The thesis "Generic Branch-Cut-and-Price" (.PDF), by Gerald Gamrath (and ...
- 2,098
9
votes
Accepted
Dual variables associated with same equation for different time instants
You do not have $3$ constraints, you have $T$ constraints.
For example, if $T=5$, then we have
\begin{align}e(1)&=e(0)-d(1)+\eta\cdot c(0)\tag{1}\\e(2)&=e(1)-d(2)+\eta\cdot c(1)\tag{2}\\...
- 912
8
votes
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\...
- 8,622
7
votes
Column generation stabilisation
In our JOC paper (Pessoa et al.) mentioned by Claudio, we have performed comparison (on 9 different problems including VRP) between some penalty function approaches and dual price smoothing (both are ...
- 1,394
5
votes
Accepted
Physical Interpretation of a dual of an LP
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$ ...
- 37.8k
4
votes
Is optimal solution to dual not unique if optimal solution to the primal is degenerate?
If I understand your question correctly, I think you can find your answer by considering the following two primal problems. The first is
\begin{alignat*}{2}
& \max & x_{1}\\
& \textrm{s....
- 37.8k
4
votes
Accepted
Derive "true" shadow price for degenerated LPs using commercial solvers (e.g. Gurobi)
I find the phrase "true shadow prices" misleading, and the use of "falsified" even more so, since the shadow prices any reputable solver returns are valid shadow prices ... ...
- 37.8k
3
votes
Accepted
On dual-formulation of a given primal for a set-covering problem
It does not look correct, and in particular the dual of an LP is an LP, so it makes no sense to have a binary variable in the dual. I suspect what led you astray was a misunderstanding of the penalty ...
- 37.8k
3
votes
Accepted
Electricity market clearing price using fixed-MIP formulation?
I've gained sufficient information in last couple of weeks to write an answer myself.
As a prerequisite to the discussion, please note the difference between uniform vs non-uniform market clearing ...
- 189
3
votes
Accepted
Termination criterion for the Phase 1 algorithm in column generation
The termination criterion is the same because the primal objective value is $0$ if and only if the dual objective value is $0$.
Your dual formulation is almost correct, but you are missing $a$ and $b$ ...
- 30.4k
3
votes
Accepted
Help with dual of a problem
Looks almost correct to me. Two issues:
Your $ \le$ dual constraints suggest that you omitted $X_a \ge 0$ in the primal. If instead $X_a$ is free, then your dual constraints should be $=$.
Your ...
- 30.4k
2
votes
CPLEX stuck in solve method - dual simplex solved model
You are solving a MIP not just an LP. Dual simplex solves the LP relaxation of the MIP. After that, the branch and cut process starts. That will usually take even more time than solving the root node/...
- 6,352
2
votes
Accepted
Developing the dual model
Your first dual constraint is wrong. The term $(1-\lambda)\times y^1$ should be included in the left side of the second dual constraint.
- 37.8k
2
votes
Accepted
Finding the dual problem of a minimum problem
Primal Problem
$$\begin{align}
\text{minimize} \quad & \sum_{i=1}^n a_i x_i + \sum_{i=1}^n b_i z_i \\\
\text{subject to} \quad & A\mathbf x-\mathbf d \le C\mathbf z \\
& x_i \ge 0 \quad \...
- 365
1
vote
Accepted
The dual values and change in the variables values
Let $\bar{A}$ and $\bar{x}$ be $A$ and $x$ augmented by slack variables, so that the constraints become $\bar{A} \bar{x} = b.$ The LP solution partitions $\bar{A} = [B N]$ (after permuting columns if ...
- 37.8k
1
vote
Accepted
Understanding reduced costs and dual values
One of the best possible ways for the models with some difficulties to understand how the model can be treating in the solving process, specifically in the situations like infeasibility, comparing ...
- 8,390
Only top scored, non community-wiki answers of a minimum length are eligible