Difference between revisions of "Error Messages/42466"

(Created page with "= Warning Message = No feasible solution was found for the problem defined using DefineOptimization(..) in ''Opt_def''. = Cause = When attempting to solve an optimization...")
 
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
= Warning Message =
+
[[Category:Error messages]]
  
−
  No feasible solution was found for the problem defined using [[DefineOptimization]](..) in ''Opt_def''.
+
== Warning message ==
 +
:<code>''No feasible solution was found for the problem defined using DefineOptimization(..) in ''Opt_def''.''</code>
  
−
= Cause =
+
== Cause ==
 +
The Optimizer can find no solution that satisfies all the constraints.
  
−
When attempting to solve an optimization problem, no solution could be found that satisfies all the constraints.
+
One possibility is that the constraints are in conflict, so that there indeed is no solution that satisfies all of the constraints. This is the most usual explanation with LP or QP problems. The other possibility is that some solution does exist, but the solver engine was just unable to locate it. This is quite common for NLPs.
  
−
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 <code>OptStatusText(«Opt_def»)</code>, 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.  
  
−
To diagnose this, the first thing you should do is look at the result of <code>[[OptStatusText]](«Opt_def»)</code>, 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 warning isn't due to exceeding the time limit or maximum search limit, it is likely 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.  
  
−
= Diagnosing =
+
Another possibility is that the solution set is actually unbounded -- i.e. one or more decision variables would be infinite. (Yes, we agree that the message is misleading in this case, but it's what the solver engine provides.) In that case, you can try adding bounds to each decision, and see if that results in a solution.
  
−
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 quite possible that there is a feasible solution, but the engine reached a time limit before finding it. You can try different parameter settings to control the search and lead the search in different directions, or even different solver engines.  
  
−
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: <code>OptSolution(«Opt_def», PassNonFeasible: true)</code>. It isn't always easy to make much sense of why it couldn't do better, but it is something to study for clues.  
  
−
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: <code>[[OptSolution]](«Opt_def», PassNonFeasible:true )</code>.  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: <code>traceFile: "trace.log"</code> 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.  
  
−
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 <code>Ct1</code>:
  
−
Another general method for diagnosing infeasibility is to introduce slack terms into each constraint (or into those that you are suspicious of).
+
:<code>f(x) &gt;= c</code>
−
For example, consider the constraint Ct1:
 
−
  f(x) >= c
 
  
−
To introduce a slack term, create:
+
To introduce a slack term, create:  
−
  Decision Slack_Ct1
 
−
  Domain: Continuous(0)
 
  
−
and change the constraint to:
+
:<code>Decision Slack_Ct1</code>
−
  f(x) + Slack_Ct1 >= c
+
:<code>Domain: Continuous(0)</code>
  
−
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:
+
and change the constraint to:  
  
−
  [[DefineOptimization]](
+
:<code>f(x) + Slack_Ct1 &gt;= c</code>
−
    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).
+
Since <code>Slack_Ct1</code> 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:
  
−
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.
+
:<code>DefineOptimization(</code>
 +
::<code>decisions: x, Slack_ct1, Slack_ct2,</code>
 +
::<code>constraints: Ct1, Ct2,</code>
 +
::<code>minimize: Slack_ct1 + Slack_ct2)</code>
 +
 
 +
Solving the slack-problem provides a way of obtaining a feasible solution (to the slack problem), which can help you identify which constraints are causing problems (i.e., those constraints that cannot be pushed to zero slack).
 +
 
 +
Debugging infeasible conditions in optimization formulations can be a challenging problem, and one that is crops up quite commonly. It is part of what makes optimization fun for those that enjoy a mathematical challenge.
 +
 
 +
==See Also==
 +
* [[DefineOptimization]]
 +
* [[OptSolution]]
 +
* [[OptStatusText]]
 +
* [[OptFindIIS]]
 +
* [[NlpDefine]]

Latest revision as of 01:25, 4 February 2016


Warning message

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

Cause

The Optimizer can find no solution that satisfies all the constraints.

One possibility is that the constraints are in conflict, so that there indeed is no solution that satisfies all of the constraints. This is the most usual explanation with LP or QP problems. The other possibility is that some solution does exist, but the solver engine was just unable to locate it. This is quite common for NLPs.

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 warning isn't due to exceeding the time limit or maximum search limit, it is likely 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.

Another possibility is that the solution set is actually unbounded -- i.e. one or more decision variables would be infinite. (Yes, we agree that the message is misleading in this case, but it's what the solver engine provides.) In that case, you can try adding bounds to each decision, and see if that results in a solution.

In non-linear problems, and especially non-convex problems, it is quite possible that there is a feasible solution, but the engine reached a time limit before finding it. 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 help you identify which constraints are causing problems (i.e., those constraints that cannot be pushed to zero slack).

Debugging infeasible conditions in optimization formulations can be a challenging problem, and one that is crops up quite commonly. It is part of what makes optimization fun for those that enjoy a mathematical challenge.

See Also

Comments


You are not allowed to post comments.