After careful inspection, I found that the scalar prod produced a huge huge acceleration. Before the model formulation itself used to take 0.5 hour, now it takes just 1.2 minutes.
Thanks a lot for redirecting me to this specific technique.
The next query is that :
Assuming I formulate this model, solve it, and get a reduced cost column from the SubProblem, how do I add this variable without reformulating the model entirely? Is there a function like AddCols(that is available in C) available in Python ? Do let me know, since in every iteration this would again save more time.
Thanks
Original Message:
Sent: 6/4/2024 11:05:00 AM
From: ALEX FLEISCHER
Subject: RE: CPLEX is taking a long time to formulate the model
Hi
have you tried the scalar product trick ?
And the add constraints in batch ?
regards
------------------------------
[Alex] [Fleischer]
[Data and AI Technical Sales]
[IBM]
------------------------------
Original Message:
Sent: Tue June 04, 2024 11:02 AM
From: HARIHARAN SUBRAMANIAN
Subject: CPLEX is taking a long time to formulate the model
I used the model.sum() instead of the usual python sum() which was suggested in the above notebook that you have posted. This led to slight improvement in times, but not too much.
Please do let me know if something else needs to be applied.
Thanks
------------------------------
HARIHARAN SUBRAMANIAN
Original Message:
Sent: Tue June 04, 2024 01:26 AM
From: ALEX FLEISCHER
Subject: CPLEX is taking a long time to formulate the model
Hi,
have you tried to follow the advice in the notebook
?
------------------------------
[Alex] [Fleischer]
[Data and AI Technical Sales]
[IBM]
Original Message:
Sent: Sat June 01, 2024 12:54 AM
From: HARIHARAN SUBRAMANIAN
Subject: CPLEX is taking a long time to formulate the model
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
------------------------------