An efficient way to verify the feasibility of provided solution

[chenzjames]

Hi,
I am looking for an automatic way to to verify whether a solution is feasible or not to a built up model, especially for model with a large number of constraints.

I am thinking of defining a function whose input is a possible solution of decision variables, then copying all constraints defined in the built up model and associating each of them with a flag or boolean. The final output will be the union of all flags, which indicates the feasibility of the input solution.

Is there any other quick way? Or is it already provided by JuMP but I could not find it.

Thanks, all.

[mlubin]

We don't currently have a tidy way to do this. Maybe most general current approach would be to use the MathProgBase interface to write a "solver" which collects all the problem data in matrix form (for LP/QP/conic models) and checks feasibility that way.

[chenzjames]

Oh, I see. I will check with MathProgBase. Thank you.

[gdowdy3]

@chenzjames, did you figure out how to implement an efficient check of feasibility? If so, would you mind sharing some of the details?

[chenzjames]

Sorry, not yet.

…

On Sat, 14 Jan 2017 at 21:43, gdowdy3 ***@***.***> wrote: @chenzjames <https://github.com/chenzjames>, did you figure out how to implement an efficient check of feasibility? If so, would you mind sharing some of the details? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#693 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AQqbD_kEoXMML8Q9xyEfXZIsj2TTH6tPks5rSNELgaJpZM4HqruI> .

[gdowdy3]

Alright, I've got a solution. It may not be the most efficient computationally, but it is relatively easy to implement. Suggestions for improvements are welcome.

Suppose your model "m" has a vector of decision variables x defined by

@variables(m, x[1:n])

and a bunch of constraints defined by lines of the form

@constraint(m, ...)

Suppose you've got another vector z which you want to test for feasibility. You can do this by:

(1) adding constraints fixing the values of x, like so

for i = 1:n
    @constraint(m, x[i] == z[i])
end

(2) setting the objective function to zero, like so

@objective(m, Min, 0)   # it doesn't matter whether you use Min or Max

(3) and calling the solver, like so

status = @solve(m)

If the status is :Optimal, then z is a feasible solution to your problem. On the other hand, if the status is :Infeasible, then z is not a feasible solution.

Note that this procedure could potentially give erroneous results because of numerical imprecision.

If you are trying to check the feasibility of a solution x returned by the solver, you need to insert a step (0):

(0) extract the numerical values of the solver's solution, like so

z = zeros(n)
for i = 1:n
    z[i] = getvalue(x[i])
end

If the decision variables are supposed to be binary, it's a good idea to round in this extraction process:

z = zeros(n)
for i = 1:n
    z[i] = round(Int, getvalue(x[i]))
end

[chenzjames]

@gdowdy3 I see. This should work well! Thank you very much!!! @gdowdy3

[adowling2]

I put together a simple Julia package to help with this type of model diagnostics. Suggestions, comments and bug reports are welcome.
https://github.com/adowling2/DegeneracyHunter.jl

[joaquimg]

@blegat maybe you can highlight here the internal MOI functions that could be used for computing value of constraints.
If I understand well the current idea is to write a FeasibilityChecker::ModelLike that could get a model and a Array\Dict with a mapping from variables to values. Then it would be easy to query function values. Even duals could be computed in the future for some problem classes...

[blegat]

You should get the function with the ConstraintFunction attribute and then use MOI.Utilities.eval_variables