Hot answers tagged

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 ...
user avatar
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 ...
user avatar
  • 2,052
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}\\...
user avatar
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\...
user avatar
  • 8,350
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 ...
user avatar
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$ ...
user avatar
  • 31.1k
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....
user avatar
  • 31.1k
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 ... ...
user avatar
  • 31.1k
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 ...
user avatar
  • 31.1k
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 ...
user avatar
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 ...
user avatar
  • 22.7k
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 \...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible