Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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
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.
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.)
Infeasibility may come from:
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.
