Originally posted by: SystemAdmin

Hi everybody,

I have used the MATLAB toolbox funtion cplexlsqbilp to solve my optimization model in CPLEX, but the results are somewhat unexpected.
In order to get more control over how CPLEX performs the calculations I am tying to customize some of the parameter settings for MIP which I think influence the solution.
Unfortunately some of the parameter settings seem not to be invoked when I run the model.

As I am new to CPLEX it would be appreciated if someone can help me understand why this happens and how can I change the parameters settings.

I am at this time primarily interested in changing the following parameters settings:

MIP dive strategy
MIP variable selection strategy
backtracking tolerance
MIP strategy best bound interval
MIP probing level
My MATLAB code for invoking the CPLEX solver is:

options = cplexoptimset(
'cplex'); options.diagnostics = 
'on'; options.mip.tolerances.mipgap=0; options.mip.tolerances.absmipgap=0; options.preprocessing.presolve = 0; options.mip.strategy.variableselect=3; % Does not seem to be invoked options.mip.strategy.backtrack=0.50;   % Does not seem to be invoked options.mip.strategy.probe=3;          % Does not seem to be invoked options.mip.strategy.dive=2;           % Does not seem to be invoked     [x,resnorm,residual,exitflag,output]=cplexlsqbilp(Obj,d,CONSTineq,bineq,CONSTeq,beq,[],[],[],options);

Basically I am trying to make the Branch-and-Cut algorithm of CPLEX less greedy, that is to make it more flexible.

Therefore I am wondering why are the above mentioned parameters settings not invoked and what should I do to be able to invoke them?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

How do you think these parameters are not used? Did you compare cplex log between with and without these parameters?
John Cui
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I compared the diagnostics log between simulations with and without parameters, and there was no change in results or computational time for the simulations. I'm not sure that is the same thing as the cplex log.

Here is how it looks for me:

Simulation 1

Solver Setup

options = cplexoptimset(
'cplex'); options.diagnostics = 
'on'; options.mip.tolerances.mipgap=0; options.mip.tolerances.absmipgap=0; options.preprocessing.presolve = 0; %options.mip.strategy.variableselect=3; % Does not seem to be invoked %options.mip.strategy.backtrack=0.50;   % Does not seem to be invoked %options.mip.strategy.probe=3;          % Does not seem to be invoked %options.mip.strategy.dive=2;           % Does not seem to be invoked     [x,resnorm,residual,exitflag,output]=cplexlsqbilp(Obj,d,CONSTineq,bineq,CONSTeq,beq,[],[],[],options);

Diagnostics Log

Number of nonzeros in lower triangle of Q = 159758 Using Approximate Minimum Degree ordering Total time 

for automatic ordering = 0.02 sec. Summary statistics 

for factor of Q: Rows in Factor            = 832 Integer space required    = 1248 Total non-zeros in factor = 160590 Total FP ops to factor    = 40636142 Clique table members: 208. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 2 threads. Root relaxation solution time =    0.14 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap   *     0     0      integral     0       -0.0000       -0.0000       11    0.00% Elapsed real time =   0.20 sec. (tree size =  0.00 MB, solutions = 1)   Root node processing (before b&c): Real time             =    0.17 Parallel b&c, 2 threads: Real time             =    0.00 Sync time (average)   =    0.00 Wait time (average)   =    0.00 ------- Total (root+branch&cut) =    0.17 sec.

Simulation 2

Solver Setup

options = cplexoptimset(
'cplex'); options.diagnostics = 
'on'; options.mip.tolerances.mipgap=0; options.mip.tolerances.absmipgap=0; options.preprocessing.presolve = 0; options.mip.strategy.variableselect=3; % Does not seem to be invoked options.mip.strategy.backtrack=0.50;   % Does not seem to be invoked options.mip.strategy.probe=3;          % Does not seem to be invoked options.mip.strategy.dive=2;           % Does not seem to be invoked   [x,resnorm,residual,exitflag,output]=cplexlsqbilp(Obj,d,CONSTineq,bineq,CONSTeq,beq,[],[],[],options);

Diagnostics Log

Number of nonzeros in lower triangle of Q = 116229 Using Approximate Minimum Degree ordering Total time 

for automatic ordering = 0.02 sec. Summary statistics 

