2
$\begingroup$

As the title says, what are the tests for optimality or non-optimality I can build into my procedure and code to alert me that the model is going to be infeasible so I need to revise my constraints?

Large models can take a quite a long time to build, run, and solve. Trying to avoid the hassle of running a model if from the getgo it was going to be non-optimal

$\endgroup$
4
  • $\begingroup$ As far as I know, some of the state-of-art solvers contain facilities to do that. For example, feasibility pump, pre-solving, IIS, etc. Would you try them? $\endgroup$ – A.Omidi Oct 26 '20 at 5:45
  • $\begingroup$ @A.Omidi I'm using Python Pulp-or and most of these are personal projects and I don't have access to these solvers. I've used Mosek before and it was the cheapest so I was thinking of it but that's all $\endgroup$ – dassouki Oct 26 '20 at 5:59
  • $\begingroup$ Would you see this link? $\endgroup$ – A.Omidi Oct 26 '20 at 8:07
  • $\begingroup$ Run a solver with s good presolver. If the model is infeasible, it might discover that in a smalll amount of time. if the problem has continuous non-convex constraints, I wouldn't count on it, however. $\endgroup$ – Mark L. Stone Oct 26 '20 at 12:46
3
$\begingroup$

TL;DR: You can do a lot with data QA, but it may not cover everything.


Let's assume that you have written your model "correctly", i.e. there are no typos etc. Then, any infeasibility will come from your data. Therefore it is (very) good practice to perform rigorous data QA checks to make sure what comes in is sensible. For example, say you are looking to staff nurses in a hospital. Then you could check that the number of available shifts each day is greater than the shifts required. This was covered quite nicely in a webinar by Princeton Consultants.

This will catch some of the things. If you want to do more than that, then I suggest that you code up your constraints explicitly. So you use the lower and upper bounds of your variables to check whether it is at all possible to satisfy the constraints. This will catch more, but requires you to keep this list up to date with the model. It is though a good idea if your model building takes a long time.

$\endgroup$
3
$\begingroup$

I don't see any way to avoid spending the time building the model, since you will presumably need something equivalent to a built model to test whether you have a problem with your constraints. Also, if you problem is a feasibility problem (find a feasible solution) rather than an optimality problem (find an optimal solution), I doubt there will be any free lunch to be had.

For a real-world optimization problem (making optimal decisions for an extant system), you might ask the end-user to specify a solution that they know is (or expect should be) feasible. It does not have to be a "good" solution, just a workable one. If you are working with parameter values that have not occurred in the past (for instance, dealing with inventory problems where supply parameters are speculative due to an unprecedented pandemic's disruption of the supply chain), you can at least ask the user for a solution they believe should work given those parameters. Given such a solution, you then plug it into all the constraints and look for violations. If a constraint is violated, either it is wrong, too tight (RHS value needs tweaking), or the user's solution is not in fact feasible. (You might go back to the user, show the infeasibility, and ask for either a different solution or a looser value for any violated constraint.)

$\endgroup$
2
$\begingroup$

Infeasibility may come from:

  1. Data that feed your optimization model.
  2. The constraints defined in your model.

To prevent the troubles implied by 1), you have to check drastically the input data that feeds your optimization model. The goal is to ensure that the input data respect the conditions for which the model is supposed to work properly. This is a common software engineering practice; for details, have a look at the design by contract.

In addition, if you have basic constraints in your model that may lead to basic infeasibilities, then check them before the launch of the resolution. You can catch and then explain these infeasibilities to the users very early and quickly in the optimization process.

To prevent troubles implied by 2), you have to follow a goal programming modeling approach. Many constraints defined by clients are not really constraints but objectives in effect: if the constraint can be satisfied, this is good, otherwise try to make it violated as little as possible. Remind that for operations the "no solution found" answer is useless.

Finally, testing the possible suboptimality of the resolution before the resolution is of course impossible. The only way to make your users happy is to ensure, by extensive testing on realistic input data, that your optimization software output quality solutions in short running times, if possible in minutes. This can be done by carefully choosing the solution technique to tackle your problem efficiently, even if approximately.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.