Originally posted by: Pan_Greece

Hi,

I have a Mixed Integer Quadratically Constrainted Quadratic problem and I use CPLEX with Matlab

Some months ago I faced a problem (related to multiple quadratic constraints) and with your help, which I really appreciate, I solved it.

Briefly, it is a large scale optimization problem where the number of the variables are more than 1200 (some of them time-related) and the number of the quadratic constraints more than 70!

The problem I face is related to integer infeasibility since I get this output:

"Presolve time = 0.03 sec. (1.43 ticks)

x =

     []

fval =

     []

exitflag =

    -2

output =

          cplexstatus: 103

    cplexstatusstring: 'integer infeasible'

           iterations: 0

            algorithm: 12

                 time: 0.0460

              message: 'No feasible point was found.'

But this does not happen all the times but only when I change some parameters more than a specific value…there is no rationale behind all this….The strange is that no matter what the output message says, it does exists at least one feasible solution…When I put the lower bound matrix equal to the upper bound matrix equal to a simple solution, I get the following output:

Tried aggregator 1 time.

MIQCP Presolve eliminated 4721 rows and 1296 columns.

All rows and columns eliminated.

Presolve time = 0.08 sec. (7.54 ticks)

 

x =

         0

         0

         0

         0

         0

         0

         0

   -0.0000

   -0.0109

   -0.0331

   -0.0488

   -0.0568

      -----

      -----

        0

         0

         0

         0

         0

         0

         0

         0

         0

 

 

fval =

   -0.5676

 

exitflag =

     1

 

output =

          cplexstatus: 101

    cplexstatusstring: 'integer optimal solution'

           iterations: 0

            algorithm: 12

                 time: 0.1090

              message: 'Function converged to a solution x.'

 

So,  is there something I can do?

Is there a way to find which bound or constraint is the reason of the "infeasibility"?

But if there is not a feasible solution, how I have found at least a solution which leads the problem to solve it?

 

Thanks in advance

 

 

#CPLEXOptimizers
#DecisionOptimization

With the toolbox functions there is not much you can do to investigate infeasibility. You should switch over to the class API. The class API provides several functions to analyze infeasible problems: feasOpt() computes a minimal relaxation of your problem that is feasible and refineConflict() finds the conflicting constraints.

If CPLEX reports "infeasible" but you know a feasible solution and CPLEX actually accepts this feasible solution then bad numerics may be involved. In that case you can try to switch on the "numerical precision emphasis" parameter.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Pan_Greece

Thanks Daniel for your qiuck reply,

 

Unfortunately, I started formulating the problem in pure Matlab and now it is too late to convert the whole problem using API class since the code is very complicated and has thousands of lines.

I tried what you adviced me to do with numerical precision but again it says  "integer infeasible"......

I also tried other parameters such as feasibility tolerance etc but the same result.....

I noticed that the problem happens when 1 inequality constraint becomes stricter than the equivalent bound. Pay attention that this constraint is a*Q<b (a, b simple numbers) which means that it is a second let's say bound (it includes only 1 variable).

• Do you think that using an expression which could be a bound as an inequality constraint, causes confusion to CPLEX?

The strange that I cannot explain is that while there is more than 1 simple solutions, the MIQCP export is "integer infeasible"...

• The word "integer" means that the problem is related to an integer variable or it refers to the problem as MIP?
• Have you ever met such a peculiar case? Any idea? (keep in mind that there are feasible solutions and it says that there not)

Thanks again

#CPLEXOptimizers
#DecisionOptimization

Several things:

1. You don't have to rewrite your whole code to use the class API. For the toolbox functions you have matrices like Aeq, Aineq, beq, bineq, etc. In order to use the class API you can just assign these matrices to an instance of class Cplex:
   

   cplex = Cplex();
   cplex.Model.A = Aeq;
   cplex.Model.lhs = beq;
   cplex.Model.rhs = beq;
   ...
   cplex.solve();
   cplex.refineConflict(...);
   cplex.feasOpt(...);
   

   This way it should not be hard to use the class API on your matrices.

2. Was this a typo or do you really have strict inequality in 'a*Q<b'? You cannot even input strict inequalities to CPLEX, I think.

3. "integer infeasible" means that the (mixed) integer model is infeasible. It does not give any hint as to "where" the infeasibility is "located".

4. Yes, we have seen models that are feasible and infeasible simultaneously. Since CPLEX uses finite precision arithmetic it has to apply a set of tolerances to all decisions. (in)feasibility is always declared with respect to those tolerances. Depending on the tolerances it is not too hard to come up with models that feasible and infeasible simultaneously within those tolerances.

Another thing you can try to debug your problem is to export your model to a SAV file (use the ExportModel parameter, see here) and then solve in the interactive:

CPLEX> read model.sav
CPLEX> optimized
CPLEX> conflict
CPLEX> display conflict all

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Pan_Greece

Daniel thanks again for the useful advice,

You were right, using API was too easy to worry about...only some simple additional lines.....

Something very strange happened again....the algorithm ran successfully (fortunately)!!!

and the results were what I expected to be.....

Here there is the output of the algorithm:

Tried aggregator 1 time.
MIQP Presolve eliminated 2953 rows and 620 columns.
MIQP Presolve modified 195 coefficients.
Number of nonzeros in lower triangle of Q = 11580
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.00 sec. (0.26 ticks)
Summary statistics for factor of Q:
  Rows in Factor            = 584
  Integer space required    = 584
  Total non-zeros in factor = 12164
  Total FP ops to factor    = 369804
Reduced MIQP has 1768 rows, 676 columns, and 33223 nonzeros.
Reduced MIQP has 70 binaries, 70 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 23744 nonzeros.
Presolve time = 0.12 sec. (16.58 ticks)
Probing time = 0.00 sec. (0.35 ticks)
Clique table members: 115.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 2 threads.
Root relaxation solution time = 0.61 sec. (247.00 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0       -1.2735    47                     -1.2735       22         
*     0+    0                           -1.2734       -1.2735       22    0.01%

Root node processing (before b&c):
  Real time             =    0.78 sec. (275.25 ticks)
Parallel b&c, 2 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.78 sec. (275.25 ticks)

 

I tried many times to run the same algorithm with the CPLEX Toolbox for Matlab but I was getting the same result all the times.

So, the API works in a few seconds while the Toolbox not at all.

Do you see something strange on this situation taking into account also the above output message??

Or simply the API class is based on more robust algorithms?

#CPLEXOptimizers
#DecisionOptimization

The class API and the toolbox functions internally use the callable library, so they use the exact same algorithms. First thing to check here is that you indeed solve the same models in both cases. To check this you can export the models to LP format in either case and then compare the two files. Can you double check that the models are the exact same?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Pan_Greece

Hello Daniel,

I used exactly the same matrixes Aeq, beq, Aineq in the class API as I did with the toolbox functions. The only thing I did is what you have told me to do in your previous reply...I just added the following lines on the same code. So there is no reason to have an internal different model (...same variables, same matrixes, same sizes)...is there?

I tested it many times and it seems that the toolbox functions cannot solve the problem while the class API can.

The surprising is that until now the class API gives me back the expected results. For this point of view, I feel lucky for the case studies I have run.

#CPLEXOptimizers
#DecisionOptimization