[SCIP] (Re-)Setting solution variables and testing for feasibility
Jan Berling
berlingjan at gmail.com
Thu Jun 16 17:59:59 CEST 2016
Dear Gregor, Dear Jakob, Dear List,
thank you for the clarifications, I have now disabled presolving by
SCIP_ERR(SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF, TRUE), "error
disable presolving");
I have tried to ckeck the solution on the original problem before, but the
result is always feasible. Even though I know it can't be feasible, by
problem-knowledge and by the check of constraints, which I know are
infeasible and also returned as infeasible by SCIPcheckCons().
SCIPcheckCons(scip, cons, mysol, 1, 1, 1, &resultcons);
SCIP_ERR(SCIPcheckSolOrig(scip, mysol, &isfeasible 1, 1), "error
checking sol orig");
Probably this is because more variables are added in the pricing process,
which are only existing in the transformed problem, as I understand.
Nevertheless, the variables which are changed in the solution are not from
the pricing process.
I think I will just check for feasibility by checking the integrality and
lprows (constraints). This is sufficient because the rounding solution will
always have feasible boundaries when the solution variables are only set to
0 or 1.
Cheers,
Jan
2016-06-16 17:34 GMT+02:00 Jakob Witzig <witzig at zib.de>:
> Hi Jan,
>
> just an additional comment to prevent confusions:
>
> Am 16.06.2016 um 17:25 schrieb Gregor Hendel:
>
>> SCIPsetPresolving(scip, SCIP_PARAMEMPHASIS_OFF,
>> true_or_false_for_quiet_output).
>>
>> Yet, this will not affect bound reductions during search caused by the
>> behavior described above.
>>
>
> Disabling presolving will not prevent global bound changes. A local bound
> change will be applied globally whenever the bound change is made at the
> effective root, i.e., the deepest node in the tree that is on all paths
> from the root node to all unprocessed nodes.
>
> Cheers,
> Jakob
>
>
>>
>> Am 16.06.2016 um 16:39 schrieb Jan Berling:
>>
>>> Hi Jakob,
>>>
>>> The problem is a pure IP, pure BIP.
>>>
>>> The infeasibility is not due to the constraints but due to the
>>> boundaries, as only the check for bounds results in infeasibility:
>>>
>>> SCIP_ERR(SCIPcheckSol(scip, mysol, 1, 1, 0, 0, &isSolFeasible),
>>> "Error checking if sol is feasible");
>>>
>>> The boundaries of the variables are lb = 0.0 and ub = 0.0, which is
>>> seen by
>>>
>>> SCIPvarGetLbGlobal(var)
>>> SCIPvarGetUbGlobal(var)
>>>
>>> Is it possible that the boundaries are changed or that the variables
>>> are fixed in the solution process? Presolving is disabled by
>>>
>>> SCIPsetBoolParam(scip, "lp/presolving", FALSE);
>>>
>>> I tried to manually change the bounds but this didn't have any effect.
>>>
>>> var->glbdom.lb <http://glbdom.lb> = 0.0
>>> var->glbdom.ub = 1.0
>>>
>>> Is it possible to "unfix" the variable or make it possible to change
>>> the value without violating bounds?
>>>
>>> Cheers,
>>> Jan
>>>
>>> 2016-06-16 9:15 GMT+02:00 Jakob Witzig <witzig at zib.de
>>> <mailto:witzig at zib.de>>:
>>>
>>>
>>> Hi Jan,
>>>
>>> you already mentioned numerical troubles, I can imagine two
>>> reasons for the infeasibility:
>>>
>>> Do you have pure IP or a MIP?
>>>
>>> 1) If you have a MIP your continuous variables need not fit with
>>> the new solution value (even if you just 'polished' the value). In
>>> that case you may should try to fix all your integer values and
>>> resolve the resulting LP again.
>>>
>>> 2) If you have a pure IP changing one solution value can lead to
>>> infeasibility due tu numerical troubles, e.g, 1e+07 * x + y == 1
>>> with x = 1e-07 and y = 0, both binary and feasibility tolerance
>>> 1e-06. Changing x to 0 will violate your constraint. Sure, this
>>> corner-case will be detected by each MIP solver but it should
>>> illustrate the issue. In that case, you have to do some clever
>>> relaxing of variables and you need to resolve the reduced problem.
>>> Just an idea for relaxing variables: If you change the solution
>>> value a variable x you could relax all variables in the
>>> 1-neighbourhood, i.e., variables sharing constraints with x.
>>>
>>> I hope this will help.
>>>
>>> Cheers,
>>> Jakob
>>>
>>>
>>>
>>> Am 15.06.2016 um 18:52 schrieb Jan Berling:
>>>
>>> Dear mailing list,
>>>
>>> when we manually change a variable of a feasible solution
>>> which was
>>> found by the scip solver, the solution becomes infeasible,
>>> even though
>>> it was feasible before and we know that it has to be feasible
>>> afterwards, from problem-knowledge.
>>>
>>> SCIP_ERR(SCIPsetSolVal(scip, mysol, var, 0), "error setting
>>> solution value");
>>> SCIP_ERR(SCIPcheckSol(scip, mysol, 1, 1, 1, 1,
>>> &isSolFeasible),
>>> "Error checking sol");
>>>
>>> Is it possible to change solution variables that way and check
>>> for
>>> feasibility?
>>>
>>> We tried to copy the solution, transformed the variables,
>>> checked that
>>> the variables we change are active, tried SCIPtrySol(),...
>>>
>>> Our reasoning behind this approach:
>>>
>>> Due to numerical inaccuracies, scip sometimes finds inaccurate
>>> solutions
>>> for our binary integer problem. We would like to round
>>> non-integer
>>> variables manually after the solution is found. But simple
>>> rounding to
>>> the nearest value (e.g. 0.99999999 to 1.0) leads to infeasible
>>> solutions
>>> in some cases. From the knowledge about our problem, we know
>>> which
>>> variables we can set to guarantee feasible but poor solutions. To
>>> improve our solutions, we would like to try to round variables
>>> first,
>>> check if the resulting solution is feasible and if not choose
>>> the poor
>>> variables as a last option.
>>>
>>> Kind regards,
>>> Jan
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>>
>>> --
>>> Jakob Witzig
>>>
>>> Zuse Institute Berlin (ZIB)
>>>
>>> Division Mathematical Optimization and Scientific Information
>>> Research Group Mathematical Optimization Methods
>>>
>>> Takustrasse 7
>>> 14195 Berlin
>>>
>>> Tel. : +49 (0)30 84185-416 <tel:%2B49%20%280%2930%2084185-416>
>>> Fax : +49 (0)30 84185-269 <tel:%2B49%20%280%2930%2084185-269>
>>> email: witzig at zib.de <mailto:witzig at zib.de>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
>
> --
> Jakob Witzig
>
> Zuse Institute Berlin (ZIB)
>
> Division Mathematical Optimization and Scientific Information
> Research Group Mathematical Optimization Methods
>
> Takustrasse 7
> 14195 Berlin
>
> Tel. : +49 (0)30 84185-416
> Fax : +49 (0)30 84185-269
> email: witzig at zib.de
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20160616/bfcb1377/attachment.html>
More information about the Scip
mailing list