Recently, I have been working on Dantzig-Wolfe(DW) decomposition technique. I found enough online resources that show worked-out examples of how to solve linear problems using the DW method. But I did not find any resource which explains solving MILP/IP with a numerical example of DW method. Can anyone provide me with any article/link of a clear numerical example of the DW method for MILP/IP?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ More specifically, I am looking for a simple formulation of DW decomposition (and a numerical example) for the MILP problem. Just like Bender's decomposition. In benders decomposition, we can separate the master problem (containing integer variables) and subproblem (containing continuous variables) and then iteratively solve it. $\endgroup$– Fouad HasanCommented Dec 6, 2022 at 0:27
-
$\begingroup$ Hey have you find any example through which we can solve MILP by DW method? Then please share. Or we can't solve MILP through DW method. $\endgroup$– Maths_hawkCommented Feb 25 at 4:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
A nice example ("SpongeRollProblem") is provided in the PuLP Github repo, which is just a classical cutting stock problem.
Different variations are implemented, which helps understanding the mechanics:
- SpongeRollProblem1 and SpongeRollProblem2 are a decomposed version, where patterns (columns) are given beforehand as part of the data.
- SpongeRollProblem3 and SpongeRollProblem4 are a decomposed version, where patterns (columns) are computed beforehand.
- SpongeRollProblem5 and SpongeRollProblem6 are a decomposed version, where patterns (columns) are computed dynamically with a column generation approach. I suggest starting with SpongeRollProblem5, SpongeRollProblem6 is a just a columnwise implementation for more efficiency, but it may be a little harder to grasp if column generation is new to you.
In these examples, you are dealing with a MIP, and the way the integral solution is obtained is simply by solving the restricted master problem with integer variables (price-and-branch). This does not guarantee optimality (unless you have generated all possible columns). Dippy is an extension of PuLP which can do the branch-and-price (the column generation procedure for solving the linear relaxation, embedded in a branch-and-bound framework) for you, but it is kind of a black box for users (the code is open source, but hard to understand).
Note that the DW method refers to the formulation. It is typically combined with column generation, but these are two different concepts. Column generation is the algorithm which dynamically generates the variables of the linear relaxation of the DW formulation.
-
$\begingroup$ If I understand well, the question is about how to get integral solutions from the linear relaxation computed by column generation $\endgroup$– fontanfCommented Dec 4, 2022 at 11:24
-
$\begingroup$ yeah i think you are right. I have added a paragraph to clarify. $\endgroup$– KuifjeCommented Dec 4, 2022 at 12:02
-
$\begingroup$ public.tepper.cmu.edu/jnh/bendersTutorialCork.pdf This reference (slide 41) says that DW method can only be applied to linear programming. Does that mean we can not solve the Mixed integer problem using DW method? $\endgroup$ Commented Dec 22, 2022 at 2:52
-
$\begingroup$ It is possible that the author includes "integer variables" in the term linear. But even assuming this, I believe the statement is overly restrictive, as the subproblem in a DW formulation can be non linear. I think that what the author means is that the master problem has to be linear. $\endgroup$– KuifjeCommented Dec 22, 2022 at 11:03