for factor of Q: Rows in Factor            = 516 Integer space required    = 774 Total non-zeros in factor = 116745 Total FP ops to factor    = 33032471 Probing time =    0.00 sec. Clique table members: 129. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 2 threads. Root relaxation solution time =    0.09 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap   *     0     0      integral     0 -0.0000       -0.0000       11    0.00% Elapsed real time =   0.20 sec. (tree size =  0.00 MB, solutions = 1)   Root node processing (before b&c): Real time             =    0.17 Parallel b&c, 2 threads: Real time             =    0.00 Sync time (average)   =    0.00 Wait time (average)   =    0.00 ------- Total (root+branch&cut) =    0.17 sec.

In both cases it takes equal amount of iterations (11) for the algorithm to reach the solution.

I found a way to see the options input for CPLEX and it seems that the parameters are being invoked but still it looks like they don't affect the optimization.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Eumpfenbach

Look at your solution output. Cplex solved the problem in the root node. No need for "probing" or "diving" if it solves at the root.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Okej, if that is the case then I am even more puzzled at what the MIP solver in CPLEX does.

The optimization problem above contains 129 binary design variables and a total of 633 constraints of which, 133 are equality constraints and 500 inequality constraints. From my point of view this is not a small optimization problem and therefor it seems unfeasible that a solution is found at the root node.

Do you have any idea or tips of what the issue is? Maybe it is my optimization model that is badly constructed or some default setting in CPLEX that is the issue?

I appreciate any and all ideas and tips I can get.

Regards
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

You have run into a very lucky case: The LP relaxation of your problem is integral. At the root node CPLEX solves the LP relaxation of your model (the LP relaxation is the same model but with all integrality constraints dropped). It turns out that the solution that CPLEX finds for this relaxation happens to satisfy all integrality constraints. So the solution for the relaxation is actually a solution for the original model and the optimal solution is found.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you for your response,

but can you please expand on what you mean with "The LP relaxation of your problem is integral"?

Also I have noticed that the results I get are quite different depending on if

options.preprocessing.presolve

is turned on or off. Despite the presolve is turned off, there is a "QP Presolve" that is performed at the root node when I am using the Barrier algorithm for the relaxation. Why is this being performed and can it be turned off?
At least for my problem it seems that the "residuals" and "resnorm" of the objective function are a lot smaller when the presolve option is turned off.

The diagnostics output looks as follows:

Number of nonzeros in lower triangle of Q = 116229 Using Approximate Minimum Degree ordering Total time 

for automatic ordering = 0.00 sec. Summary statistics 

for factor of Q: Rows in Factor            = 516 Integer space required    = 774 Total non-zeros in factor = 116745 Total FP ops to factor    = 33032471 Clique table members: 129. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 2 threads. Number of nonzeros in lower triangle of Q = 116229 Using Approximate Minimum Degree ordering Total time 

for automatic ordering = 0.00 sec. Summary statistics 

for factor of Q: Rows in Factor            = 516 Integer space required    = 774 Total non-zeros in factor = 116745 Total FP ops to factor    = 33032471 Tried aggregator 1 time. QP Presolve eliminated 126 rows and 129 columns. Number of nonzeros in lower triangle of Q = 74691 Using Approximate Minimum Degree ordering Total time 

for automatic ordering = 0.01 sec. Summary statistics 

for factor of Q: Rows in Factor            = 387 Integer space required    = 387 Total non-zeros in factor = 75078 Total FP ops to factor    = 19395150 Reduced QP has 507 rows, 387 columns, and 2649 nonzeros. Reduced QP objective Q matrix has 149769 nonzeros. Presolve time =    0.05 sec. Tried aggregator 1 time. QP Presolve eliminated 384 rows and 384 columns. Reduced QP has 510 rows, 390 columns, and 3426 nonzeros. Reduced QP objective Q matrix has 3 nonzeros. Presolve time =    0.00 sec. Parallel mode: using up to 2 threads 

for barrier. Number of nonzeros in lower triangle of A*A
' = 5253 Using Approximate Minimum Degree ordering Total time 

for automatic ordering = 0.00 sec. Summary statistics 

