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