<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1252">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
Dear SCIP team and SCIP users,</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
A few months ago I asked if it was possible to solve a problem where all constraints were convex but some variables were integer (so relaxing these integral variables to intervals would make the problem convex).</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
SCIP provides a "constraints/nonlinear/assumeconvex" parameter that tells the solver "whether to assume that any constraint in the presolved problem is convex".</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
In my problem, if this parameter was False (default), constraints were not recognized as convex and SCIP entered into an expensive and useless spatial branch-and-bound. </div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
If this parameter was True, however, SCIP gave integer solutions that were clearly suboptimal.</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
Stefan took some time to give me a very clear answer, and I wanted to share it here in case other people may face the same issue.</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
The problem was coming from SCIP's pre-processing that was breaking the convexity of my constraints : namely, one of the preprocessings replaces expressions like x^2 by x if x \in {0,1} - which is equivalent in {0,1}. This preprocessing may break the convexity
of a constraint - for instance x^2/(y+1) < 1 is convex on [0,1]^2 but after running the preprocessing it becomes x/(y+1)<1 which is not convex anymore. </div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
So Stefan pointed to such preprocessings and suggested to add something like "if assumeconvex == False" in their conditions to avoid destroying convexity ; after doing the correct change the solver works perfectly (cf. discussion below for more details).</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<br>
</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
Thanks for your help (and hopefully this message will help some other users!)</div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
Guillaume </div>
<div style="font-family: Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);" class="elementToProof">
<br>
</div>
<div id="appendonsend"></div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>De :</b> Stefan Vigerske <svigerske@gams.com><br>
<b>Envoyé :</b> samedi 16 août 2025 12:50<br>
<b>À :</b> Guillaume BS <guillaume_bs@hotmail.com><br>
<b>Objet :</b> Re: [SCIP] Solving a Convex MINLP</font>
<div> </div>
</div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt;">
<div class="PlainText">Hi,<br>
<br>
thanks, I think I can reproduce and explain.<br>
The assumeconvex parameter itself is odd. It tells SCIP that something <br>
is convex, but doesn't explain why that is the case, and what is <br>
necessary to preserve convexity. SCIP applies this to the presolved <br>
problem, but the presolve reductions do not care about it and could <br>
possibly destroy the convexity. It would be best not to use this <br>
parameter, unless one knows exactly what is going on.<br>
<br>
Looking at the problem, it's quite easy to guess where things go wrong: <br>
You have binary variables z_0_0_ and terms z_0_0_^2 in the nonlinear <br>
constraints. SCIP simplifies this to z_0_0_, which then destroys <br>
convexity of the constraint function. There is no parameter to turn this <br>
off. If you are happy to change code, then remove this part: <br>
<a href="https://github.com/scipopt/scip/blob/80c1fbfe1b38cf92132630654bdf0998df8dd9e7/src/scip/expr_pow.c#L1440-L1445">https://github.com/scipopt/scip/blob/80c1fbfe1b38cf92132630654bdf0998df8dd9e7/src/scip/expr_pow.c#L1440-L1445</a><br>
If I do this, then the "MIP" problem seems to be solved correctly.<br>
<br>
For the relaxed problem, replacing z_0_0_^2 by z_0_0_ is not possible <br>
for SCIP, so you don't see the same issue.<br>
<br>
Best,<br>
Stefan<br>
<br>
On 04/08/2025 17:17, Guillaume BS wrote:<br>
> Hi Stefan,<br>
> Thanks for your answer.<br>
> Indeed exporting the nonlinear program with the ".cip" format allows easy communication of non-linear models between the C API and the SCIP command-line interface.<br>
> <br>
> I could reproduce the behavior observed in C: with the parameter "constraints/nonlinear/assumeconvex" to TRUE, SCIP converges to a suboptimal solution - while setting this parameter to FALSE leads to the true solution.<br>
> On another hand, the fractional relaxation of the problem (with binary variables relaxed in [0,1] instead of {0,1}) is solved correctly even with assumeconvex = TRUE.<br>
> <br>
> I attached an example to this email with both the MIP and relax problems. Note that the non-linear constraints, lines 97 to 111, are convex (it is a direct implementation of constraints 9.c in
<a href="https://www.researchgate.net/profile/Gerard-Cornuejols/publication/225470397_Mixed-integer_nonlinear_programs_featuring_onoff_constraints/links/0deec5213623630b0e000000/Mixed-integer-nonlinear-programs-featuring-on-off-constraints.pdf?_sg%5B0%5D=started_experiment_milestone&_sg%5B1%5D=started_experiment_milestone&origin=journalDetail">
https://www.researchgate.net/profile/Gerard-Cornuejols/publication/225470397_Mixed-integer_nonlinear_programs_featuring_onoff_constraints/links/0deec5213623630b0e000000/Mixed-integer-nonlinear-programs-featuring-on-off-constraints.pdf?_sg%5B0%5D=started_experiment_milestone&_sg%5B1%5D=started_experiment_milestone&origin=journalDetail</a>
; computing the hessian also shows convexity).<br>
> <br>
> This behavior tends to show something odd with the assumeconvex parameter when used in a branch-and-bound tree.<br>
> Do you confirm this interpretation – and, if so, do you know where it could come from ?<br>
> <br>
> Many thanks,<br>
> Guillaume<br>
> <br>
> <br>
> <br>
> ________________________________<br>
> De : Stefan Vigerske <svigerske@gams.com><br>
> Envoyé : lundi 21 juillet 2025 11:09<br>
> À : Guillaume BS <guillaume_bs@hotmail.com><br>
> Objet : Re: [SCIP] Solving a Convex MINLP<br>
> <br>
> Hi,<br>
> <br>
> The reading/writing situation sounds not so good. There is some work in<br>
> progress to add nl writing, but not sure it will make it into SCIP 10.<br>
> For gms, there is a reader in the COIN-OR/GAMSlinks project, but it<br>
> needs GAMS to run. OSiL writing is something that technically wouldn't<br>
> be hard to do, but noone found the time.<br>
> Anyway, yhou could try writing in SCIP's own CIP format. For that one,<br>
> SCIP can write and read nonlinear constraints as well.<br>
> <br>
> Stefan<br>
> <br>
> On 21/07/2025 11:00, Guillaume BS wrote:<br>
>> Dear Stefan,<br>
>><br>
>> Thanks a lot for your answer, and for confirming this was not the intended behavior.<br>
>><br>
>> The MINLP displaying this strange behavior was created with the C/C++ inteface of SCIP ; it contains several non-linear constraints (containing sum of fractions known to be convex).<br>
>><br>
>> In order to better understand the problems and ensure there is no bug on my side/provide a reproductible example, I try to export the problem to a file to run it with SCIP command line interface.<br>
>><br>
>> I could export a gms file (with the SCIPwriteGms function), but this format is not read by SCIP.<br>
>> Conversly, it seems SCIP could read the OSiL format, but not export models in it.<br>
>> I could not find any format for "generic" MINLPs - containing the nonlinear expressions provided by SCIP - that SCIP could both read and write. Do you know how one can export a nonlinear model created with the SCIP C++ interface and read it in the CLI ?<br>
>><br>
>> Thanks again for your time,<br>
>> Guillaume<br>
>> ________________________________<br>
>> De : Scip <scip-bounces@zib.de> de la part de Stefan Vigerske <svigerske@gams.com><br>
>> Envoyé : dimanche 13 juillet 2025 19:02<br>
>> À : scip@zib.de <scip@zib.de><br>
>> Objet : Re: [SCIP] Solving a Convex MINLP<br>
>><br>
>> Hi,<br>
>><br>
>> constraints/nonlinear/assumeconvex only overwrites the convexity check<br>
>> for nonlinear functions. So any g_i(x,y) is assumed to be convex in<br>
>> (x,y) on the domain given by the variable bounds. So if this can be<br>
>> assumed for y in [0,1], it will also work for y in {0,1}.<br>
>> Maybe there is some bug which results in an incorrect solution for the<br>
>> MINLP case.<br>
>><br>
>> Stefan<br>
>><br>
>><br>
>> On 07/07/2025 13:19, Guillaume BS wrote:<br>
>>> Dear SCIP team,<br>
>>><br>
>>> I am trying to solve a relatively simple convex MINLP of the shape:<br>
>>><br>
>>> min c^t x<br>
>>> s.t.: g_i(x,y) \leq 0 i \in 1..m<br>
>>> Ax + By \leq d<br>
>>> x \in R^n, y \in B^n'<br>
>>><br>
>>> with all functions g_i convex (cf "Convex MINLP" in <a href="https://www.scipopt.org/doc/html/WHATPROBLEMS.php">
https://www.scipopt.org/doc/html/WHATPROBLEMS.php</a> ).<br>
>>> I try to solve the MINLP (with variables y in {0,1}, and its convex relaxation (with variables y in [0,1] ).<br>
>>><br>
>>> In the documentation, a parameter "constraints/nonlinear/assumeconvex" is described, which allows assuming that all constraint functions are convex.<br>
>>><br>
>>> The convex relaxed NLP with y \in [0,1]:<br>
>>><br>
>>> *<br>
>>> is easily solved by SCIP when the "constraints/nonlinear/assumeconvex" parameter equals TRUE<br>
>>> *<br>
>>> is not easily solved by SCIP (several minutes for a toy instance with a few variables and constraints) when "constraints/nonlinear/assumeconvex" equals FALSE ; from the logs, it seems SCIP can't prove the complexity of the constraints and runs a spatial
branch-and-bound (several nodes are generated, despite having only continuous variables).<br>
>>><br>
>>> The MINLP with y \in {0,1}:<br>
>>><br>
>>> *<br>
>>> is not correctly solved when "constraints/nonlinear/assumeconvex" is true: a feasible solution, with values of the binary variable y fixed "randomly", is returned by SCIP.<br>
>>> *<br>
>>> is very slow when "constraints/nonlinear/assumeconvex" is false<br>
>>><br>
>>> So it seems the "constraints/nonlinear/assumeconvex" parameters not only controles the convexity of the constraints in the NLP relaxation, but also the convexity of the variables' domains - which would make it improper to solve an MINLP.<br>
>>><br>
>>> Is this understanding correct and, if so, is there a way to solve a MINLP when all constraints are known to be convex - but the variables domain isn't ? (for instance by stating, for each nonlinear constraint, that it should be considered as convex?)<br>
>>><br>
>>> Many thanks,<br>
>>> Guilaume<br>
>>><br>
>>><br>
>>> _______________________________________________<br>
>>> Scip mailing list<br>
>>> Scip@zib.de<br>
>>> <a href="https://listserv.zib.de/mailman/listinfo/scip">https://listserv.zib.de/mailman/listinfo/scip</a><br>
>><br>
>> _______________________________________________<br>
>> Scip mailing list<br>
>> Scip@zib.de<br>
>> <a href="https://listserv.zib.de/mailman/listinfo/scip">https://listserv.zib.de/mailman/listinfo/scip</a><br>
>><br>
> <br>
> <br>
<br>
</div>
</span></font></div>
</body>
</html>