Decomposition playgroundLaboratorio di decomposizione

The Lagrangian dual of a small integer program, and the same iterations seen in the primal: every cut of the dual is a column, i.e., an integer point of the subproblem, and the Dantzig-Wolfe point moves in the hull of the columns found so far.

Il duale lagrangiano di un piccolo problema intero, e le stesse iterazioni viste nel primale: ogni taglio del duale è una colonna, cioè un punto intero del sottoproblema, e il punto di Dantzig-Wolfe si muove nell'inviluppo delle colonne trovate finora.

Primal: the columns of the subproblem (its integer points, or a given finite set) and their hull, the coupling constraints (the shaded sides are infeasible), the columns generated so far and their hull, the Dantzig-Wolfe point ; the optima of the continuous relaxation (its region dotted), of the Lagrangian dual, i.e., over the hull , and of the integer problem : \(z_{\mathrm{LP}} \le z_{\mathrm{LD}} \le z_{\mathrm{IP}}\).Primale: le colonne del sottoproblema (i suoi punti interi, o un insieme finito dato) e il loro inviluppo, i vincoli accoppianti (i lati ombreggiati non sono ammissibili), le colonne generate finora e il loro inviluppo, il punto di Dantzig-Wolfe ; gli ottimi del rilassamento continuo (la sua regione punteggiata), del duale lagrangiano, cioè sull'inviluppo , e del problema intero : \(z_{\mathrm{LP}} \le z_{\mathrm{LD}} \le z_{\mathrm{IP}}\).

best \(L\)miglior \(L\)
\(z_{\mathrm{LP}}\)
\(z_{\mathrm{LD}} = \max L\)
\(z_{\mathrm{IP}}\)
statusstato