Download the files sample.dat: and m4n500s0.inp that contain data about timetabled trips housed in different depots.1 The name of the file indicates the number of depots (m), the number of trips (n) and finally the identifier of the instance (0,1,2,3,4). Trips are identified by numbers from m to n+m−1 and indexed by i that runs through the same range of numbers. The format of the files is as follows:
|
The instance sample.dat is a small toy instance used in class for the lecture that may be used for debugging or visualization purposes.
Download also the python script mdvs-template.py. It contains the function readData that reads the input data file and populates a list Ts with every arc. This list is used to build a tuplelist, which is a Gurobi sub-class. It then contains the code that implements the multi-depot model (24)–(28) of slide 35.
Capacity | 62, 59, 56, 56 | 45,45,45,45 | 20,20,20,20 |
Linear Programming lower bound | |||
Integer Optimal solution | |||
Number of vehicles used | |||
Number of depots used |
Tips:
model.addVar(vtype=GRB.BINARY) |
model.addVar(lb=0.0, ub=1.0, vtype=GRB.CONTINUOUS) |
Instead of solving a unique huge model, it is good practice to decompose a problem into smaller simpler subproblems. Download now the script lagrangian-template.py that contains elements to implement a Lagrangian relaxation approach. Consider the Lagrangian relaxation (29)–(32) of slide 37. Write a python function that solves Φh(λ), that is a function that solves a Min Cost Flow problem with the arc costs defined as a function of the h-th depot and of λ as in (37) in slide 40.
Once you a wrote such a script, use it to solve the subproblems and to compute a lower bound for the following values of vector λ:
Lower Bound | |
all elements equal to 100 | |
all elements equal to 1000 | |
elements are random real numbers from [0,1000] |
Are they all valid lower bounds? Can you devise a procedure to find the values for λ that give the greatest possible lower bound?
Tips: use the method: lagrangian_heuristic in lagrangian-template.py and complete it with the missing parts. You will need a model used earlier in this exercise.
Once the algorithm stops (there are no more negative reduced cost path), you can solve an Integer Linear problem defined only on the set of generated columns. How large is the gap from the LP solution and the integer solution?
Tips: To retrieve the dual multipliers αi and βh use the method model.getAttr("Pi", constraint), where constraint is a dictionary indexed over the constraints.