CapacitatedVehicleRouting demo utilization problem

[ysu1028]

Hello,

I'm implementing the dial-a-ride problem using pricing callbacks to generate a new entering column in the master problem and I'm referring to your work of CapacitatedVehicleRouting demo:https://github.com/atoptima/ColunaDemos.jl/tree/master/src/CapacitatedVehicleRouting

I'm confused about:

1. how to make the master problem and subproblem being iteratively solved using callback?
2. should I feed the model.jl with the initial solution?
3. from model.jl, I can only get the defined cvrp model, x (variables), and decomposed model, how can I use the code to obtain the results? I'm quite confused about the whole process...

If there is a small example for the implementation of the pricing callback that could be very helpful!

the status of my packages:
Gurobi v.0.8.1
JuMP v.0.21.4
MathOptInterface v0.9.20
BlockDecomposition v1.2.5

Thank you in advance!

Best,
Yue

[guimarqu]

Hi,

You have documentation about the pricing callback here : https://atoptima.github.io/Coluna.jl/latest/user/callbacks/#Pricing-callback . The example should work.

1. The master problem must be solved using a (MI)LP solver. You can solve pricing problems using a pricing callback. You have to define the callback and use the method specify!.
2. You don't have to feed the model with an initial solution because the master formulation has artificial variables. So column generation starts with a kind of phase 1.
3. You can optimize the model and retrieves the value of the variables like you would do with any JuMP model. The solution of the master formulation is automatically projected to the original formulation.

[ysu1028]

3. The solution of the master formulation is automatically projected to the original formulation.

Thank you so much for your fast and detailed reply!

I also referred to https://github.com/atoptima/Coluna.jl/issues/404. Now the cvrp demo can run on my computer :)
I use coluna to be the optimizer which is defined as:

coluna = optimizer_with_attributes(
Coluna.Optimizer,
"params" => Coluna.Params(
solver = Coluna.Algorithm.TreeSearchAlgorithm() # default BCP
),
"default_optimizer" => Gurobi.Optimizer # Gurobi for the master & the subproblems
)

two points that are still not clear for me:

1. Coluna.Algorithm.TreeSearchAlgorithm() is used to solve both the master problem and pricing sub-problem?

2. by using the method specify! which in this case is:
   specify!(subproblems[1], lower_multiplicity = 0, upper_multiplicity = 20, solver = route_pricing_callback)
   we actually replace the solver = Coluna.Algorithm.TreeSearchAlgorithm() with route_pricing_callback, right? so if question 1 is yes, the master problem will also be solved by route_pricing_callback? Or it will only change the method for solving the subproblem and the master problem will still be solved by Coluna.Algorithm.TreeSearchAlgorithm()?

Thank you very much for your time and efforts! Your reply will definitely help me a lot!

Best,
Yue

[guimarqu]

1. TreeSearchAlgorithm solves the master IP. The subsolver (defined using default_optimizer parameter or by assigning a solver to the master using specify!) solves the master LP and the restricted master IP if you use restricted master heuristic.

specify!(subproblems[1], lower_multiplicity = 0, upper_multiplicity = 20, solver = route_pricing_callback)

the first subproblem will be solved using the pricing callback route_pricing_callback. Other subproblems and the master are solved by the MILP solver defined in default_optimizer.

[ysu1028]

specify!(subproblems[1], lower_multiplicity = 0, upper_multiplicity = 20, solver = route_pricing_callback)

Thank you very much for the reply!

It cannot be more clear!

Best,
Yue