# How do you proceed if your milp is not solvable

We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical).

We went with a very simple aproach (make a cube person x visit x Time and add constraints from here on). Our solution works well if the problem is solvable.

Our customer needs a solution with alternative options if the problem is not solvable, for example "here is a possible solution with X more people" or "a solution with 2 hours more worktime".

Our initial thoughts were to extend our people / time cube by a given number of cells and then add high penalty values to our goal function for these values.

Does anyone have a better idea / knows what is common practice?

• That sounds like a plausible approach. Is there a reason why you have rejected it? When you ask for something "better", can you clarify how you would measure "better"? Better in what respect? What's the primary shortcoming of the solution you already have in mind?
– D.W.
Apr 23 '18 at 19:22
• I don't have much experience in this field and google doesn't really help me out with this kind of question, so my question is if this approach is a "good"/ performant way to solve the problem or if there are better "best-practices". The primary shortcoming is to add another thousand variables / constraints and make the problem bigger. And it's still not guaranteed to find a solution this way Apr 23 '18 at 19:30
• OK. Well, the way to find out whether the performance is acceptable is to try it yourself and see. We can't tell you that (and certainly not with the amount of information here). Help us help you by putting some effort in on your own, try the obvious approaches, see how well they work, report on what you've found in the question, and ask a specific question about how to improve some specific way. There's no reason to expect there to be any "common practice" when you have a special/custom situation like this.
– D.W.
Apr 23 '18 at 23:29

It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following:

# Precision

Typical solvers report solutions as "optimal" using gap parameters specifying relative and absolute differences. Take this CPLEX parameter as an example: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html

You can use this in two ways:

### Sanity tests

If you don't know if your problem is solvable in practice, i.e., constraints are not contradictory in a non-obvious way, just set the precision to lowest possible value and try to solve the problem. The solver should just find anything meeting the constraints practically ignoring the cost function.

Next, when you know that the problem is solvable, you can tighten the constraints. In your example you mention the number of people, first you can start with $x+10$ and if it works you then decrease it to $x+5$ and so on. By doing so you can easily estimate which set of parameters and constraints you can further optimize.

### Practical precision

The question is whether you need the highest possible precision or maybe you can bend the rules and consider using less "optimal" solution. This can highly speed up the calculations, i.e., in my problems I was able to find the solution in seconds instead of hours by switching gap from $0.0001$ to $0.01$ in Gurobi.

# Hard constraints and soft constraints

Common approach is to change some of the constraints to constraints with penalty. For instance, instead of saying that $x < 10$ you say that $x - p < 10$ where $p \ge 0$. Next, you add $p$ to your cost function with big negative multiplier. Such a variable splitting can help finding solutions in case of infeasibility, what's more, if you report the solutions during calculations you can use them to get better approximations of the constraints you can drop to get better results. It looks like this is something you already considered and this is a common approach.

# Presolve

Depending on the type of your problem, you may be able to divide it into multiple phases and calculate the solutions in parallel. Using this method with "sanity tests" method mentioned above you can still have some solution in case when your most wanted model is not feasible.

Example: if you are optimizing for two "realms" (like number of people and number of tasks), try to set some value manually and optimize the other value for that case. By doing this you make the model much easier so you can calculate multiple of them.

# Simplify the model

It sounds easy but in fact can be very hard. Make sure that you don't perform unnecessary difficult operations (like calculating GCD or multiplying variables). Look for easier formulations including constraints moved to cost function (i.e, instead of calculating the minimum of a set and them maximizing it with the cost function, use min-max trick). Make sure that you have smallest possible domains (especially for so-called "big $M$" variables). Also, check your floating point precision.

# Just deal with it

Sometimes you just can't mitigate it, after all it might not be solvable in any acceptable time. You can consider calculating different problem (i.e., completely different approach) or use different algorithm at all (neural nets, simulated annealing etc).