How can I identify the feasible region of solutions for a problem?

[joejenb]

Hi I currently have a simple problem in pysciopt that has no objective function, a mixture of linear and non linear constraints and some continuous and binary variables.

It solves as expected, however, I am primarily interested in finding the constraints/cuts identified whilst solving that must be satisfied in order for a solution to be valid.

What is the best way to do this?

So far I have tried using a cut selector and storing any cuts added. I have also looked at using getConss and selecting constraints added by a separator. However, in both cases I am unsure how to identify which constraints are tightest and must be satisfied for the solution to be valid.

Any help would be greatly appreciated.

[Joao-Dionisio]

Hey @joejenb! To make sure I understand, you want to find out which constraints and cuts are not tight for a specific solution, right?

I don't think there's a single method you can call that does this, but you can check if the LHS and RHS of the constraints are the same. Regarding cuts, I'm thinking it might be possible just to check if the cut's age is zero or not, but not 100% sure this works in PySCIPOpt at the moment.

[joejenb]

Hi @Joao-Dionisio, thanks for the response! Sorry I think I might have been a bit vague in my wording.

My understanding was that as solving progresses some constraints/cuts become redundant i.e the region they rule out is expressed more concisely or with a tighter bound by a constraint/cut added later in the solving process. These redundant constraints/cuts I would like to remove/ignore.

In addition to this I thought (less certain on this) that some constraints/cuts are added to help reach a solution but do not hold for all valid solutions. In other words there are some valid solutions to the original problem for which these constraints/cuts would be violated. If this is the case then I would also want to remove these.

This would ultimately give the subset of constraints/cuts found whilst solving that best define the region of feasible solutions for a problem.

Hope this is slightly clearer and thanks again.

[Joao-Dionisio]

Ah, I see. This is quite a bit more difficult as you're not interested in a specific solution, especially given that some/most of the cuts are only locally valid, given that they may arise from branching decisions. I have to think some more about this.

In the meantime, you can just try to work with the transformed problem you obtain after presolving (but there will be other things like variable aggregation and whatnot that you might want to disable).

For globally valid cuts (which AFAIK only remove solutions from the LP relaxation), there is SCIPgetGlobalCutPool, not yet on PySCIPOpt. Some of these cuts might be redundant, and I don't know how to separate them. One could think of checking whether their age is 0, but this wouldn't work since you want them to be tight for all solutions on the boundary. This is starting to smell like a difficult optimization of its own.