[SCIP] Solution feasibility of the copied SCIP
M. Far.
pharham at gmail.com
Mon Dec 3 19:43:59 CET 2018
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> 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> 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>
>> Datum: 03.11.18 14:46 (GMT+01:00)
>> An: hendel at zib.de
>> Cc: SCIP_Mailing_list SCIP_Solver <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> 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 listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> 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/20181203/27296ec1/attachment.html>
More information about the Scip
mailing list