Hot answers tagged

17

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 structures to impose constraints on the dual space. They reduce the number of pricing iterations without compromising the complexity. Unfortunately, they are ...


9

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 supervised by our Marco Lübbecke) is mentioned on the About webpage for the Generic Column Generation (GCG) software. Compare with SCIP's VRP (tiny) example docs. ...


9

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}\\e(3)&=e(2)-d(3)+\eta\cdot c(2)\tag{3}\\e(4)&=e(3)-d(4)+\eta\cdot c(3)\tag{4}\\e(4)&=0.5\cdot E\tag{5}\end{align} You might like to use the same ...


8

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\times D_1 + \overline Y \times D_2 + E\times D_3\\\text{s.t.}&\quad D_1+D_3 \ge a\\&\quad D_2-\beta D_3 \ge b\\&\quad D_3 = 0\\&\quad D_1 \ge 0\\&...


7

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 described in the Claudio's answer). Penalty function approaches we tried have generally better performance than dual price smoothing. However, the former are ...


5

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$ of product $A$ by a small amount will reduce (increase) the total purchase quantity (TPQ to save me future typing) by $y_A$ times the change. The interpretation ...


4

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.t.} & x_{1}+x_{2} & \le1\\ & & x_{1} & \le1\\ & & x & \ge0 \end{alignat*} and the second is \begin{alignat*}{2} & \max &...


4

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 ... possibly only in one direction, or even for a zero step size in either direction, when degeneracy occurs, but still correct. I can't say why it's "not a larger ...


3

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 portion of the primal objective. You can rewrite the primal objective as \begin{gather*} \sum_{j=1}^{P}c_{j}x_{j}+P_{Dhd}\left[\sum_{i=1}^{F}\sum_{j=1}^{P}a_{ij}...


3

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 price. Non-convexities present in electricity market clearing models would lead to non-uniform prices, which would result in participants loosing money if no ...


2

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 \forall i=1,\ldots,n \\ & z_i \le 0 \quad \forall i=1,\ldots,n \end{align}$$ The dual formulation of the primal problem can be obtained by writing the ...


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