Design choices on how to implement several algorithms for the same problem

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) :