Error Messages/42466

Warning Message

No feasible solution was found for the problem defined using DefineOptimization(..) in Opt_def.

Cause

When attempting to solve an optimization problem, no solution could be found that satisfies all the constraints.

There are two possible causes for this. First, the constraints may themselves be in conflict, so that there in fact is no solution that satisifies all of the constraints. The second possibility is that some solution does exist, but the solver engine was just unable to locate it.

To diagnose this, the first thing you should do is look at the result of OptStatusText(«Opt_def»), which may provide additional information about why the solver engine terminated before a feasible solution was found. For example, it may reveal that a time limit was exceeded before it had found one.

Diagnosing

In LPs, if this occurs and it isn't due to some time limit or maximum search limit being hit, then it is indeed the case that no feasible solution exists -- that your constraints (and bounds) are in mutual conflict. One tool for diagnosing this at this point in the case of LPs is OptFindIIS, which provides a way of locating a minimal set of constraints that is inconsistent, such that if any single constraint is eliminated, the problem becomes feasible.

In non-linear problems, and especially non-convex problems, it is very plausible that the engine simply gave up before finding a feasible solution, so it is hard to generalize. You can try different parameter settings to control the search and lead the search in different directions, or even different solver engines.

To avoid confusion, OptSolution and related functions return Null when the solution is infeasible. However, you can examing the "closest" solution found by the solver for clues by providing an optional parameter: OptSolution(«Opt_def», PassNonFeasible:true ). It isn't always easy to make much sense of why it couldn't do better, but it is something to study for clues.

In non-linear problems, you can add: traceFile:"trace.log" to the DefineOptimization, and then study the resulting log file in a text editor after the the attempted solve. You can immediately see which constraints are unsatisfied (they are marked with {!}), and by seeing how the solve was progressing, you can often identify where the problem was. For linear or quadratic problems, you can attempt using a non-linear solver engine with trace.log by including the «engine» parameter to DefineOptimization -- the benefit being just that you can see how a non-linear engine progresses, which might help to identify which constraints are being problematic.

Another general method for diagnosing infeasibility is to introduce slack terms into each constraint (or into those that you are suspicious of). For example, consider the constraint Ct1:

  f(x) >= c

To introduce a slack term, create:

 Decision Slack_Ct1
 Domain: Continuous(0)

and change the constraint to:

  f(x) + Slack_Ct1 >= c

Since Slack_Ct1 has no upper bound, it is guaranteed that a solution exists that satisfies this constraint. Set up a new DefineOptimization problem that minimizes slack as its objective -- being sure to include the slack terms as decisions:

 DefineOptimization(
    decisions:x,Slack_ct1, Slack_ct2,
    constraints: Ct1, Ct2,
    minimize: Slack_ct1+Slack_ct2)

Solving the slack-problem provides a way of obtaining a feasible solution (to the slack problem), which can then help you identify which constraints are causing the problems (i.e., those constraints that cannot be pushed to zero slack).

Debugging infeasible conditions in optimization formulations is very difficult in general. It is also a situation you tend to encounter often when formulating optimization problems, and is one of the main reasons why building optimization models tends to be difficult.