Originally posted by: fel85

Dear all,
I created a VNS for a MIP project scheduling and staffing (min)-problem. Therefore I splitted the problem in a binary (determine project -start points with the VNS) and a Linear-Problem (staffing-problem). I use the Java API of Cplex to solve/evaluate the LP-models. For the initial solution I save all constraints of the Linear-Model which are related to the project start points in an array and solve the initial model to get the initial-solution quality. After applying a neighborhood function (for example change the start point of project X for one period) I remove the constraints from the initial LP, which are related to the project start period of project X (the constraints are stored in the array). Afterward I add the new constraints to the LP-model. Then I solve the model to get the quality of the first neighborhood change. Then I apply the neighborhood function again and again and evaluate the qualities as mentioned above.
Removing and adding the 36 constraints lasts 1200 ms. (building a new model from scratch is just a little bit slower). Solving the model lasts additionally 1000ms. So, altogether one solution evaluation lasts more than two seconds. The LP has 2,980 columns and 884,000 rows. Solving the MIP to optimality with CPLEX MIP-Solver with the default parameter settings lasts only 20 seconds. So my questions are:
Is 1200ms an appropriate time to remove and add 36 constraints to the model?
Is 1000ms an appropriate time to solve a model with 2,980 columns and 884,000 rows?
Do you have any ideas to remove / add constraints remarkably faster?
Do you have any ideas to improve the solving time of the model?
Thank you very much for your help!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> fel85 wrote:
> Is 1200ms an appropriate time to remove and add 36 constraints to the model?

Depends. Are you using an abacus or a Beowulf cluster?

> Is 1000ms an appropriate time to solve a model with 2,980 columns and 884,000 rows?

A prime determinant of performance is the number of nonzeros.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: fel85

Thank you Paul for your response,
my “abacus”-machine ;-) has an Intel (R) Core (TM) i5 CPU 760@2.8 GHz processor with 4GB of RAM.
I know that the performance depends on the machine I use.
I would like to know if there exists a more efficient way to remove / add constraints. Thereby I hope that I can decrease the removing and adding time on my machine for example by a factor of ten (from 1200ms to 120ms).
My LP has:
2,980 columns, 884,000 rows and 1,023,936 nonzeros.
The reduced LP has:
1,694 columns, 8374 rows and 16,166 nonzeros.
Thank you very much for your help!
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> fel85 wrote:
> My LP has:
> 2,980 columns, 884,000 rows and 1,023,936 nonzeros.
> The reduced LP has:
> 1,694 columns, 8374 rows and 16,166 nonzeros.

I may be a bit lost here. Is the "reduced LP" the first LP after CPLEX is done presolving it, or are we talking about two distinct LPs here? If it is the presolved LP, then somewhere near 90% of your constraints are redundant, and a reasonable place to start would be trying to figure out if there is an easy way to recognize the redundant ones and not include them in the first place. If these are two distinct LPs, never mind.

How do you remove constraints? Are you using IloMPModeler.remove()?

In the C++ API, model (IloModel) and solver object (IloCplex) are separate objects, and IIRC removing model objects goes faster if you first kill the extracted solver object. In the Java, API, model and solver are essentially one object (IloCplex), and I'm not sure whether that makes model changes slower in Java than in C++ (or whether CPLEX automatically kills and reextracts the solver instance when it sees the model being tweaked).

My impression is that when a significant portion of a model is being changed, it seems to be faster to delete the model entirely and rebuild from scratch.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Is the time spent in the calls to add() and remove() or is the time spent in actually setting up the constraints?
It might be worth trying to formulate the constraints using an instance of IloLPMatrix instead of an array of ranges. That might be a little faster.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: fel85

Thank you Paul and Daniel for your responses!
I fixed the problem using a tighter formulation of the lp.
Hence the solving and modifying time is reduced to approximately 400ms.
Thanks
#CPLEXOptimizers
#DecisionOptimization