Hi all,

I have a general question related to the column generation implementation for vehicle routing problems in CPLEX:

While solving the master problem as an LP, is it advised to solve the set-covering version of the problem (with inequality constraints) than the set-packing version (with equality constraints)? In one of the tutorials on column generation (https://doi.org/10.1007/s10288-010-0130-z), it was argued that equality constraints in the master problem result in free dual variables which typically slow down the convergence of the column generation algorithm. Is this statement true in general for any column generation procedure? If yes, are there any sources for the same? Unfortunately, in our experiments, we are not seeing faster convergence of the column generation for the set covering version (keeping all other parameters the same), so I am curious about the technical details. Any insights are much appreciated.

Thanks
Venktesh

------------------------------
Venktesh Pandey
------------------------------

#DecisionOptimization

Think of a case where you start off with a dummy route that has high cost, a big M. This route visits all customers. Suppose further that there are 3 customers.
So, this column looks something like {M, 1, 1, 1} where the 1s indicate that this column features in the constraint on the number of visit for each customer respectively.
If you have discovered via column generation two other columns that are not dummy columns, say, {100, 1, 1, 0} and {100, 0, 1, 1}.

That is, the first of the routes above costs 100 and visits customers 1 and 2. The second of the route costs 100 and visits customers 2 and 3. If you only have equality constraints on the number of visits to customers, then you will notice that the dummy route will still feature in the primal basis. So, the primal objective function will continue to be M.

If you had >= constraint on the customer visits, you would probably have a primal objective function of 200 where each customer is visited atleast once and customer 2, in particular, is visited twice.

------------------------------
CPLEX User
------------------------------

Original Message:
Sent: Tue February 22, 2022 06:58 AM
From: Venktesh Pandey
Subject: Column generation implementation in CPLEX (equality vs inequality constraints)

Hi all,

I have a general question related to the column generation implementation for vehicle routing problems in CPLEX:

While solving the master problem as an LP, is it advised to solve the set-covering version of the problem (with inequality constraints) than the set-packing version (with equality constraints)? In one of the tutorials on column generation (https://doi.org/10.1007/s10288-010-0130-z), it was argued that equality constraints in the master problem result in free dual variables which typically slow down the convergence of the column generation algorithm. Is this statement true in general for any column generation procedure? If yes, are there any sources for the same? Unfortunately, in our experiments, we are not seeing faster convergence of the column generation for the set covering version (keeping all other parameters the same), so I am curious about the technical details. Any insights are much appreciated.

Thanks
Venktesh

------------------------------
Venktesh Pandey
------------------------------

#DecisionOptimization

Thank you for your response. Feasibility can be an issue as you pointed out when we are working with a subset of columns, but it does not explain why convergence rates would be affected. In our experiments, we started the restricted master with columns in which routes serve a single customer at a time, i.e., columns of the type {50,1,0,0}, {50,0,1,0}, and {50,0,0,1} and hence we do not face issues with discovering the optimal solution.

------------------------------
Venktesh Pandey
------------------------------

Original Message:
Sent: Tue February 22, 2022 08:14 PM
From: CPLEX User
Subject: Column generation implementation in CPLEX (equality vs inequality constraints)

Think of a case where you start off with a dummy route that has high cost, a big M. This route visits all customers. Suppose further that there are 3 customers.
So, this column looks something like {M, 1, 1, 1} where the 1s indicate that this column features in the constraint on the number of visit for each customer respectively.
If you have discovered via column generation two other columns that are not dummy columns, say, {100, 1, 1, 0} and {100, 0, 1, 1}.

That is, the first of the routes above costs 100 and visits customers 1 and 2. The second of the route costs 100 and visits customers 2 and 3. If you only have equality constraints on the number of visits to customers, then you will notice that the dummy route will still feature in the primal basis. So, the primal objective function will continue to be M.

If you had >= constraint on the customer visits, you would probably have a primal objective function of 200 where each customer is visited atleast once and customer 2, in particular, is visited twice.

------------------------------
CPLEX User

Original Message:
Sent: Tue February 22, 2022 06:58 AM
From: Venktesh Pandey
Subject: Column generation implementation in CPLEX (equality vs inequality constraints)

Hi all,

I have a general question related to the column generation implementation for vehicle routing problems in CPLEX:

While solving the master problem as an LP, is it advised to solve the set-covering version of the problem (with inequality constraints) than the set-packing version (with equality constraints)? In one of the tutorials on column generation (https://doi.org/10.1007/s10288-010-0130-z), it was argued that equality constraints in the master problem result in free dual variables which typically slow down the convergence of the column generation algorithm. Is this statement true in general for any column generation procedure? If yes, are there any sources for the same? Unfortunately, in our experiments, we are not seeing faster convergence of the column generation for the set covering version (keeping all other parameters the same), so I am curious about the technical details. Any insights are much appreciated.

Thanks
Venktesh

------------------------------
Venktesh Pandey
------------------------------

#DecisionOptimization