[SCIP] Cutting off the optimum when using relaxation handler

Renato Melo melo.renatosilva at gmail.com
Sat Dec 12 21:02:28 CET 2020 

SOLVED!
I did what you said, and now it's working.

Great thanks!

On Sat, Dec 12, 2020 at 5:01 PM Renato Melo <melo.renatosilva at gmail.com>
wrote:

>
> SOLVED!
> I did what I said, and now it's working.
>
> Great thanks!
>
> On Sat, Dec 12, 2020 at 7:30 AM Stefan Vigerske <svigerske at gams.com>
> wrote:
>
>> Hi,
>>
>> yes, the relaxator doesn't need to provide a solution.
>>
>> 108159 is the optimal value in the original problem, but the relaxation
>> is supposed to work on the transformed problem. At least the bound it
>> returns should correspond to the transformed problem, i.e., the problem
>> that SCIP actually solves. So in the relaxator code, it should be
>>     *lowerbound = SCIPtransformObj(scip, 108159); //pr76
>>
>> Stefan
>>
>> On 12/11/20 8:47 PM, Renato Melo wrote:
>> > Thank you again, Stefan.
>> >
>> > I will carefully review my constraint handler. Nevertheless, I would
>> prefer
>> > to provide only a lower bound, not a solution for my relaxation.
>> According
>> > to the SCIP's documentation, giving a solution is optional:
>> > "Usually, the RELAXEXEC callback only solves the relaxation and
>> provides a
>> > lower (dual) bound through the corresponding pointer and possibly a
>> > solution..."
>> >
>> > To illustrate, I forced my situation in the TSP example (
>> > https://www.scipopt.org/doc/html/TSP_MAIN.php). In this example, for
>> the
>> > input tspdata/pr76 the optimum value is *108159*. So, I have included a
>> > simple relaxation handler that always returns 108159 as a lower bound.
>> > After doing this, the algorithm ends with a solution of value *108425*,
>> > which is wrong.
>> >
>> > Below we have the constructor and the RELAXEXEC callback methods.
>> >
>> > MyDualBound::MyDualBound(SCIP *scip) : ObjRelax(scip,  "my-dual-bound",
>> >   "Dual bound for TSP",  1.0,  2,  TRUE) {}
>> >
>> > SCIP_DECL_RELAXEXEC(MyDualBound::scip_exec)
>> > {
>> >      *lowerbound = 108159; //pr76
>> >      *result = SCIP_SUCCESS;
>> >       return SCIP_OKAY;
>> > }
>> > What am I doing wrong?
>> >
>> > On Thu, Dec 10, 2020 at 3:55 AM Stefan Vigerske <svigerske at gams.com>
>> wrote:
>> >
>> >> Hi,
>> >>
>> >> yes, it doesn't look right.
>> >> Either the 5.0625 dual bound is wrong or the 2.25 solution is actually
>> >> not feasible. The initial dual bound may come from SCIP solving an LP
>> >> relaxation, to which all constraints have contributed linear
>> >> (in)equalities. A linear constraint just adds itself, your constraint
>> >> handler may do something specific.
>> >> But the 2.25 solution seems to violate some linear constraint that was
>> >> present in the original problem. That is, SCIP accepted the relaxation
>> >> solution in the transformed problem and thus may not have checked the
>> >> solution on this constraint. You might want to check why this happens,
>> >> e.g., whether the constraint is indeed still present in the transformed
>> >> problem (i.e., hasn't been removed by presolve), and whether the check
>> >> and enforce flags were set to TRUE.
>> >>
>> >> Stefan
>> >>
>> >> On 12/9/20 4:28 PM, Renato Melo wrote:
>> >>> Thank you for your helpful answer, Stefan
>> >>>
>> >>> I did completely forget to implement the ENFORELAX callback. Now, I
>> did
>> >>> what you said, and it is working almost fine.
>> >>>
>> >>> The algorithm ends with the following message:
>> >>>
>> >>> SCIP Status        : problem is solved [optimal solution found]
>> >>> Solving Time (sec) : 3.62
>> >>> Solving Nodes      : 1 (total of 2 nodes in 2 runs)
>> >>> Primal Bound       : +2.25000000000000e+00 (2 solutions)
>> >>> Dual Bound         : +2.25000000000000e+00
>> >>> Gap                : 0.00 %
>> >>>     [linear] <linking cons>: <x_50,0.000000>[B] (+0)
>> +<x_50,2.250000>[B]
>> >> (+0)
>> >>> +<x_50,4.500000>[B] (+0) +<x_50,6.750000>[B] (+0) +<x_50,9.000000>[B]
>> >> (+0)
>> >>> -<x_50>[B] (+1) == 0;
>> >>> ;
>> >>> violation: left hand side is violated by 1
>> >>> best solution is not feasible in original problem
>> >>>
>> >>> I searched for this error, and I found results related to feasibility
>> >>> tolerance, but I do not know how to solve it.
>> >>>
>> >>> In addition, I observed the following. Despite my relaxator finds a
>> >>> solution in the beginning of solving process, a dual bound greater
>> than
>> >>> mine appears in the output log:
>> >>>
>> >>> ...    dualbound       primalbound      Gap
>> >>> ... | 5.062500e+00 | 3.397500e+02 |6611.11%
>> >>> ... | 5.062500e+00 | 3.397500e+02 |6611.11%
>> >>> Truncate separation round because of stalling (10 stall rounds).
>> >>> *...| 2.250000e+00 | 2.250000e+00 |   0.00%
>> >>>
>> >>> Then it changes to my lower bound (2.25 is my lower bound and also the
>> >>> optimum).  Nevertheless, I think that this behavior is not right. Am I
>> >>> wrong?
>> >>>
>> >>> Best regards,
>> >>> Renato
>> >>>
>> >>> On Tue, Dec 8, 2020 at 1:21 AM Stefan Vigerske <svigerske at gams.com>
>> >> wrote:
>> >>>
>> >>>> Hi,
>> >>>>
>> >>>> regarding
>> >>>>
>> >>>>    > [src/scip/cons.c:3294] ERROR: enforcing method of constraint
>> handler
>> >>>>    > <cycle-elimination> for relaxation returned an invalid result 1
>> >>>>
>> >>>> the problem is that the enforcement method of the cycle-elimination
>> >>>> constraint handler returned SCIP_DIDNOTRUN as a result, which is not
>> >>>> valid. The minimal thing enforcement needs to do is to check whether
>> the
>> >>>> corresponding solution is feasible and thus return SCIP_FEASIBLE or
>> >>>> SCIP_INFEASIBLE. It can also do something to resolve infeasibility or
>> >>>> more, which should then result in some more status codes:
>> >>>> https://www.scipopt.org/doc-7.0.1/html/CONS.php#CONSENFOLP
>> >>>>
>> >>>> Since you seem to have a relaxation, maybe the problem is in the
>> >>>> ENFORELAX implementation of your constraint handler. The least the
>> >>>> constraint handler has to do is to confirm that your relaxation
>> solution
>> >>>> is indeed feasible.
>> >>>>
>> >>>> Stefan
>> >>>>
>> >>>>
>> >>>> On 12/7/20 3:51 PM, Renato Melo wrote:
>> >>>>> Hi everyone,
>> >>>>>
>> >>>>> I am implementing a branch-and-cut model using C++ with SCIP 6.0.1.
>> I
>> >> am
>> >>>>> using a relaxation handler to find lower bounds for a minimization
>> >>>> problem.
>> >>>>> The idea is providing only the lower bound value, not a relaxed
>> >> solution.
>> >>>>> Therefore, I was only updating the '*lowerbound' pointer on the
>> >> RELAXEXEC
>> >>>>> callback. However, when my relaxation finds a lower bound value
>> equal
>> >> to
>> >>>>> the problem's optimal objective value, the branch-and-cut ends with
>> a
>> >>>>> solution greater than the optimal. I have no idea why this is
>> >> happening.
>> >>>>>
>> >>>>> - It can be because I am not providing a relaxed solution?
>> >>>>>
>> >>>>> I tried to provide a relaxed solution that I know is optimal (for a
>> >>>>> restricted case of the problem). To do this, I am setting the values
>> >> one
>> >>>> by
>> >>>>> one with SCIPsetRelaxSolVal() and calling SCIPmarkRelaxSolValid() to
>> >>>> inform
>> >>>>> SCIP that the solution is complete and valid. In this case, if I set
>> >> the
>> >>>>> "includeslp" argument of SCIPmarkRelaxSolValid() as FALSE, nothing
>> >>>> changes,
>> >>>>> and SCIP continues cutting off the optimum. When I set the
>> "includeslp"
>> >>>>> argument to TRUE, I get the following error:
>> >>>>>
>> >>>>> [src/scip/cons.c:3294] ERROR: enforcing method of constraint handler
>> >>>>> <cycle-elimination> for relaxation returned an invalid result 1
>> >>>>>
>> >>>>> However, I am sure that there are no cycles in the given solution.
>> That
>> >>>> is,
>> >>>>> the solution is feasible.
>> >>>>>
>> >>>>> I followed the Relaxator example (
>> >>>>> https://www.scipopt.org/doc/html/RELAXATOR_MAIN.php) to implement
>> my
>> >>>>> relaxation and add a relaxed solution to SCIP's data structure. The
>> >>>>> priority is -1, and the frequency is 1.
>> >>>>>
>> >>>>> Have you some suggestions about what I can do?
>> >>>>>
>> >>>>> Best regards,
>> >>>>> Renato
>> >>>>>
>> >>>>>
>> >>>>> _______________________________________________
>> >>>>> Scip mailing list
>> >>>>> Scip at zib.de
>> >>>>> https://listserv.zib.de/mailman/listinfo/scip
>> >>>>>
>> >>>>
>> >>>>
>> >>>
>> >>
>> >>
>> >
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20201212/9e36809a/attachment.html>

More information about the Scip mailing list