How to know which constraint is failing?

[Guillaume]

hello,

I am using the linear solver, and when it does not find a solution I would like to know which constraint is failing (at least one).
I am using the .Net wrapper but the solver does not provide me a lot of information except that it is INFEASIBLE.
Can somebody help me where to find this information? I want to get the info programmatically, not looking into some log files (I don't know how to get them anyway).

[csm...@bytefoods.co]

Hi,

I have often wanted this information as well, it's a very natural question. Unfortunately it's hard to make formal. What does it mean for a constraint to fail? Your linear constraints can be represented by signed planes in some high dimensional space and if there are no solutions then it means the solution subspaces don't have any intersection, so which plane is the "wrong" one? You might be able to associate some notion of the size of the intersection (maybe just empty or not) with each subset of constraint spaces, and take the maximal such subset with non-zero intersection and call everything outside that subset "wrong" or "obstructionist" or "filibusterers" or some other politically charged term.

It gets more complicated if there are solutions but they are just hard to find. The way this distinction manifested in our system is that sometimes the solver returned immediately with no solutions and sometimes it just ran until it timed out. When it returned immediately, I just had to dig thru the log files, which you can turn on by setting some of the parameters that you pass to the solver. In python:

parameters = pywrapcp.Solver.DefaultSolverParameters()
#        parameters.print_added_constraints = True
#        parameters.print_model = True
 parameters.print_model_stats = True
 parameters.trace_search = True
 parameters.trace_propagation = True

print_model_stats will tell you if you have any a-priori false constraints, like a var x in [0,1] and you say x > 2.

When looking thru the logs I looked at the last thing it tried to do before failing. If you have a debugger, you can actually subclass SearchMonitor and put a breakpoint in the "BeginFail" method. Or if you don't have a ton of constraints you could try putting break points in the "applydecision" and "refutedecision" methods.

A more programmatic approach (still a heuristic) might be to read off the leaves or parents of leaves of the solution tree after failure occurs. Not exactly sure how to do that, but you basically just need to get the solution tree. There's a TreeMonitor class too, that I haven't dug into. You could also programmatically parse the log files...but that seems like changing your own behavior by praying to god.

Anyways, hope this helps. I'm not an expert in this field.

TL;DR; your question isn't really well defined, and if you answer it conclusively it would probably represent a breakthru in this field.

[Guillaume]

I would like to thank you for your detailed answer.
First of all, breakpoints and logs are not an option for me because my goal is not to debug my instance, or-tools solver is working very well and providing the results I need. My goal is to provide a useful message to the user when there is no solution.
Thank you also for pointing me out to the solution tree, although it does not seem easy, it could be a valid option.

I agree that my question is not well defined, but as you say, it is a very natural question, so there is probably a way to define it better. Let me explain my problem a little bit more:
My users have some freight to put into a truck and I am using or-tools to optimize what can be loaded into the truck. When it does not fit, I would like to explain to the user what is the problem. It could be due to the volume of the freight, or its weight, or due to the weight on axles..
So in fact I have, 'good constraints', which represent my input such as the volume and weight of the freight, and 'wrong constraints' which are the one I am interested in when they 'fail', such as the truck capacity or its maximum weight.

What about removing the 'wrong constraints' Ci and using them as objective, like this:
Minimize Sum_i(Oi), subject to the 'good' constraints.
Where Oi is the objective for Ci. For instance if Ci is x-4y<5, then my objective would be Max(0, x-4y-5)
The solution to this minimisation problem should give me the 'failing' constraints that I want by simply taking the ones having Oi!=0 at the solution value.

Of course, now I don't have a linear objective anymore but may be it possible to transform it into something linear? I am really just thinking out loud here and would be happy to have your feedback.

[Sébastien Roy]

Infeasible problems usually are cause by systematic implementation errors in you linear program. If it is an actual infeasibilty and you want to avoid the frustration of ended up with nothing, you have to reformulate you problem model to be feasible by construction. It may mean having a cascade of problems to solve (relax one or many constraints in first phase and make that constraint satisfaction as part of the objective function, then set the optimal value as a new constraint and move on to the next). There are many advantages and disadvantages with such approach.

In practice, it needs a lot of experience with modelling problem and being able to identify the impossible things your .net app users want... and steer them away from it as it does not exists.

[Guillaume]

Just to clarify, there is no error in my implementation. For instance, if you have a command for delivering 1000 liters of milk and your tank capacity is 500 liters, then it is clearly infeasible!
I agree with your suggestion to reformulate the problem by relaxing constraints and putting them in the objective function. However, I am not a linear programming expert, so if you can help me on how to do this, or pointing me to some tutorials, I would be very grateful :)

[Sébastien Roy]

Super hard to do without further info on your model. Linear programming is pretty esoteric so there isn't much web-based info on the topic (unlike some other algorithmic intensive fields out there).

Myself I enrolled to a mathematical programing class from a local University to get kick started and that pretty much did the trick.

[Chris Smith]

You basically want to do like in machine learning. You have an objective function, and you incorporate various terms into it. This is the idea of soft constraints. So for example, take a constraint x < 5 and your objective function maximize(y). Now make it soft: eliminate the constraint and move it into the objective function.

maximize(y + (5 - x))

The idea is if x < 5, then 5 - x > 0 and y + 5 - x > y so you are increasing the objective, which is good. If x > 5, then you are decreasing the objective. There are variations on this, you can add weight to it,

maximize(y + a*(5-x))

and make a larger or small depending on how important you want your constraint to be relative to the rest of the objective. Another variation is to add some sort of decay to it:

maximize(y - exp(x - 5))

This way the solver can't "cheat" the objective by just making x really really negative. One more variation:

maximize(y + min(5 - x, 0))

This tells the objective function to only let the constraint count against the objective, not towards.

Hopefully this gives you an idea how this works.

--
You received this message because you are subscribed to a topic in the Google Groups "or-tools-discuss" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/or-tools-discuss/GgymTwBgMCI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.