[SCIP] Solution feasibility of the copied SCIP
M. Far.
pharham at gmail.com
Mon Nov 5 17:15:01 CET 2018
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20181105/e2cf4cb3/attachment.html>
More information about the Scip
mailing list