<div dir="ltr"><br>SOLVED!<br>I did what I said, and now it's working.<br><br>Great thanks!</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sat, Dec 12, 2020 at 7:30 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, the relaxator doesn't need to provide a solution.<br>
<br>
108159 is the optimal value in the original problem, but the relaxation <br>
is supposed to work on the transformed problem. At least the bound it <br>
returns should correspond to the transformed problem, i.e., the problem <br>
that SCIP actually solves. So in the relaxator code, it should be<br>
    *lowerbound = SCIPtransformObj(scip, 108159); //pr76<br>
<br>
Stefan<br>
<br>
On 12/11/20 8:47 PM, Renato Melo wrote:<br>
> Thank you again, Stefan.<br>
> <br>
> I will carefully review my constraint handler. Nevertheless, I would prefer<br>
> to provide only a lower bound, not a solution for my relaxation. According<br>
> to the SCIP's documentation, giving a solution is optional:<br>
> "Usually, the RELAXEXEC callback only solves the relaxation and provides a<br>
> lower (dual) bound through the corresponding pointer and possibly a<br>
> solution..."<br>
> <br>
> To illustrate, I forced my situation in the TSP example (<br>
> <a href="https://www.scipopt.org/doc/html/TSP_MAIN.php" rel="noreferrer" target="_blank">https://www.scipopt.org/doc/html/TSP_MAIN.php</a>). In this example, for the<br>
> input tspdata/pr76 the optimum value is *108159*. So, I have included a<br>
> simple relaxation handler that always returns 108159 as a lower bound.<br>
> After doing this, the algorithm ends with a solution of value *108425*,<br>
> which is wrong.<br>
> <br>
> Below we have the constructor and the RELAXEXEC callback methods.<br>
> <br>
> MyDualBound::MyDualBound(SCIP *scip) : ObjRelax(scip,  "my-dual-bound",<br>
>   "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>
> <br>
> On Thu, Dec 10, 2020 at 3:55 AM Stefan Vigerske <<a href="mailto:svigerske@gams.com" target="_blank">svigerske@gams.com</a>> wrote:<br>
> <br>
>> 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]<br>
>> (+0)<br>
>>> +<x_50,4.500000>[B] (+0) +<x_50,6.750000>[B] (+0) +<x_50,9.000000>[B]<br>
>> (+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>><br>
>> 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<br>
>> 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<br>
>> solution.<br>
>>>>> Therefore, I was only updating the '*lowerbound' pointer on the<br>
>> RELAXEXEC<br>
>>>>> callback. However, when my relaxation finds a lower bound value equal<br>
>> 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<br>
>> 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<br>
>> 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<br>
>> 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>
>><br>
> <br>
<br>
</blockquote></div>