Hello,
So I am having a model with 1000 constraints, but with 200K variables. The problem is a set covering problem. All variables are binary. The problem is solved as a linear program. This is basically a column generation problem.
The 200K variables refer to the initial 200K columns needed to ensure initial feasibility.
Now, when I add the constraints using Python + DoCPLEX, in the following manner:
for i in range(len(legs)):
# print("I am currently adding constraint = ",i)
airline_cp_model.add_constraint(airline_cp_model.sum(coverage_matrix[i][j]*x[j] for j in range(len(pg.pairings))) >= 1, 'airline')
Note that len(legs) = 1000. len(pg.pairings) = 200,000
Now, to formulate this model, i.e especially for all the constraints to be added it takes approximately more than 10-15 Mins. This 15 mins is especially consumed just for, adding the constraints. The variable creation, setting of the objective function and other things are done quite fast, but the addition of constraints takes too much time.
Q1. How do I quicken this up? Is there maybe a way I can feed the matrix(A) and RHS vector(B) of Ax >= B and get this done faster?
Q2. Assuming say, I am fine with spending 15 mins on the model formulation as a one-time initial cost. But, during Column Generation(CG), we generate variables from the pricing subproblem. Now, say if I get 1 variable, it is nothing but a column. Right now, I add this column to each constraint and create the model from "Scratch" at every CG iteration i.e when a variable is added.
To give an example:
Let the constraints look like the below in the CG iteration i as follows:
0x1 + 1x2 + 0x3 >=1
0x1 + 0x2 + 1x3 >=1
Now say another variable enters into CG iteration i+1 and the constraints become as follows:
0x1 + 1x2 + 0x3 + 1x4>=1
0x1 + 0x2 + 1x3 + 1x4>=1
To achieve the above : I do it in the following way in a rough manner:
Create a totally new blank fresh model
Add n+1 = 3+1 = 4 variables
The coverage_matrix had 1000 rows and 200,000 columns. Now it shall have 1000 rows and 200,001 columns.
i.e len(legs) =1000(not changed), but len(pg.pairings) = 200,001 which has increased by 1.
This means I will do the exact above part i.e
"""
for i in range(len(legs)):
# print("I am currently adding constraint = ",i)
airline_cp_model.add_constraint(airline_cp_model.sum(coverage_matrix[i][j]*x[j] for j in range(len(pg.pairings))) >= 1, 'airline')
"""
Again...
Then I will resolve the model with the added variable.
Now this becomes prohibitively slower due to readdition of 200,001 constraints again and again.
Now it seems there is an addcols method in CPLEX+C. But is there a similar method in doCPLEX. If yes, do mention the method with a simple example. If not, do let me know how to resolve the above problem.
------------------------------
HARIHARAN SUBRAMANIAN
------------------------------