[SCIP] Cutting off the optimum when using relaxation handler

Renato Melo melo.renatosilva at gmail.com
Fri Dec 11 20:47:00 CET 2020 

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/20201211/34e800f4/attachment.html>

More information about the Scip mailing list