Feasible and infeasible solutions

A feasible solution is one that satisfies all linear and non-linear constraints. Each time the OptQuest Engine generates a new set of values for the decision variables it creates feasible solutions for linear constraints.

If a linear constraint is defined using only decision variables, the OptQuest Engine can determine feasibility when it generates a solution, because it has all the information it needs to calculate a value and ensure its feasibility. For example, if the constraint specifies the sum of the decision variables must be <= 100, the OptQuest Engine can evaluate the constraint when it picks a solution. In this case, the OptQuest Engine will never return an infeasible solution. If the OptQuest Engine cannot find any solution that will satisfy this type of constraint, the problem is constraint infeasible and the OptQuest Engine throws a COptQuestException when the COptQuestOptimization::Optimize() method is called.

If a constraint contains user-controlled variables or is a non-linear expression of decision variables, the value of the constraint is calculated after the OptQuest Engine has generated possible solutions. If the constraint has user-controlled variables, the caller must calculate the value of the variable, and then communicate the result of the calculation to the OptQuest Engine. For example, if the constraint is Var1*Result1 >= 500, where Result1 is a user-controlled variable, the caller must calculate the value of Result1 and tell the OptQuest Engine the value.  The OptQuest Engine can then calculate the value of the constraint and determine the feasibility. If the constraint is a non-linear string equation of only decision variables, the OptQuest Engine does not need any additional information to calculate the value of the constraint.

The OptQuest Engine notes whether a solution is feasible or infeasible, and a penalty is assigned to infeasible solutions. A feasible solution is always superior to an infeasible solution.

The objective function and requirements are evaluated at the end of each iteration of the optimization. The OptQuest Engine uses the results of the non-linear constraints (requirements) to determine if a solution is requirement-feasible. If the result of a requirement is within the bounds of the requirement, the result is requirement-feasible. If the result is outside the bounds of the requirement, the solution is requirement-infeasible.

The OptQuest Engine makes finding a feasible solution its highest priority. Once it has found a feasible solution, it concentrates on finding better solutions.

The fact that a particular solution may be infeasible does not imply that the problem itself is infeasible. However, infeasible problems do exist. For example, suppose that in a Job Shop problem a foreman insists on finding an optimal configuration with the following constraints:

drills + grinders <= 4

drills + grinders >= 5

Clearly, there is no combination that will satisfy both of these constraints.

You can make infeasible problems feasible by fixing the inconsistencies of the relationships modeled by the constraints. The OptQuest Engine detects optimization models that are linear-constraint-infeasible and throws a COptQuestException.  If a model is linear-constraint-feasible, the OptQuest Engine will always find a feasible solution and search for the optimal solution (i.e., the best solution that satisfies all linear constraints).

The OptQuest Engine cannot detect requirement-infeasible solutions. An example of a requirement-infeasible problem is:

drills * grinders <=  19

drills * grinders >=  20

If the OptQuest Engine cannot find any feasible solutions, you should check the requirements of the problem for feasibility.

Non-linear constraint and infeasible solutions

The OptQuest Engine may have trouble finding feasible solutions if the bounds on your requirement are tight.  For example, if a risk calculation needs to between .09 and .10, the OptQuest Engine may have trouble finding feasible solutions.  If OptQuest does not find any feasible solutions, consider loosening the restrictions on your non-linear constraints.

 

It is important that the value of a requirement provide a measure that can be used by the OptQuest Engine to determine a distance from feasibility.  A requirement value that indicates a pass/fail condition will not help the OptQuest Engine in its search for solutions since every solution that fails is equally bad.   It is better to assign a range of values to the requirement where a solution that is closer to the bound of the requirement can be treated as superior to a solution whose value is farther away from the bound.