When one is interested in solving a problem but considering different objective functions the choice is easy, a class for problem, a class for solution and a class by algorithm then in the main function (or file) we just need to call the appropriate one. The reason for that is that the different problems has the same feasible region thus they can share a common problem and solution classes

What to do in the case of having a problem and I need to do the following :

  • solve it

  • find an bound using a relaxation (Lagrangian for instance)

  • find an bound using a reformulation (Dantzig-Wolfe and column generation).

What is the best idea to structure the code ?


It depends on how you choose to solve your master and slave problems (for your Lagrangian and Dantzig-Wolfe decompositions). Theoretically, you can solve everything with linear programs. In this case your usual favorite structures and classes can be used as is.

If you are using a package such as PuLP (python), you have a class for the problem (pulp.LpProblem), and you solve it by calling your favorite available solver with the pulp.LpProblem.solve() command.

Now, for the two other options (Lagrange and Dantzig-Wolfe), you can exploit the fact that they both require master and slave problems. In fact, the slave problems are identical, and the master problems are duals of one another. This is something that I would take advantage of.

Column generation and Lagrangian relaxation have the following pseudo-code :

Initialize your set of variables V
Initialize the "continue" parameter to True
While continue is True :
   relaxed_objective, duals = MasterProblem(V)
   v, continue = SlaveProblem(duals)
   if v has negative reduced cost (for minimization problem) :
      Add v to V
   else :
      continue = False

Again, the slave problems are identical so a same class can be used. Depending on how you solve your slave problem, you might need an appropriate class. If you are solving it as a linear problem, the pulp.LpProblem class works.

As for the Master problem, for column generation, it is a linear problem, so in terms of PuLP it falls in the pulp.LpProblem class as well. As for Lagrange, it depends on how you choose to tackle it. Since it is the dual of Dantzig's formulation, you can, again, use the pulp.LpProblem class (or any other problem class if you are using another package). If you choose to solve it with a sub-gradient method, you would need an ad hoc class.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.