Support Constraints in MILP

[mohammadreza chamanbaz]

Hello

In LP or Convex programming, we can find the support constraints (or at least active constraints) by looking at the dual variables. Now, the question is how to find support (or at least active) constraints in a MILP or in general in a mixed integer convex programming?

Regards,
Mohammadreza

[Johan Löfberg]

why complicate matters with the dual? Simply look at the constraint function and see if they are active. Either manually, or by using the function check

[mohammadreza chamanbaz]

Thanks for the reply. Indeed for the continuous problems (e.g. LP or convex problems), I can easily use check to see which constraints are active. But, for the mixed-integer case, the solution does not necessarily happen on the constraints. Please see the attached figure. This is a simple integer programming (the same argument applies to mixed integer case). The solution is not located on the constraints. Hence, if I check the constraints, non of the them are active at the solution.

[Johan Löfberg]

so what do you want to do then? duality is not used in milp programming as there is no such well defined concept. if you have no active constraints, well then you have no active contraints so what would you be looking for?

[mohammadreza chamanbaz]

I am looking for the constraints whose removal improves the objective value (support constraints). But, I don't want to do an exhaustive search. I mean I don't want to remove the constraints one by one and see if the resulting problem has smaller objective value or not.

[Johan Löfberg]

I believe that is a very hard problem in the integer case.

some might try to infer info from relaxed lp dual, but that will not be generally valid

https://yalmip.github.io/faq/mipdual/

[mohammadreza chamanbaz]

Thanks!
Then, you believe the only exact approach is to do an exhaustive search?

[Johan Löfberg]

I think you have to simply have to research the topic on proposed strategies