for Cholesky factor: Threads                   = 2 Rows in Factor            = 510 Integer space required    = 1608 Total non-zeros in factor = 14149 Total FP ops to factor    = 415905 Itn      Primal Obj        Dual Obj  Prim Inf Upper Inf  Dual Inf 0 -5.5779707e-005 -3.8700000e+005 2.70e+005 6.93e+004 3.75e+005 1 -1.9141306e-006 -1.1785117e+006 6.28e+003 1.61e+003 8.71e+003 2 -7.4258802e-007 -5.1857830e+005 5.19e+002 1.33e+002 7.20e+002 3 -6.4007602e-007 -3.8009154e+004 1.59e+001 4.06e+000 2.20e+001 4 -6.3687530e-007 -4.9518484e+002 1.51e-001 3.88e-002 2.10e-001 5 -6.3684467e-007 -2.7793110e+000 7.17e-004 1.84e-004 9.95e-004 6 -6.3684458e-007 -1.5341056e-002 3.34e-006 8.55e-007 4.63e-006 7 -6.3684468e-007 -8.4497371e-005 1.54e-008 3.93e-009 2.13e-008 8 -6.3685220e-007 -1.1818169e-006 8.66e-011 2.22e-011 1.20e-010 9 -6.3705106e-007 -6.6339043e-007 4.20e-012 1.05e-012 5.67e-012 10 -6.3706209e-007 -6.3799346e-007 3.11e-012 3.69e-014 1.96e-013 11 -6.3706938e-007 -6.3714775e-007 3.07e-012 1.07e-014 1.56e-014   Total time on 2 threads =    0.03 sec. Barrier time =    0.08 sec.   QP crossover. Primal and Dual:  Fixing 256 variables. Primal:  Pushed 184, exchanged 72. Dual  :  Pushed 0, exchanged 72. Removing shift (1). Total crossover time =    0.05 sec.   Total time on 2 threads =    0.12 sec. Root relaxation solution time =    0.12 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap   *     0     0      integral     0       -0.0000       -0.0000       11    0.00% Elapsed real time =   0.17 sec. (tree size =  0.00 MB, solutions = 1)   Root node processing (before b&c): Real time             =    0.16 Parallel b&c, 2 threads: Real time             =    0.00 Sync time (average)   =    0.00 Wait time (average)   =    0.00 ------- Total (root+branch&cut) =    0.16 sec.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi,

I have run into a new problem while using cplexlsqbilp toolbox function in MATLAB which is a bit off-topic, but I did not want to start a new thread so I am posting it here.

I have tried to use my model to solve a problem but what ever I do it does help, and I still get the same message back.

This is how I initiate cplexlsqbilp in my model:

%% Bound and Cut solver   options = cplexoptimset(
'cplex'); options.diagnostics = 
'on'; options.mip.tolerances.mipgap=0; options.mip.tolerances.absmipgap=0; options.preprocessing.presolve = 0; options.mip.strategy.startalgorithm=4; %Barrier algorithm 

for root node relaxation options.mip.strategy.subalgorithm=4;    %Barrier algorithm 

for subproblem solution   [x,resnorm,residual,exitflag,output]=cplexlsqbilp(Obj,d,CONSTineq,bineq,CONSTeq,beq,[],[],[],options);

And this is the output and subsequent error message:

Number of nonzeros in lower triangle of Q = 356002 Using Approximate Minimum Degree ordering Total time 

for automatic ordering = 0.00 sec. Summary statistics 

for factor of Q: Rows in Factor            = 2640 Integer space required    = 3960 Total non-zeros in factor = 358642 Total FP ops to factor    = 69184986 Clique table members: 730. MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 2 threads. Root relaxation solution time =    0.28 sec.   Nodes                                         Cuts/  Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap   0     0    infeasible                                          0   Root node processing (before b&c): Real time             =    0.36 Parallel b&c, 2 threads: Real time             =    0.00 Sync time (average)   =    0.00 Wait time (average)   =    0.00 ------- Total (root+branch&cut) =    0.36 sec.

??? Error using ==> cplexlsqbilp at 264
Inner matrix dimensions must agree.

Error in ==> Model_sparse at 193
x,resnorm,residual,exitflag,output]=cplexlsqbilp(Obj,d,CONSTineq,bineq,CONSTeq,beq,[,],[,options);

As the model contains quite a large number of design variables and constraints I am using sparse matrices to initiate Obj,d,CONSTineq,bineq,CONSTeq,beq. The sizes of the matrices and vectors are as follows:
Obj=(40x2640), d=(40x1)
CONSTineq=(2480x2640), bineq=(2480x1)
CONSTeq=(1172x2640), beq=(1172x1)
My question is,

what does the error messages mean and what can I do make cplexlsqbilp solve my problem?
Kind regards
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: John Cui

Looks like your model is infeasible, so you need to check your model or data.

You have 2 approaches to debug:
1. set options.exportmodel = 'debug.sav', then use cplex interactive to debug the model file.
2. switch from cplexlsqbilp to Cplex class, then use methods in Cplex class to debug your model.
John Cui
#CPLEXOptimizers
#DecisionOptimization