Regarding question 1, as far as I know the tolerance parameters apply to all algorithms, but I'm just a user. Perhaps someone from IBM knows more. I have no idea regarding the second question, so I'll have to defer to an IBMer for that one.
I do have a couple of questions. First, regarding scaling, did you try rescaling the source model yourself (rather than asking CPLEX to do it), perhaps by changing the units of some variables?
Second, when you add variables and constraints to one model to get the next one, do you also edit the final solution of the previous model to get a starting solution for the next model? I'm thinking of the functions IloCplex.setBasisStatuses() and IloCplex.SetStart() in the Java API. If, say, you are able to plug in values for the new columns so that the extended version of the previous solution is feasible in the new model, it might speed things up. I'm assuming that right now you are using advanced start based on the final basis of the previous model, which is not a complete basis for the new model.
Original Message:
Sent: Fri December 31, 2021 03:33 AM
From: Lukka D
Subject: which differences in these successive matrices causes a high increase in kappa (and runtime) in the second matrix?
Hi Prof Rubin
Thank you so much for your response.
a) tried using aggressive scaling and zeroing out small values in the second matrix, and solved using primopt, but still the runtime did not reduce (took 146 sec) and kappa was still high (kappa was still high at around 1e+13)
CPLEX Warning 1034: Detected 100.00% (1) unstable condition number(s) >= 1e+010.
Primal simplex - Optimal: Objective = 1.9509625578e+011
Solution time = 146.41 sec. Iterations = 82326 (69336)
Deterministic time = 49644.87 ticks (339.09 ticks/sec)
CPLEX> dis sol kappa
Condition number of basis = 3.1e+013
b) yes earlier also we had noticed that solving interior method (baropt) was much faster than primal when each "individual problem" is solved,
however we ran into severe performance problems when barrier is used in the application in the end to end solve (for these objectives). in fact barrier was much slower than primal in the end-to-end solve and it also became infeasible.
Had the following questions related to this
in our application we solve a series of LP problems matrices one after the other
The main concern is that some of the matrices take very long to solve
The application uses column generation to generate the matrices for a given objective
Some of the later objectives take a long time to solve, in some cases hours to solve one matrix.
In the application it currently uses advanced start with PRIMAL to solve the objectives, since this typically gives the best speedup
However for the later objectives advanced start with PRIMAL takes a very long time
Hence we tried to solve this using BARRIER, but we saw that while BARRIER may solve it faster, it does not seem to give a good starting point to the next iteration/matrix (though crossover is already on by default). Hence the next barrier solve has a very large infeasibiity.
Question1) after barrier optimization is finished, crossover starts, can Crossover refine the final solution to respect EPRHS and EPOPT tolerances? (currently we are using default for EPRHS and EPOPT tolerances, but still the starting point to the next iteration seems to be infeasible). What is the feasibility/optimality tolerance used by BARRIER after crossover? is it the same as EPRHS, EPOPT tolerances? is there any way to ensure that the starting point given to next barrier solve is feasible?
Question2) We see solver goes into re-solve with some matrix files while using Concurrent. What is the criteria when such re-solve is triggered ?
------------------------------
Lukka D
Original Message:
Sent: Thu December 30, 2021 04:06 PM
From: Paul Rubin
Subject: which differences in these successive matrices causes a high increase in kappa (and runtime) in the second matrix?
Not a direct answer, but is it possible for you to scale your data and variables better? Those 1048 warnings point to a possible source of numerical issues, and your right-hand side nonzeros range from around 5e-6 to around 8e+8 in the first model (1.55e+8 in the second, which is actually slightly better but still no cause for joy). Having 14 orders of magnitude difference seems to me to be an invitation for numerical problems.
Also, you might try solving with the interior point method ("baropt" command in the interactive solver). I ran both SAV files with CPLEX 20.1 on my desktop PC. Primal simplex produced slightly better but generally similar times to what you reported. The interior point solver (using four threads) was about 6x faster on the first problem and about 16x faster on the second one.
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Thu December 30, 2021 09:43 AM
From: Lukka D
Subject: which differences in these successive matrices causes a high increase in kappa (and runtime) in the second matrix?
Hi these uploaded two matrices are matrix1(SubProb_7-Obj_410-Master_1.SAV.gz) and matrix2 (SubProb_7-Obj_410-Master_2.SAV.gz).
===================================================================================
Here is what the datacheck 2 gives while solving the faster matrix 1 (SubProb_7-Obj_410-Master_1.SAV.gz)
===================================================================================
CPLEX> primopt
CPXPARAM_Read_DataCheck 2
CPXPARAM_Read_APIEncoding "UTF-8"
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T067' in constraint 'OUTMIN0177T067' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T068' in constraint 'OUTMIN0177T068' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T069' in constraint 'OUTMIN0177T069' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T070' in constraint 'OUTMIN0177T070' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T071' in constraint 'OUTMIN0177T071' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T072' in constraint 'OUTMIN0177T072' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T073' in constraint 'OUTMIN0177T073' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP023770T024' in lower bound looks like 3/100 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP011911T024' in upper bound looks like 29/100 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP079811T071' in constraint 'OUTMIN0177T071' looks like 4/71 in single precision.
CPLEX Warning 1036: Too many warnings of this type have been detected. All further warnings of this type will be ignored.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'CAP0009T077' are fractions and can be scaled with 48/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'CAP0115T077' are fractions and can be scaled with 75/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL025246T074' are fractions and can be scaled with 9/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL025246T075' are fractions and can be scaled with 9/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL047541T022' are fractions and can be scaled with 19/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL047541T023' are fractions and can be scaled with 19/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL063097T029' are fractions and can be scaled with 47/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL063097T043' are fractions and can be scaled with 47/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL063097T045' are fractions and can be scaled with 47/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL044004T023' are fractions and can be scaled with 7/1.
CPLEX Warning 1047: Too many warnings of this type have been detected. All further warnings of this type will be ignored.
CPLEX Warning 1048: Detected constraint with wide range of coefficients. In constraint 'CAP0055T008' the ratio of largest and smallest (in absolute value) coefficients is 1.81923e+008.
CPLEX Warning 1048: Detected constraint with wide range of coefficients. In constraint 'CAP0055T048' the ratio of largest and smallest (in absolute value) coefficients is 2.45641e+008.
================================================================================
===================================================================================
Here is what the datacheck 2 gives while solving the slower matrix 2 (SubProb_7-Obj_410-Master_2.SAV.gz)
================================================================================
CPLEX> primopt
CPXPARAM_Read_DataCheck 2
CPXPARAM_Read_APIEncoding "UTF-8"
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T067' in constraint 'OUTMIN0177T067' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T068' in constraint 'OUTMIN0177T068' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T069' in constraint 'OUTMIN0177T069' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T070' in constraint 'OUTMIN0177T070' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T071' in constraint 'OUTMIN0177T071' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T072' in constraint 'OUTMIN0177T072' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP128127T073' in constraint 'OUTMIN0177T073' looks like 4/71 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP023770T024' in lower bound looks like 3/100 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP011911T024' in upper bound looks like 29/100 in single precision.
CPLEX Warning 1036: Decimal part of coefficient for variable 'OP079811T071' in constraint 'OUTMIN0177T071' looks like 4/71 in single precision.
CPLEX Warning 1036: Too many warnings of this type have been detected. All further warnings of this type will be ignored.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'CAP0225T029' are fractions and can be scaled with 18/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'CAP0225T030' are fractions and can be scaled with 18/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'CAP0124T076' are fractions and can be scaled with 75/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'CAP0115T077' are fractions and can be scaled with 75/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL031703T039' are fractions and can be scaled with 24/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL031703T040' are fractions and can be scaled with 24/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL031703T041' are fractions and can be scaled with 24/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL031703T042' are fractions and can be scaled with 24/1.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL002386T027' are fractions and can be scaled with 31/50.
CPLEX Warning 1047: Decimal part of coefficients in constraint 'BAL002386T053' are fractions and can be scaled with 31/50.
CPLEX Warning 1047: Too many warnings of this type have been detected. All further warnings of this type will be ignored.
CPLEX Warning 1048: Detected constraint with wide range of coefficients. In constraint 'CAP0055T008' the ratio of largest and smallest (in absolute value) coefficients is 1.81923e+008.
CPLEX Warning 1048: Detected constraint with wide range of coefficients. In constraint 'CAP0055T048' the ratio of largest and smallest (in absolute value) coefficients is 2.45641e+008.
CPLEX Warning 1048: Detected constraint with wide range of coefficients. In constraint 'CAP0052T033' the ratio of largest and smallest (in absolute value) coefficients is 1.23607e+008.
CPLEX Warning 1048: Detected constraint with wide range of coefficients. In constraint 'CAP0052T035' the ratio of largest and smallest (in absolute value) coefficients is 1.89042e+008.
CPLEX Warning 1048: Detected constraint with wide range of coefficients. In constraint 'CAP0052T037' the ratio of largest and smallest (in absolute value) coefficients is 1.1201e+008.
The warnings seem similar, but still matrix2 has much higher kappa and takes longer to solve with more time solving infeasibilities.
Can you help identify what data elements between matrix2 and matrix1 cause matrix2 to have higher kappa and hence takes more time to solve?
------------------------------
Lukka D
Original Message:
Sent: Thu December 30, 2021 09:37 AM
From: Lukka D
Subject: which differences in these successive matrices causes a high increase in kappa (and runtime) in the second matrix?
Hi
We are trying to understand how to speed up CPLEX performance within our application.
In general it seems there is some correlation between slower runtimes for some matrices and ill-conditioning of matrices (larger kappa numbers).
The way the application works is by
a) solving the first matrix (e.g. SubProb_7-Obj_410-Master_1.SAV.gz) using "primopt"
b) based on the solution of the first matrix and based on the original problem, some new columns (and related constraints) are added to obtain the next matrix. (SubProb_7-Obj_410-Master_2.SAV.gz)
c) Next the second matrix (SubProb_7-Obj_410-Master_2.SAV.gz) is solved using "primopt"
and the process continues
It seems that the condition number (kappa) of the second matrix SubProb_7-Obj_410-Master_2.SAV.gz is much larger than the first matrix.
Can you help us understand which of the changes introduced in the second matrix causes the large increase in condition number (kappa)?
I am using cplex 12.7 (but the pattern can be replicated using higher versions as well i guess)
Steps to replicate
1) read SubProb_7-Obj_410-Master_1.SAV.gz
2) set read datacheck 2 to turn on modeling assistance
3) do primopt, it solves in around 4 sec with a kappa of around 1.0e+7
read SubProb_7-Obj_410-Master_1.SAV.gz
Warning: File contains basis. Basis is loaded.
Problem 'SubProb_7-Obj_410-Master_1.SAV.gz' read.
Read time = 0.06 sec. (2.32 ticks)
CPLEX> set read datacheck 2
New value for indicator to check data consistency: 2
CPLEX> primopt
CPXPARAM_Read_DataCheck 2
CPXPARAM_Read_APIEncoding "UTF-8"
Iteration: 10719 Objective = 42156028419.582680
Removing shift (21).
CPLEX Warning 1033: Detected 100.00% (1) suspicious condition number(s) >= 1e+007.
Primal simplex - Optimal: Objective = 4.2155721458e+010
Solution time = 3.61 sec. Iterations = 10850 (9991)
Deterministic time = 1942.98 ticks (538.22 ticks/sec)
CPLEX> dis sol kappa
Condition number of scaled basis = 7.3e+007
4) read in the second matrix SubProb_7-Obj_410-Master_2.SAV.gz and repeat the same steps as above
5) set read datacheck 2
6) do "primopt". Here it takes more time to solve scaled infeasibilities and finally finishes the solution in 135 seconds. The kappa is much larger 1e+10 (in some other box i saw kappa also becomes 1e+14 after solving this same matrix, not sure why the kappa value differs while solving the same matrix in different boxes)
Iteration: 89886 Objective = 195096257290.817990
Iteration: 90206 Objective = 195096255777.109040
Removing shift (317).
CPLEX Warning 1034: Detected 100.00% (1) unstable condition number(s) >= 1e+010.
Primal simplex - Optimal: Objective = 1.9509625578e+011
Solution time = 135.34 sec. Iterations = 90390 (77153)
Deterministic time = 46413.22 ticks (342.93 ticks/sec)
CPLEX> dis sol kappa
Condition number of scaled basis = 1.6e+010
This seems to indicate that
1) matrix1 (SubProb_7-Obj_410-Master_1.SAV.gz) is easier to solve, it is quicker (kappa is lower)
2) matrix 2 (SubProb_7-Obj_410-Master_2.SAV.gz) is a bit tougher to solve in comparison, kappa is higher > 1e+10)
We would like to identify what are the data elements in the second matrix that result in increase in kappa (and make the problem tougher to solve)
the main request is
1) can you help me identify which of the data elements in the second matrix are causing the high kappa number?. I tried the datacheck 2, but there are not many differences between the warnings given in matrix, so i did not get too much idea
2) is there any way to identify and delete the problematic data from matrix 2(SubProb_7-Obj_410-Master_2.SAV.gz), so that the condition number becomes better (back to the 1e+7 range as in matrix1 SubProb_7-Obj_410-Master_1.SAV.gz). ?
Is there any utility in interactive cplex that can identify and delete the suspected data elements so that we can confirm that deleting these suspected data elements can reduce ill-conditioning (kappa value) (make the problem easier to solve?
Is there any script that can be used to diff two matrices say (matrix2-matrix1) and then generate intermediate matrices e.g. matrix2-change1, matrix2-change2, matrix2-change3 etc etc, until we get original matrix1 by removing all the changes between matrix2 and matrix1?
alternatively can you recommend what approach (steps) to use to identify which set of data changes in going from matrix1 to matrix2 cause matrix2 to become numerically difficult to solve?
------------------------------
Lukka D
------------------------------
#DecisionOptimization