[SCIP] constraint handler where initial linear constraints are satisfied in CONSCHECK

[Kamp, Dominik]

Hello Ross, hello Marc,

maybe it is not related, but I would like to add that there was a recent fix of a potential bug in the checking procedure, which especially applies for heuristic trivial.

Formerly, the original constraints were checked here, which could in principle lead to violated original bounds since the solution is constructed to satisfy the transformed bounds only. Now, the transformed constraints are checked, so that the solution is guaranteed to be feasible for the transformed problem before it is retransformed to the original problem.

Nevertheless, original constraints should not be violated in either way, but checking out the latest bugfix release is definitely worth a try.

Best regards,

Dominik

> Am 28.11.2023 um 18:54 schrieb Marc Pfetsch <pfetsch at mathematik.tu-darmstadt.de>:
> 
> 
> 
> Hi Ross!
> 
>> Before presolve begins, the trivial heuristic is generating solutions that are integer but do not satisfy the linear constraints (e.g. I get all variables = 1).  On these invocations, checklprows=true, so I guess it is my responsibility to check LP feasibility?
> 
> Note that this refers to the rows in the LP, which is not necessarily the same as the linear constraints, since not every linear constraint might be represented in the LP. This flag signifies that you should not always expect that the rows are satisfied.
> 
> > It surprised me that
>> this could happen, because my check priority was lower than linear constraint. If I just return FEASIBLE when checklprows=true, then I am not getting a final chance to check again after the linear constraints have been checked.
> 
> From looking at the code (SCIP 8), there are two cases:
> 
> - completely = FALSE: In this case your code will only be called if all other constraint handlers returned `SCIP_FEASIBLE`. Thus, you can assume that linear constraints are satisfied if your code is called (although the LP rows might not be satisfied if certain user specified cuts have been added).
> 
> - completely = TRUE: In this case all constraint handlers always are called. This option is only used to output the reasons of infeasibility, so it is not that relevant what you do.
> 
> 
> I do not recall whether we changed something in the process of checking between SCIP 7 and 8.
> 
> 
>> The only mitigation I can come up with is to write the extra code to check that the linear constraints are satisfied myself. In the context of TSP, this is easy enough, as I know what my degree constraints are and don't need to traverse the SCIP model.
>> However, the actual problem I am working on is solver independent callbacks in MathOpt (part of Google's OrTools). The API we expose is similar to Gurobi, there are callbacks at MIP_NODE, where the solution is fractional (but meets all linear constraints) and you can optionally add cuts or lazy constraints, and a second callback on MIP_SOLUTION where the solution is integer and meets all linear constraints from the original model. In the latter case, you must add a violated lazy constraint if one exists, otherwise the solution is interpreted as feasible. Given that the user gets a single callback, rather than adding many small constraints as in SCIP, there isn't really any performance reason not to check the linear constraints for them, and this simplifies their job.
>> To get this API to work, it seems like I would need to iterate over all the linear constraints in the model inside of CONSCHECK whenever checklprows is true. I was hoping there was a better way to do this, as this doesn't really seem like what I should be doing (the constraint handlers don't talk to each other generally in SCIP AFAIK).
> 
> Yes, this would be cumbersome and it should not be necessary given the information above.
> 
>> Note that if I disable heuristics, then everything seems to work, at least on my examples (the docs say that CONSCHECK is invoked by the heuristics).
> 
> Yes, indeed.
> 
> 
> What you could do is to run the code in debug mode and set a break point at the SCIPtrySol() calls in heur_trivial. If you then follow the code, you will probably land in scip_sol.c:checkSolOrig(). It then should first check the linear constraints first, which should return "SCIP_INFEASIBLE" causing the process to stop.
> 
> It might be that your linear constraints are not checked correctly.
> 
> Best
> 
> Marc
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip