[SCIP] Solution feasibility of the copied SCIP

Gerald Gamrath gamrath at zib.de
Tue Dec 4 17:46:02 CET 2018


Dear Saleh,

what do you mean with different? Is the objective function value of the 
two solutions equal (within tolerances)? Then, SCIP just finds two 
different optimal solutions in the two runs, something that I would not 
expect, but may happen. If the value is indeed different, then there is 
really a bug.

What happens if you create two copies of the problem and solve them? Are 
the solutions of both copies identical?

Best,
Gerald

Am 03.12.18 um 19:43 schrieb M. Far.:
> Hi.
> I Have a problem I could not solve yet and my experiments depends on that.
> Consider the following code:
> ```
> SCIP* scip;
> SCIP_CALL(SCIPcreate(&scip));
> SCIP_CALL(SCIPincludeDefaultPlugins(scip));
> // [ code blocks to create scip problem ] ...
> // immediately create a copy of scip
> SCIP* scip2;
> SCIP_CALL(SCIPcreate(&scip2));
> SCIP_HASHMAP *varmap, *conmap;
> SCIP_CALL(SCIPhashmapCreate(&varmap, SCIPblkmem(scip2), 
> SCIPgetNVars(scip)));
> SCIP_CALL(SCIPhashmapCreate(&conmap, SCIPblkmem(scip2), 
> SCIPgetNConss(scip)));
> SCIP_CALL(SCIPcopyOrig(scip, scip2, varmap, conmap, "copyProb", false, 
> false, NULL));
> // solve the copy of scip
> SCIP_CALL(SCIPsolve(scip2));
> auto sol2 = SCIPgetBestSol(scip2);
> // solve the original scip
> SCIP_CALL(SCIPsolve(scip));
> auto sol1 = SCIPgetBestSol(scip);
> ```
> Could you please explain why sol1 and sol2 become different?
> It does not matter if I solve scip before or after solving scip2. I 
> even used `SCIPwriteOrigProblem` for both scip and scip2 just before 
> calling `SCIPsolve` for each, and the lp files are the same. Yet, they 
> return different optimal solutions.
>
> On Mon, Nov 5, 2018 at 7:15 PM M. Far. <pharham at gmail.com 
> <mailto:pharham at gmail.com>> wrote:
>
>     Thanks Gerald.
>     Using hash maps was the key.
>
>     // create a copy using hashmaps for variables
>     SCIP_HASHMAP* varmap;
>     SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(scip2),
>     SCIPgetNVars(scip)) );
>     SCIP_CALL( SCIPcopyOrig(scip, scip2, varmap, nullptr, "copyProb",
>     false, false, nullptr) );
>
>     // solve the copied problem
>     SCIP_CALL( SCIPsolve(scip2) );
>
>     // create a solution for scip based on the solution of scip2
>     SCIP_SOL* solInit;
>     SCIP_CALL( SCIPcreateSol(scip, &solInit, NULL) );
>     for (int i = 0; i < SCIPgetNVars(scip); ++i)
>     {
>         auto var = (SCIP_VAR*)SCIPhashmapGetImage(varmap,
>     SCIPgetVars(scip)[i]);
>         auto solval = SCIPgetSolVal(scip2, SCIPgetBestSol(scip2), var);
>         SCIP_CALL( SCIPsetSolVal(scip, solInit, SCIPgetVars(scip)[i],
>     solval) );
>     }
>
>     // add the new solution to the original scip
>     SCIP_Bool success;
>     SCIP_CALL(SCIPaddSolFree(scip, &solInit, &success));
>
>     Best regards.
>
>
>     On Sat, Nov 3, 2018 at 5:19 PM Gerald Gamrath <gamrath at zib.de
>     <mailto:gamrath at zib.de>> wrote:
>
>         Dear Saleh,
>
>         you cannot just take a solution for scip2 and add it to scip1.
>         You need to create a new solution in scip1 and set the value
>         of each variable in scip1 to the value the corresponding
>         variable in scip2 has in the solution. You should use the
>         hashmaps for this that SCIP fills while copying the problem.
>         Please check any of the sub-MIP heuristics of SCIP for an
>         example how this can be done.
>
>         Best,
>         Gerald
>
>         -------- Ursprüngliche Nachricht --------
>         Von: "M. Far." <pharham at gmail.com <mailto:pharham at gmail.com>>
>         Datum: 03.11.18 14:46 (GMT+01:00)
>         An: hendel at zib.de <mailto:hendel at zib.de>
>         Cc: SCIP_Mailing_list SCIP_Solver <scip at zib.de
>         <mailto:scip at zib.de>>
>         Betreff: Re: [SCIP] Solution feasibility of the copied SCIP
>
>         Dear Gregor,
>
>         Here, I list different configurations of presolving parameter
>         in both scips and their effect:
>         1. OFF in scip & DEFAULT in scip2 => solution of scip2 is
>         INFEASIBLE for scip & final solution of scip is NOT OPTIMAL
>         (different than that of scip2)
>         2. OFF in scip & OFF in scip2 => solution of scip2 is FEASIBLE
>         for scip & final solution of scip is OPTIMAL (same as that of
>         scip2)
>         3. DEFAULT in scip & DEFAULT in scip2 => solution of scip2 is
>         INFEASIBLE for scip & final solution of scip is OPTIMAL (same
>         as that of scip2)
>         4. DEFAULT in scip & OFF in scip2 => solution of scip2 is
>         FEASIBLE for scip & final solution of scip is OPTIMAL (same as
>         that of scip2).
>         So I suppose the bug appears when I turn on presolving for
>         scip2. Please note that I cannot have default presolving
>         settings in the original scip as it is going to be a master
>         problem for column generation. Yet, these tests are done
>         before I add the pricer and run column generation. Therefore,
>         it is a VRP with some initial routes that make a complete
>         solution and I want to examine this initial solution.
>
>         Under configuration 1, making "presolving/donotaggr" and
>         "presolving/donotmultaggr" TRUE in scip2 had no effect on the
>         results I stated above. However, it changes the violated
>         constraint. Before turning on these parameters in scip2, the
>         violated constraint was in the form of `x1 + x2 + a*y <= 0`
>         where variables x1 and x2 are continuous and y is binary: 
>         `[linear] <cap_con>: <x1>[C] (+180) +<x2>[C] (+0) -180<y>[B]
>         (+0) <= 0`. The value of x1 in the solution of scip2 is 180
>         (same as here), but the value of y in that solution was 1
>         (scip takes it as 0 here).
>         When I set "presolving/donotaggr" and
>         "presolving/donotmultaggr" to TRUE, the solution of scip2
>         `violates original bounds of variable <z1> [0,0] solution
>         value <1>` in scip. z1 is a binary variable which is 0 in the
>         solution of scip2 and, later, in the solution of scip.
>         Without touching presolving/donotaggr" and
>         "presolving/donotmultaggr" in scip2, I tested this procedure
>         on other instances to see which constraints are violated. The
>         violation constraint differ but they are either in the linear
>         form like `x1 + ... + xn + a*y <= 0` or some binary variable
>         bounds. So I guess it is not deterministic.
>
>         Going back to configuration 1, both scip and scip2 have
>         identical OrigProblem lp files (as expected). When I write
>         TransProblems, scip2 has the following statistics just after
>         calling SCIPpresolve(scip2):
>         \   Variables        : 252 (151 binary, 2 integer, 0 implicit
>         integer, 99 continuous)
>         \   Constraints      : 158
>         \   Obj. scale       : 0.1
>         \   Obj. offset      : 4050
>         And it has the following statistics after calling
>         SCIPsolve(scip2):
>         \   Variables        : 252 (151 binary, 2 integer, 0 implicit
>         integer, 99 continuous)
>         \   Constraints     : 139
>         \   Obj. scale       : 0.1
>         \   Obj. offset      : 4050
>         whereas for scip, I get the following statistics after calling
>         SCIPsolve(scip2):
>         \   Variables        : 609 (464 binary, 6 integer, 0 implicit
>         integer, 139 continuous)
>         \   Constraints      : 504
>         \   Obj. scale       : 0.1
>         \   Obj. offset      : 0
>         The OrigProblem has the following statistics (same for both):
>         \   Variables        : 609 (464 binary, 6 integer, 0 implicit
>         integer, 139 continuous)
>         \   Constraints      : 514
>         \   Obj. scale       : 1
>         \   Obj. offset      : 0
>
>         When I look at the `cap_con` in the TransProblem of scip2, it
>         is transformed into `+1 t_x1 +1 t_x2 <= +180` (i.e. y is set
>         to 1) in both of its transformed problems (i.e. after
>         SCIPpresolve(scip2) and after SCIPsolve(scip2)). However,
>         there is no `cap_con` in TransProblem of scip! I think this is
>         where the problem occurs, but I cannot see how.
>
>         Thank you for your consideration, I would really appreciate
>         your help.
>
>         Saleh
>
>         On Fri, Nov 2, 2018 at 8:57 PM Gregor Hendel <hendel at zib.de
>         <mailto:hendel at zib.de>> wrote:
>
>             Dear Saleh,
>
>             this is indeed a bit strange.
>
>             There is probably a numerical problem. For starters, you
>             can use presolving, but avoid multiaggregations by
>             setting the two boolean parameters "presolving/donotaggr"
>             and "presolving/donotmultaggr" to TRUE in your scip2. They
>             are often the reason for numerical troubles in the
>             original space.
>
>             Unfortunately, you have optimized out some of the relevant
>             information to help you, such as the type and violation of
>             the constraint that is violated.
>
>             Two questions:
>             1. I assume that if you do *not* disable presolving in the
>             original SCIP, the bug is not triggered?
>             2. If the problem is a simple MIP problem, have you tried
>             to write out the transformed problems of both SCIPs? You
>             could write them in lp-format, which is very readable for
>             small instances, and check what has happened to the
>             violated constraint after presolving in the problem copy.
>
>             To do so, use
>
>             SCIP_CALL( SCIPpresolve(scip2) );
>             SCIP_CALL( SCIPwriteTransProblem
>             <https://scip.zib.de/doc-6.0.0/html/group__GlobalProblemMethods.php#gada41a57fc5a464ad565763d24e588d3a>(scip2,
>             "presolvedprob.lp", "lp", false) )
>
>             Maybe one of my guesses gets you started already,
>             Gregor
>
>
>             Am 02.11.18 um 17:58 schrieb M. Far.:
>>             Hi
>>             I am working on a simple MILP problem in SCIP's c++
>>             interface using CPLEX as the LP solver.
>>             I have to disable presolving in my original problem
>>             'scip'. So I have:
>>             SCIP_CALL( SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF,
>>             true) );
>>             after creating scip. Then, I need to solve a copy of the
>>             problem by creating a second problem 'scip2':
>>             SCIP* scip2;
>>             SCIP_CALL( SCIPcreate(&scip2) );
>>             SCIP_CALL( SCIPcopyOrig(scip, scip2, nullptr, nullptr,
>>             "copyProb", false, false, nullptr) );
>>             SCIP_CALL( SCIPsetIntParam(scip2, "display/verblevel", 2) );
>>
>>             And I can turn on presolving procedure in this problem.
>>             So I have:
>>             `SCIP_CALL( SCIPsetPresolving(scip2,
>>             SCIP_PARAMSETTING_DEFAULT, true) );`
>>
>>             Next, I want to add the solution of scip2 as an initial
>>             feasible solution to the original problem. Hence:
>>             ```
>>             SCIP_CALL( SCIPsolve(scip2) );
>>             auto sol2 = SCIPgetBestSol(scip2);
>>             SCIP_Bool stored;
>>             SCIP_CALL( SCIPaddSolFree(scip, &sol2, &stored) );
>>             ```
>>             However, when I solve the original scip by calling
>>             `SCIPsolve(scip)`, I get the following message in the output:
>>             ```
>>             violation: right hand side is violated by <a_number>
>>             all 1 solutions given by solution candidate storage are
>>             infeasible
>>             ```
>>             Next, it ignores the solution, solves the problem, and
>>             finds an "optimal solution" which is inferior to sol2
>>             (hence, not optimal indeed).
>>
>>             I understand that something may be wrong with the
>>             transformation. But I do not know how to fix this.
>>             (OS: Linux 4.15, SCIP ver.: 6.0.0, CPLEX ver.: 12.8.0,
>>             gcc ver.: 7.3.0)
>>
>>             Bests,
>>
>>             Saleh
>>
>>             _______________________________________________
>>             Scip mailing list
>>             Scip at zib.de  <mailto:Scip at zib.de>
>>             https://listserv.zib.de/mailman/listinfo/scip
>
>             _______________________________________________
>             Scip mailing list
>             Scip at zib.de <mailto:Scip at zib.de>
>             https://listserv.zib.de/mailman/listinfo/scip
>
>
>
>         -- 
>         M Saleh F
>
>
>
>     -- 
>     M Saleh F
>
>
>
> -- 
> M Saleh F

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20181204/6073563c/attachment.html>


More information about the Scip mailing list