[SCIP] Solution feasibility of the copied SCIP
M. Far.
pharham at gmail.com
Sat Nov 3 14:46:51 CET 2018
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20181103/8b97a388/attachment.html>
More information about the Scip
mailing list