[SCIP] Cutting off the optimum when using relaxation handler
Renato Melo
melo.renatosilva at gmail.com
Sat Dec 12 21:01:25 CET 2020
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/9b2dace1/attachment.html>
More information about the Scip
mailing list