[SCIP] Cutting off the optimum when using relaxation handler

Sat Dec 12 11:30:07 CET 2020

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
>>>>>
>>>>
>>>>
>>>
>>
>>
> 