[SCIP] SCIP presolver for MIQCP

[Benjamin Müller]

Dear Ahmed,

yes, it is a normal behaviour you can observe on many MIQCPs. During 
presolving SCIP detects some structures which can be reformulated with 
the help of auxiliary variables. For example, one can replace the 
product of binary variables by using an AND constraint, or disaggregate 
quadratic constraints into smaller ones, ...

In the log file you can see that because of these reformulations (and 
probably other presolving techniques) SCIP was able to reduce the number 
of quadratic constraints a lot. It might be worth to test different 
values for the parameters

     constraints/quadratic/disaggregate
     constraints/quadratic/replacebinaryprod

in the quadratic constraint handler to have more control over the 
applied reformulations.


Cheers,

Benny


On 03/10/2016 04:53 AM, Ahmed Ibrahim wrote:
> Hi All,
> I was wondering whether it is normal for the presolver to return a 
> presolved MIQCP with a larger number of continuous variables and 
> larger number of linear constraints than was provided in the original 
> instance?
> The details are provided below (N.B iam using opti toolbox which 
> interfaces SCIP with Matlab):
>  Problem Properties:
> # Decision Variables: 527
> # Constraints:             4261
>   # Linear Inequality: 256
>   # Quadratic Constraints: 2844
>   # Bounds:                1054
>   # Binary Variables:      107
> ------------------------------------------------------
>   Solver Parameters:
> Solver:                    SCIP
> ------------------------------------------------------
> numerics/lpfeastol = 1e-012
> feasible solution found by trivial heuristic after 0.0 seconds, 
> objective value -1.000000e+000
> presolving:
> (round 1, fast)       9 del vars, 20 del conss, 0 add conss, 0 chg 
> bounds, 0 chg sides, 0 chg coeffs, 0 upgd conss, 0 impls, 42 clqs
> (round 2, fast)       9 del vars, 20 del conss, 7560 add conss, 0 chg 
> bounds, 0 chg sides, 0 chg coeffs, 840 upgd conss, 0 impls, 42 clqs
> (round 3, fast)       9 del vars, 20 del conss, 7560 add conss, 0 chg 
> bounds, 840 chg sides, 840 chg coeffs, 840 upgd conss, 2520 impls, 760 
> clqs
> (round 4, exhaustive) 9 del vars, 20 del conss, 7560 add conss, 0 chg 
> bounds, 840 chg sides, 840 chg coeffs, 1074 upgd conss, 2520 impls, 
> 760 clqs
> (round 5, medium)     9 del vars, 22 del conss, 7644 add conss, 0 chg 
> bounds, 840 chg sides, 840 chg coeffs, 1074 upgd conss, 2604 impls, 
> 844 clqs
> (round 6, exhaustive) 9 del vars, 108 del conss, 7646 add conss, 0 chg 
> bounds, 840 chg sides, 840 chg coeffs, 1074 upgd conss, 2604 impls, 
> 844 clqs
> (round 7, exhaustive) 9 del vars, 108 del conss, 7646 add conss, 0 chg 
> bounds, 840 chg sides, 1917 chg coeffs, 1074 upgd conss, 2604 impls, 
> 844 clqs
>    (0.2s) probing: 51/106 (48.1) - 0 fixings, 0 aggregations, 0 
> implications, 0 bound changes
>    (0.2s) probing aborted: 50/50 successive totally useless probings
> presolving (8 rounds: 8 fast, 5 medium, 4 exhaustive):
>  9 deleted vars, 108 deleted constraints, 7646 added constraints, 0 
> tightened bounds, 0 added holes, 840 changed sides, 1917 changed 
> coefficients
>  2604 implications, 867 cliques
> presolved problem has 3038 variables (106 bin, 0 int, 0 impl, 2932 
> cont) and 10638 constraints
> 2604 constraints of type <varbound>
>      42 constraints of type <setppc>
>       2 constraints of type <and>
>  5882 constraints of type <linear>
>     104 constraints of type <logicor>
>    2004 constraints of type <quadratic>
>
>
> Regards,
> Ahmed
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
______________________________
Benjamin Müller
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
benjamin.mueller at zib.de
+49 30 841 85-195

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20160310/694df51a/attachment.html>