Primal Feasibility Report for Infeasible Models

[chelseas]

I would like to be able to call primal_feasibility_report on an infeasible model and get a primal feasibility report.

The docs show calling it on a feasible model....and it returns nothing, which isn't useful. But it would be useful to call it on an infeasible solution and figure out which constraints need to be changed and by how much.

It might be possible to compute this feasibility report using compute_conflict! and some manual reasoning about the constraints, but it seems to me the functionality already exists inside primal_feasibility_report. Is there a way to use the two calls together to get what I want?

[mlubin]

But it would be useful to call it on an infeasible solution and figure out which constraints need to be changed and by how much.

This is precisely what the function does:

julia> model = Model()

julia> @variable(model, x)

julia> @constraint(model, 2x <= 10)

julia> @constraint(model, 2x >= 11)

julia> primal_feasibility_report(var->2.0, model)
Dict{Any, Float64} with 1 entry:
  2 x ≥ 11.0 => 7.0

Given the infeasible solution x = 2, the constraint 2x >= 11 is violated by 7.

primal_feasibility_report only reasons about a concrete solution. It's not the right function for digging into global properties of the model (does a feasible solution exist? how much do I need to modify constraints so that a feasible solution exists?). Methods for answering these questions about global properties depend very much on the problem class and the solvers on hand. Could you share more about what you want?

[chelseas]

I don't want to have to provide an infeasible point if I just solved the problem and it reported infeasible -- shouldn't it have an infeasible point readily at hand already?

[chelseas]

I have been playing around with a variety of solvers including Gurobi, CPLEX and Mosek.

[mlubin]

shouldn't it have an infeasible point readily at hand already?

Not necessarily. Global solvers usually return certificates of infeasibility, not infeasible points. You can call solution_summary to see what the solver is returning. I'd consult the documentation for your favorite solver to be sure of what they recommend for diagnosing infeasibility.

If you're looking for the smallest perturbation of the constraints (under some norm) so that the problem is feasible, you can formulate this as an explicit optimization problem and solve it.

[chelseas]

Ok didn't know that some solvers don't return infeasible points. :/

Oh interesting about formulating it as an optimization problem.... I'm actually looking for the problem to be infeasible as I'm doing satisfiability, but that gives me some ideas. (So like I'm looking to perturb a problem's constraints such that it is infeasible, actually). (But asking the reverse question is also informative)

On Fri, 22 Apr 2022 at 12:42, Miles Lubin @.***> wrote:

shouldn't it have an infeasible point readily at hand already?

Not necessarily. Global solvers usually return certificates of infeasibility, not infeasible points. You can call solution_summary https://jump.dev/JuMP.jl/stable/manual/solutions/#Solutions-summary to see what the solver is returning. I'd consult the documentation for your favorite solver to be sure of what they recommend for diagnosing infeasibility.

If you're looking for the smallest perturbation of the constraints (under some norm) so that the problem is feasible, you can formulate this as an explicit optimization problem and solve it.

— Reply to this email directly, view it on GitHub https://github.com/jump-dev/JuMP.jl/issues/2960#issuecomment-1106806423, or unsubscribe https://github.com/notifications/unsubscribe-auth/ADRQXSQ3DBR2QWDK6ZNU7RLVGL6K7ANCNFSM5UDE6LQQ . You are receiving this because you authored the thread.Message ID: @.***>

-- PhD Candidate Department of Aeronautics and Astronautics Stanford University

[odow]

Ok didn't know that some solvers don't return infeasible points

it's probably the case that most solvers don't return infeasible points, and even if they did, there is no guarantee that the infeasible point is the one with the minimal constraint violation, so it wouldn't be that informative in general.

[blegat]

Some solvers decided not to return the current solution when the problem is infeasible because otherwise, there is a risk of the user using it without checking the status and therefore thinking it's feasible

[odow]

@chelseas is there anything actionable to do here? Do we need to clarify the docs?

[chelseas]

Yeah I think it would be nice to add a sentence to the docs like "your inclination might be to use this with a model that has just been solved and reported infeasible, but this is actually not usually possible because solvers don't usually provide an infeasible solution."

On Mon, Apr 25, 2022, 4:39 PM Oscar Dowson @.***> wrote:

@chelseas https://github.com/chelseas is there anything actionable to do here? Do we need to clarify the docs?

— Reply to this email directly, view it on GitHub https://github.com/jump-dev/JuMP.jl/issues/2960#issuecomment-1109142685, or unsubscribe https://github.com/notifications/unsubscribe-auth/ADRQXSXC3ZLGX43AP7QNOJLVG4UJNANCNFSM5UDE6LQQ . You are receiving this because you were mentioned.Message ID: @.***>

[jd-foster]

If you're already using Gurobi, it has an option to do this auto-magically for you (for bounds and linear constraints); e.g. https://www.gurobi.com/documentation/9.5/refman/c_feasrelax.html Maybe continue this over on Discourse if you run into any usage issues?

[odow]

I've tagged this as a documentation fix. Clarifying the infeasible situation is reasonable. primal_feasibility_report(model) is intended for cases in which the solver reports a primal feasible point, but there may be numerical infeasibilities to some tolerance.