Constraint Feasibility Checks & Actions

[pedromxavier]

When generating penalty functions for constraints like $$a x + b \le 0$$ i.e. $$g(x) \le 0$$ one might go for $$\rho_k (g_k(x) + s)^{2} = 0, g(x) \in \text{PBF}$$ to compose the objective function.

As it is expected from PBF's that go $$ g: \mathbb{B}^{n} \to [a, b] $$, we can compute $$ [l, u] $$ such that $$ [a, b] \subseteq [l, u] $$ which gives us checks on wheter the function is infeasible or even always feasible. Tests against MOI's Knapsack were successful in detecting this case.

The question is: what to do when such things happen?

My first suggestion is:

# -*- Bounds & Slack Variable -*-
l, u = PBO.bounds(g)

s = if u < zero(T) # Always feasible
    @warn "Always-feasible constraint detected"
    continue
elseif l > zero(T) # Infeasible
    @warn "Infeasible constraint detected"
    error()
else
    VM.expansion(VM.encode!(VM.Binary, model, nothing, zero(T), abs(l)))
end

Although, I also suggest for continue and error() to be triggered by flags such as :ignore_feasible and :error_infeasible. Setting MOI termination status seems appropriate in the latter.

[bernalde]

I agree with you in resulting as an infeasible problem if we are able to detect it soon enough without even passing it to the solver. If the constraint is always feasible, we might as well remove it from the original problem.

[pedromxavier]

Some experiments might want weird constraints to be added. I know one that has been implemented for my Final Project (from SAT-like formulations) that relies on a weaker never-satisfiable constraint and a stronger one. There might be other cases like this wandering around so keeping flags to control this behaviour seems the right way