[SCIP] Cutting off the optimum when using relaxation handler

[Stefan Vigerske]

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