Introduction to optimization

Optimization technology allows analysts to search for optimal solutions to complex business and engineering problems.

The OptQuest® Engine, OptTek Systems, Inc.’s optimization software, enables you to find the best answer to questions such as:

• What is the maximum return on budgets allocated to different uses, given uncertain product demand, machine reliability, and raw material availability?

• What is the most effective configuration of machines for production scheduling under variable conditions of demand and operation?

• What are the most effective location and release sequencing of raw materials to minimize waiting time?

• What are the optimal work force allocations to minimize lead time and labor costs?

• What are the optimal allocations for an investment portfolio?

Investigating every possible scenario can be extremely time-consuming and, in many cases, impossible. The OptQuest Engine replaces the inaccuracy of trial-and-error with a potent search engine that pinpoints the best decision. Users can quickly determine what combination of variables results in achieving their objectives.

How the OptQuest Engine works

The OptQuest Engine incorporates metaheuristics to guide its search algorithm toward better solutions. This approach remembers which solutions worked well and recombines them into new, better solutions. In addition, this technique does not get trapped in local solutions or get thrown off course by noisy (uncertain) model data.

The OptQuest Engine combines Tabu search, scatter search, integer programming, and neural networks into a single, composite search algorithm providing maximum efficiency in identifying new scenarios. OptTek’s well-researched technology has been shown to be orders of magnitude faster than other approaches. The OptQuest Engine is also flexible, intelligent, and easy to use. And, according to experts in the field, it is the most reliable optimization software on the market today.

The OptQuest Engine uses many different heuristics and meta-heuristics to generate new solutions.  The OptQuest Engine’s solution search algorithm has been designed to be a “black-box,” general purpose, global optimization algorithm.  It has been designed to use many heuristics to find a global optimal solution quickly and it is guaranteed to work with all types of problems.  

Using the documentation

The intent of this document is to provide an overview of the features of the OptQuest Engine. Please refer to The Java and .NET OptQuest Engine API documentation included with your version of the OptQuest Engine for detailed information on the classes and methods.

Platforms

The OptQuest Engine optimization software is available in the following formats:

If you need a COM version or if you are interested in a version that works with python please contact optinfo@OptTek.com for more information.

Defining an optimization

The simplest optimization problem contains the following information:

• decision variables

• objective function

• the goal of the optimization (to either minimize or maximize the value of the objective function)

Optimization is an iterative process where:

• The OptQuest Engine calculates possible solutions for the decision variables

• The objective function and constraints are evaluated using the solutions suggested by the OptQuest Engine

• The results are analyzed by the OptQuest Engine and a new set of possible solutions is calculated

The OptQuest Engine

The standard use of OptQuest uses the COptQuestOptimization class and follows a push-based pattern which involves implementing an Evaluate() method to perform evaluation of solutions provided by OptQuest and a MonitorStatus() method to collect solution information at the end of each evaluation cycle. Using this pattern OptQuest pushes a solution out for evaluation and pushes a final solution out to allow a user to make updates in their user interface.

The class COptQuestUserControlledOptimization provides a pull-based pattern for interaction with OptQuest in which the user requests a solution for evaluation using the GetNextSolution() method when ready to perform an evaluation, calls ReturnEvaluatedSolution() when an evaluation is complete, and can use a series of getter methods to request current state of the optimization and make updates to the user interface when desired.

The COptQuestOptimization class allows you to define and run an optimization problem. In the simplest case, you:

• Add decision variable objects to the COptQuestOptimization object

• Add an objective object to the COptQuestOptimization object and set the goal of the optimization (maximize or minimize)

• Extend the COptQuestOptimization class and override the COptQuestOptimization.Evaluate(COptQuestSolution) method. In the Evaluate() method, you calculate the objective value using the solution provided by OptQuest.

  • Display the progress of the optimization by overriding the COptQuestOptimization.MonitorStatus(COptQuestSolution) method to provide feedback on the progress of the optimization.

• Define how long the optimization should run by setting the stop properties of the COptQuestOptimization class

The COptQuestUserControlledOptimization also allows you to add decision variables and define an objective but your application calls COptQuestUserControlledOptimization.GetNextSolution() when it is ready to evaluate a solution and calls COptQuestUserControlledOptimization.ReturnEvaluatedSolution() when the evaluation has completed.

When using COptQuestUserControlledOptimization, you will

• Call COptQuestUserControlledOptimization.BeginOptimization() after you have added decision variables and an objective.

• Call COptQuestUserControlledOptimization.GetNextSolution() to get a solution for evaluation

• Evaluate the solution and call COptQuestUserControlledOptimization.ReturnEvaluatedSolution()

• Call COptQuestUserControlledOptimization.GetCompletedSolutions() when you want to update your user interface.

• Call COptQuestUserControlledOptimization.EndOptimization() when you no longer want new solutions.

For more complex optimizations, you may add constraints to your model. Constraints may be linear constraints or non-linear constraints

You may want to provide solution analysis after the optimization completes.

Defining decision variables

A decision variable is a quantity that the decision-maker controls. For example, the number of nurses to employ during the morning shift in an emergency room may be a decision variable in an optimization model for labor scheduling. The OptQuest Engine manipulates decision variables in search of values that produce the optimal value for the objective function.

Decision variables are added to an optimization problem by instantiating a decision variable and adding the instance to the optimization using the COptQuestOptimization.AddVariable() method.

You can optionally assign a name to a decision variable and the variable names can be used in string expressions for defining a COptQuestStringObjective or a COptQuestStringConstraint. If the variable name contains special characters such as blanks, enclose the variable name in square brackets or curly braces when creating the string expression. For example, “2500*[Machine 1] + 3000 * [Machine 2] <= 100000”.

Defining the range of valid values

You define the range of values for a decision variable by setting the lower bound and upper bound of the variable. It is important to pick meaningful bounds for your decision variables so the OptQuest Engine doesn’t waste time exploring solutions that are not meaningful.

You can further limit the set of valid values by defining a sub-range of values that are excluded as possible solutions for a decision variable. The COptQuestVariable.SetExclusiveRange() method can be used to define a sub-range of values that will be excluded as possible solutions. For example, if your decision variable can have a value between 0 and 1 but not between 0 and .25, you would set the low bound to 0, the high bound to 1and an exclusive range of 0 and .25. Any value > 0 and < .25 would be excluded.

Multiple exclusive ranges can be defined on one decision variable.

The OptQuest Engine supports the following type of decision variables.

Defining user-controlled variables

User-controlled variables are variables that are involved in an optimization problem, but their values are set by you rather than the OptQuest Engine. The value for a user-controlled variable may be the result of a calculation that involves one or more decision variables or it may be the output of a simulation. User-controlled variables can be used to define objectives or constraints.

User-controlled variables are added to an optimization problem by instantiating a COptQuestUserControlledVariable and adding the instance to the optimization with the COptQuestOptimization.AddVariable() method.

The values of user-controlled variables should be set by you in the COptQuestOptimization.Evaluate(COptQuestSolution) method. Use the COptQuestSolution.SetVariableValue() method to assign a value to the solution given to you by the Evaluate() method.

You can optionally assign a name to a user-controlled variable and the variable names can be used in string expressions for defining a COptQuestStringObjective or a COptQuestStringConstraint. If the variable name contains special characters such as blanks, enclose the variable name in square brackets or curly braces when creating the string expression. For example, "[Risk Factor] <= .10;"

Defining the objective

Optimization is the process of searching for the values of the decision variables  that provide a maximum or a minimum value of the objective.

The objective is added to an optimization problem by instantiating an objective object and adding the instance to the optimization using the COptQuestOptimization.AddObjective() method.

Defining constraints

You define a constraint using the COptQuestStringConstraint class which allows you to define the constraint as a mathematical string expression.
See String Expressions.

OptQuest will not return a solution that violates a linear constraint. If a constraint is a non-linear constraint, solutions that violate the non-linear constraint will be marked as infeasible.

If the expression includes user-controlled variables, you set the values of the user-controlled variables in the COptQuestOptimization.Evaluate(COptQuestSolution) method. The OptQuest Engine will calculate the value of the expression using the values you supplied and determine the feasibility of the constraint.

It is important that the value of a non-linear constraint provide a measure that can be used by the OptQuest Engine to determine a distance from feasibility. A constraint 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 non-linear constraint where a solution that is closer to the bound of the constraint can be treated as superior to a solution whose value is farther away from the bound.

If you want to know if a constraint is linear or non-linear, you can call the method COptQuestStringConstraint.IsLinear().

If you want to know if a constraint is feasible, you can call COptQuestSolution.IsConstraintFeasible(COptQuestStringConstraint).

Numeric values in constraints should not contain a group separator. Enter the value 300000.25 rather than 300,000.25.

String expressions

The COptQuestStringConstraint and COptQuestStringObjective classes allow you to define a constraint or an objective using a string to define a mathematical expression. To use this capability, you must provide unique names for decision variable and user-controlled variables that are added to the optimization using the COptQuestOptimization.AddVariable() method.   When the mathematical expression is parsed, the variable names are used to locate the decision variable or user-controlled variable and retrieve the value used to evaluate the expression.

The following are examples of valid string expressions defining an objective function. An objective function expression cannot use the operators =, <=, >=.

Var1 + 3*Var2

250*exp(Var1 + 0.67*Var2)

The following are examples of valid string expressions defining a linear constraint. Constraint expressions must use at least one of the operators =, <=, >=. The < and > operators are not supported by OptQuest and are treated as <=, >= operators if used.

Var1 + 3*Var2 = 200

500 <= Var1 – Var2 + 3*Var3 10 <=  600

Var1 + Var2/10 >= 5

The following are examples of valid string expressions defining a non-linear constraint:

Var1*3*Var2 >= 600

max(Var1,Var2) <= 30

Constraint expressions can also use the “or” keyword to define a logical or constraint. More than one “or” can be used creating multiple or clauses. There is no need group or clauses with parantheses since the order of evaluation does not change the result.

Var1*3*Var2 >= 600 or max(Var1,Var2) <= 30

An equation string may use the mathematical operators of +, -, *, and / and the functions described in the table below.  You can use parentheses to enforce the order of evaluation.

The variable names in the constraint equation must match the names of variable objects added to the COptQuestOptimization object. The constraint expression is not evaluated until optimization begins, so a constraint string can reference a variable that has not yet been added to the problem. Any characters enclosed in square brackets or curly braces are treated as a variable name. For example, [Machine 1] is treated as a variable name and the OptQuest Engine will locate a variable with the name “Machine 1”.

A COptQuestStringConstraint defines a linear constraint if the mathematical expression of the string constraint is a linear expression of decision variables. A COptQuestStringConstraint defines a non-linear constraint if the mathematical expression of the string constraint is a non-linear expression of decision variables or contains user-controlled variables. To use a string constraint to define a non-linear constraint, instantiate a COptQuestStringConstraint object and set the string expression using the COptQuestStringConstraint.SetEquation() method. Use the COptQuestOptimization.AddConstraint() method to add the non-linear constraint to the optimization.

Checking string expressions

The OptQuest Engine will validate all string expressions when the COptQuestOptimization.Optimize() method is called.  If any errors are found, a COptQuestException will be thrown. All named decision variables and named user-controlled variables that are used in a COptQuestStringConstraint or COptQuestStringObjective must be defined before the string expressions can be validated.

You can check string expressions for syntax errors before starting the optimization by calling the COptQuestStringConstraint.CheckExpression() or COptQuestStringObjective.CheckExpression(). To use the CheckExpression() method, you must add the decision variables and the COptQuestStringConstraint or COptQuestStringObjective to an instance of the COptQuestOptimization class. If the expression contains errors, a COptQuestException is thrown. The exception will give detailed information on the error.

The OptQuest Engine also allows you to check a constraint string expression or an objective string expression for linearity.  COptQuestStringConstraint objects and COptQuestStringObjective objects are always checked for linearity when the COptQuestOptimization.Optimize() method is called. The IsLinear() method provides a way to check expressions and report linearity before the optimization begins.

You can use the following functions when defining string expressions.

Defining stop criteria

You control how long an optimization will run by setting stop criteria. If more than one stop criteria are specified, the optimization stops when any one of the criteria is satisfied. An optimization can also be stopped at any time by calling the COptQuestOptimization.StopOptimization() method.

Running the optimization

The optimization is run by calling the COptQuestOptimization.Optimize() method.

The Optimize() method performs the following functions:

• Checks all string expressions, making sure the variable names in the expression refer to a named variable that was added to the problem and the expression is syntactically correct. If any errors are detected, a COptQuestException is thrown.

• Checks the set of linear constraints for constraint feasibility. If no feasible solution exists, a COptQuestException is thrown.

• The OptQuest Engine checks that at least one stop option has been specified.

Linearity and String Expressions

The OptQuest Engine will analyze a problem and pick the best method for solving the problem. If a problem has linear constraints and a linear objective, OptQuest will use linear programming to generate the first solution. This solution will have the best objective value. OptQuest will continue to generate solutions using metaheuristics. Although the first solution will give the best objective value, other solutions are available for solution analysis.

When the optimization completes

If the optimization terminates because of an error, a COptQuestException will be thrown.  You can use COptQuestException methods to determine the error condition.  Be sure to put a try/catch block around your call to the COptQuestOptimization.Optimze() method.  Any error in the problem setup will throw a COptQuestException.

The method COptQuestOptimization.GetTermnationReason() will return an integer value representing the termination reason.  The method COptQuestOptimization.GetTermnationReasonString() will return a text string describing the reason the optimization terminated.    

To retrieve the best solution, call the COptQuestOptimization.GetBestSolution() method.  You can use COptQuestSolution methods to retrieve information about the best solution such as the value of each decision variable and the objective.  Use the COptQuestSolution.IsFeasible() method to check the best solution for feasibility.  A feasible solution satisfies all linear and non-linear constraints. To retrieve the best N solutions, call COptQuestOptimization.GetNthBestSolution(int)where the parameter identifies the order of the solution. If the parameter is 1, the best solution is returned, 2 the second best solution etc.

The following table describes the reasons an optimization terminates.

Running additional iterations

The OptQuest Engine supports running additional iterations after the initial optimization has completed. The OptQuest Engine will suggest a new solution for each additional iteration continuing the search begun in the initial optimization.

To run additional iterations, call the COptQuestOptimization.SetAdditionalIterations() method specifying the number of additional iterations to be run. Call the COptQuestOptimization.OptimizeAdditional() method to continue the optimization for the additional iterations. The COptQuestOptimization.Evaluate(COptQuestSolution solution) method will be called for each additional iteration.

You can also specify an additional number of seconds to run by calling the COptQuestOptimization.SetAdditionalTime() and specifying the number of seconds to run. Call the COptQuestOptimization.OptimizeAdditional() method to continue the optimization for the additional time. The COptQuestOptimization.Evaluate(COptQuestSolution solution) method will be called for each additional iteration.

This process can be repeated any number of time.

Pause and continue

This COptQuestOptimization.ContinueOptimize() allows you to continue an optimization that was stopped before all iterations were completed or while there was time remaining. The method will resume the optimization where it left off.

If you set additional iterations after stopping the optimization, the additional iterations are added to the remaining iterations. If you set additional time, the additional time is added to the remaining time.

Multi-objective optimization

Practical optimization problems often involve multiple conflicting objectives. For example, in a portfolio optimization problem it is desirable to both maximize expected return and minimize risk; in a supply chain planning problem it is desirable to minimize both unmet demand and excess inventory.

The OptQuest Engine supports multiple objectives, allowing the analyst to view and explore the trade-offs between objectives. For example, consider an optimization problem faced by a small specialty retailer in which the retailer would like to maximize profit while also keeping a large selection of products. Imagine this graph represents the trade off between these objectives.

For the retailer, profit is highest with a low selection of high-margin products. Initially the curve is flat, and selection can be added without a large dip in profit (Region A). After a certain point when the retailer can no longer take advantage of economies of scale (due to limited stock room), profit dips more sharply (Region B) . With this complete description of the trade space, an analyst can make an informed decision about how much immediate profit to trade for increased selection (which may drive longer-term profit due to greater customer satisfaction).

OptQuest gives a complete picture of this multi-objective trade space, which we call the pattern frontier, and which is also known as the Pareto frontier in the Optimization literature. The frontier points are the solutions for which no improvement can be made in one objective without making another objective worse.

Frontier multi-objective optimization

The OptQuest Engine supports the ability to take a complete look at the multi-objective trade space, defined as the pattern frontier.The OptQuest engine automatically searches for the points on this frontier without the user having to guide the search in any way. The OptQuest Engine performs a search for the optimal value for each objective (without concern with the other objectives), and then works to build the frontier with the goal of filling in any gaps. As the search progresses, the frontier points can be retrieved from the OptQuest Engine and used to plot and display both the objectives and the underlying variable values. This allows the analyst to make informed decisions, evaluating the trade-offs between the different objectives.

To define a multi-objective pattern frontier optimization, instantiate each sub-objective (COptQuestUserControlledObjective or COptQuestStringObjective) and then add the sub-objectives to an instance of COptQuestFrontierMultiObjective.  Each sub-objective is evaluated in the same manner as a simple objective: it has a direction (minimize or maximize) and its value is set by the user or the OptQuest Engine.

OptQuest Engine Setup

To set up a multi-objective pattern frontier problem, use the class COptQuestFrontierMultiObjective to define the pattern frontier objectives. To add objectives to a COptQuestFrontierMultiObjective, use the method COptQuestFrontierMultiObjective.AddObjective() for each objective of the frontier objective. The objectives added to the COptQuestFrontierMultiObjective can be COptQuestUserControlledObjective or COptQuestStringObjective.

In the Evaluate() method, set the value for each COptQuestUserControlledObjective that is used as a sub-objective of the COptQuestFrontierMultiObjective using the method COptQuestSolution.SetObjectiveValue(COptQuestObjective obj, double value). For each COptQuestStringObjective, set the value of each COptQuestUserControlledVariable used in the string expression.

To retrieve the solutions on the frontier use the method COptQuestOptimization.GetPatternFrontier()

Sample Code

The following is a simple example optimization problem with one variable and two objectives that demonstrates the use of pattern frontier optimization.

// Setup of variables, constraints, and optimization

COptQuestContinuousVariable x = new COptQuestContinuousVariable(0, 10);

COptQuestObjective objective1 = new COptQuestUserControlledObjective();
objective1.SetMaximize();
COptQuestObjective objective2 = new COptQuestUserControlledObjective();
objective2.SetMinimize();

COptQuestFrontierMultiObjective frontierMultiObjective = new COptQuestFrontierMultiObjective();
frontierMultiObjective.AddObjective(objective1);
frontierMultiObjective.AddObjective(objective2);

ExampleOptimization optQuest = new ExampleOptimization();
optQuest.AddVariable(x);
optQuest.AddObjective(frontierMultiObjective);

// run the optimization
optQuest.Optimize();

// grab all solutions on the pattern frontier (the multi-objective trade space).
ArrayList<COptQuestSolution> frontier = optQuest.GetPatternFrontier();


// examine, plot, etc the points on frontier. For example, to access the value of objective1
// for (say) the first frontier point, use
double obj1Value = frontier.get(0).GetObjectiveValue(objective1)

// required optimization class that extends COptQuestOptimization and implements Evaluate()
public class ExampleOptimization extends COptQuestOptimization {
    public void Evaluate(COptQuestSolution solution) throws COptQuestException {
        // run a simulation here to obtain values for objective1 and objective2,
        // based on the decision variables provided by OptQuest, and obtained using
        // the method solution.GetVariableValue(x))
        solution.SetObjectiveValue(objective1, <objective1 value provided by user>);
        solution.SetObjectiveValue(objective2, <objective2 value provided by user>);
    }
}

Analyzing results

Solutions

The COptQuestSolution object contains the information about a particular solution. When the OptQuest Engine creates a solution, it sets the values for the decision variables.  When a solution is evaluated, the objective value and user controlled variable values are set.  

If you are calculating the objective value or setting the values of user controlled variables, you will need to override the COptQuestOptimization.Evaluate(COptQuestSolution solution) method. Use the COptQuestSolution methods to retrieve the values for decision variables and set the values of the objective function and user controlled variables.

Before a solution is evaluated, it contains:

• The value for each decision variable

• The iteration that created the solution

To retrieve information after a solution has completed evaluation, override the COptQuestOptimization.MonitorStatus(COptQuestSolution) method.  The solution parameter is the solution that just completed evaluation.  If you are tracking the progress of the optimization, MonitorStatus() is the place you should retrieve the best solution found thus far.  After a solution has completed evaluation, it will contain:

• The value for each decision variable

• The iteration that created the solution

• The feasibility of the solution

• The value of the objective

• The value of user controlled variables

• Replication information if replication processing is being used.

Feasible and infeasible solutions

A feasible solution is one that satisfies all constraints.

Each time the OptQuest Engine generates a new set of values for the decision variables it creates feasible solutions for all linear constraints. If the OptQuest Engine cannot generate any feasible solutions for the linear constraints, the OptQuest Engine will throw a COptQuestException.EXCEPT_CONSTRAINTINFEASIBLE when the COptQuestOptimization.Optimize() method is called.

If the OptQuest model contains non-linear constraints, a solution may violate one or more of the non-linear constraints. The OptQuest Engine uses the results of the non-linear constraints to determine if a solution is constraint feasible. If the result is within the bounds of the constraint, the result is feasible. If the result violates the constraint, the solution is infeasible. Feasibility is determined when a solution is returned to OptQuest.

The OptQuest Engine assigns a penalty to infeasible solutions. A feasible solution is always superior to an infeasible solution.

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

There is no combination that will satisfy both of these linear 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).

If the model contains non-linear constraints that have no valid, feasible solution, OptQuest will run until the stop criteria is met but all solutions will be infeasible. An example of an infeasible problem that contains non-linear constraints is:

drills * grinders <= 19

drills * grinders >= 20

Non-linear constraint and infeasible solutions

The OptQuest Engine may have trouble finding feasible solutions if the bounds on your constraint 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 constraint provide a measure that can be used by the OptQuest Engine to determine a distance from feasibility. A constraint value that indicated 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 constraint where a solution that is closer to the bound of the constraint can be treated as superior to a solution whose value is farther away from the bound.

Sorting solutions

The OptQuest Engine provides methods for you to retrieve solutions using an iteration counter or you can retrieve solutions ordered from best objective value to worst objective value.

Sorting infeasible solutions

Sorting infeasible solutions using the objective value may not be very informative since the objective value for an infeasible solution may not be anywhere near the objective value for a feasible solution.  You can ask OptQuest to sort infeasible solutions using an infeasibility index where a solution that is close to feasibility is considered better than one that is farther away.  The default sorting uses the objective value.  To use the infeasibility index for sorting infeasible solutions, call COptQuestOptimization.SetUseInfeasibilityIndex(true).    

Note that this feature only affects sorting of infeasible solutions.  Feasible solutions are always sorted using their objective value.  If your user interface plots the optimization progress by displaying the objective value for each iteration, you may see the objective value bounce around while OptQuest searches for a feasible solution.

The following COptQuestOptimization methods allow you to retrieve a solution.

Solution sets

The COptQuestSolutionSet class allows you to select a set of solutions and perform statistical analysis or sensitivity analysis on the set.  Solutions are selected using a filter that you implement via the ISolutionFilter interface.   You provide an implementation for the ISolutionFilter.IncludeInSet() method.

A COptQuestSolutionSet object is created by calling COptQuestOptimization.CreateSolutionSet().  A filter is added by the COptQuestSolutionSet.SetSolutionFilter() method. The solution set is loaded by the COptQuestSolutionSet.LoadSolutionSet() method where you specify the number of solutions you want in the set and how you want the solutions to be ordered.  Ordering can be based on the iteration counter, Nth best sorting or unordered. The ISolutionFilter.IncludeInSet() method is called for each solution until the set contains the number of solutions you requested or all solutions have been checked.

The COptQuestSolutionSet class provides methods to calculate statistics on any variable in the problem or the objective using the solutions in the set.  You can also use the solution set to do your own customized calculations.  

Simulation optimization

In order to add optimization to your simulation package, you must be able to:

• Identify the simulation objects that you want OptQuest to manipulate.  These simulation objects will be defined as decision variables in OptQuest.  An OptQuest solution is a set of values for the decision variables.

• Set the values of the simulation objects in the simulation model and run a simulation using these values.  Optimization is an iterative process, so you must be able to repeat this set/run process for many iterations.  

• You must be able to identify simulation outputs that are affected by the decision variables.  The outputs may be used to define the objective of the optimization or to define non-linear constraints on the optimization.  For example, your objective may be to maximize Profit where Profit is an output of the simulation model. Simulation outputs used in constraints or objectives will be defined as COptQuestUserControlledVariable objects.

• You must be able to determine when a simulation has completed and you must be able to retrieve the values of the simulation outputs.  You need to tell OptQuest the values of the simulation outputs (user controlled variables) so OptQuest can determine how to adjust the search for the best solution.  OptQuest analyzes the results of the simulation and uses its intelligent search procedures to generate a new potential solution.

Running replications

The features of the general replication algorithm are available to you if your application can get control after each replication of a simulation.  You will need to tell OptQuest the values of the simulation outputs for the replication just completed. (Not the averaged values for all replications run thus far.)  OptQuest will keep track of the results for each replication and decide whether more replications are needed. See General replication algorithm.

If your simulation package supports the ability to go back and run more replications for a particular solution, then your simulation optimization can support running additional replications after an optimization has completed.  For most simulation packages, you will need the ability to set one or more random seeds such that running a replication with a solution produces new results, not the same results seen in the original replications.  See Running additional replications.

User Interface for Simulation Optimization

You will want to provide a user interface that allows the user to define:

• Decision Variables

• User Controlled Variables

• Constraints

• Objectives

• Optimization Options

• Display Results

Define Decision variables (Simulation Inputs)

You may want to create a list of all simulation objects that can be used as decision variables and allow the user to select from the list.  You will need to define the type of the decision variable (continuous, discrete, integer, etc.)  The variable type may be determined by the usage in the simulation model or it may be the choice of the user.  You will need to specify the range of values for the decision variable and you will want to make this a meaningful range so that OptQuest doesn't waste time looking at solutions that don't make sense.   

Decision variable names can include blanks and other special characters.  If the decision variable names are use in string expressions, enclose the name in square brackets or curly braces in the expression.  Square brackets can also be nested so array elements can be named using nested square brackets ([My Array[2]].)

Define User controlled variables (Simulation Outputs)

In most cases, your optimization definition will include outputs of the simulation.  For example, your objective may be to maximize Profit or Throughput where Profit and Throughput are outputs of the simulation model. You may want to create a list of simulation outputs and let the user select from the list.

Simulation outputs are defined as COptQuestUserControlledVariable objects.  OptQuest will use the value of user controlled variables to evaluate a constraint or an objective that has been defined as a string expression using user-controlled variables.

User controlled variable names can include blanks and other special characters.  If the decision variable names are used in string expressions, enclose the name in square brackets or curly braces in the expression.  Square brackets can also be nested so array elements can be named using nested square brackets ([Machine Output[2]].)

Define Constraints

COptQuestStringConstraint objects allow you to combine decision variables and/or user controlled variables in an expression.  String constraints are a powerful tool that allows the user to create mathematical expressions and define relationships among decision variables and user controlled variables.  You may want to provide an interface that allows your users to create constraint expressions.

Define optimization objective

The objective is the goal of the optimization.  The objective may be an output of the simulation or it can be a mathematical expression that uses decision variables and/or user-controlled variables representing outputs of the simulation.  

You will want to provide an interface that allows your users to create objectives.

Define optimization options

You will want to allow your users to select the stop criteria.  The OptQuest engine allows multiple stop options to be set.  Optimization stops when the first stop criteria is satisfied.  See Defining stop criteria.

If your simulation package can support general replication, you may want to allow your users to set the parameters available for general replication.  See General replication algorithm.

Running the optimization

You will need to extend the COptQuestOptimization class and override the Evaluate(COptQuestSolution) method.  If you want to provide feedback to the user while the optimization is in progress, override the MonitorStatus(COptQuestSolution) method as well.

To start the optimization, call the COptQuestOptimization.Optimize() method.  

When the Evaluate(COptQuestSolution) method is called, OptQuest has a new solution that needs to be evaluated.  Your Evaluate() method needs to do the following:

• For each decision variable, use the COptQuestSolution.GetVariableValue() method and set the value of the corresponding simulation object to the new value.

• Run the simulation.  

• After the simulation has completed, retrieve the results from the simulation outputs and set the values for user controlled variables and objectives.

If you are using general replications, the Evaluate() method will be called for each replication.  The method COptQuestSolution.GetReplication() will return the replication to be simulated. You can use the replication number to set a unique seed in the simulation.

The MonitorStatus(COptQuestSolution) method is called after OptQuest has evaluated the results that were set in the Evaluate(COptQuestSolution) method to determine if there is a new best solution.  If you are using general replication management, MonitorStatus() will be called after each replication.  The method COptQuestSolution.IsLastReplication() will return true if this is the last replication of the simulation.  Note the IsLastReplication() is not valid in the Evaluate() method because the current solution has not completed evaluation. See Displaying single objective results or Displaying pattern frontier results.

Displaying single objective results

While the optimization is running, COptQuestOptimization.MonitorStatus(COptQuestSolution) will be called after each solution completes evaluation.
You may want to display the following information while the optimization is in progress.

• The current iteration, If you are using replications you may want to display the current iteration and replication. For example: “Iteration 10, Replication 3”

• A graph displaying the best objective value at each simulation/iteration. You should distinguish between feasible and infeasible solutions.

• The values of the decision variables for the best solution and/or the current solution.

• The feasibility of the solution. The solution is feasible if all constraints satisfied the bounds of the constraint.

• The feasibility of each constraint.

When the optimization completes

When the optimization completes, you may want to display the solutions ordered from best objective value to worst. Use the COptQuestOptimization.GetNthBestSolution() method to retrieve each solution. The input parameter identifies the solution where the best solution is 1, second best is 2 and so on.

Solution replication information

The COptQuestSolution object contains detailed replication information. To retrieve a solution, use the COptQuestOptimization methods GetBestSolutio(), GetNthBestSolution() or GetIterationSolution(). From the solution, you can get the following information.

Displaying pattern frontier results

If your objective is a COptQuestFrontierMultiObjective the result is a set of solutions that are on the frontier. In a pattern frontier there isn’t a concept of a single best solution as each solution on the frontier is considered to be as good as any other solution.

You can display a graph of the pattern frontier as the optimization search progresses. COptQuestOptimization.GetPatternFrontier() will return a list of COptQuestSolution objects that are on the frontier. The X and Y axes of the graph should each represent an objective that is part of the COptQuestFrontierMultiObjective`.

If the COptQuestFrontierMultiObjective contains more than two objectives, you may want to let the user choose which objectives to display.

The number of solutions on the frontier will change as the optimization progresses so you will need to redraw the graph displaying the current points on the frontier. While the optimization is in progress, points on the frontier may be added or removed.

A pattern frontier contains only feasible solutions. No solutions will appear on the graph until there is at least one solution that satisfies all the constraints.

You will want to provide a way for the user to see the details of each solution on the frontier. You might allow the user to select a point on the frontier and then display the details of the selected solution.

General Replication Algorithm

The OptQuest Engine supports objective values that are based on experimentation through the General Replication Algorithm. This feature allows the user to provide the OptQuest Engine with results of multiple replications per simulation/iteration.

The OptQuest Engine allows you to run a fixed number of replications per simulation or a varying number of replications per simulation. The varying replications option can significantly speed up optimizations by running fewer replications when there is little variation in collected outputs or when the objective value for the current iteration is far from the best solution found.

The COptQuestOptimization.Evaluate(COptQuestSolution) method will be called for each replication of a solution. Your Evaluate(COptQuestSolution) method should run the simulation using a unique seed for each replication. When the simulation comnpletes, retrjeve the output values and set a value for each COptQuestUserControlledVariable and each objective. By default, OptQuest will use the mean as the replication statistic. Optionally, you can specify a different statistic for objectives and user controlled variables by calling COptQuestObjective.SetReplicationStatistic() or COptQuestUserControlledVariable.SetReplicationStatistic(). If you are using confidence testing, the statistic must be the mean of replication values.

To turn on replication processing, call COptQuestOptimization.SetUseReplications(true). To run a fixed number of replications call COptQuestOptimization.SetMinimumReplications() and do not set confidence settings for the objective(s).

Running a varying number of replications

To use variable replication management, you provide a minimum number of replications to run, a maximum number of replications to run, and confidence settings for at least one objective. The objective statistic must be MEAN. If no statistic is set, OptQuest defaults to mean. Replication processing will stop when all objectives meet the criteria provided in the confidence settings or the maximum number of replications is reached. The OptQuest Engine will always run the minimum number of replications for a solution. OptQuest then determines if more replications are needed to satisfy the confidence parameters.

To run a varying number of replications:

• Call COptQuestOptimization.SetUseReplications(true) to turn on replication processing

• Set the minimum number of replications to a value greater than one by calling the COptQuestOptimization.SetMinimumReplications() method. Set the maximum number of replications to a value larger then the minimum number of replications by calling COptQuestOptimization.SetMaximumReplications() method.

• Replication confidence for an objective is set with a type, a level, and an error percentage. Type 1 confidence testing checks if the statistical confidence level specified is met for the objective. Type 2 confidence testing can only be used for single objective problems and does Type 1 checking and also stops if the current objective is far from the best objective currently known. The confidence level indicates the alpha value to be used in testing, and the error percent provides the perrcent of the sample mean to be used in the stopping condition. For a number of replications greater than 30, the confidence interval will be calculated using the Standard Normal distribution. For a number of replications equal to or less than 30, the confidence interval will be calculated using the Standard T distribution. Call COptQuestObjective.SetReplicationConfidence() setting the confidence type, confidence level, and error percent.

The evaluations for the General Replication Algorithm include a replication number that provides a unique number from the iteration number. The replication number can be used to ensure that the trial run with this solution is unique from other trials run with the same solution.

The following methods are used to define the parameters for replication processing.

The following methods allow you to query a COptQuestSolution for replication data.

Running additional replications

The OptQuest Engine supports running additional replications on a set of solutions after an initial optimization has completed. To support this feature, you must be able to setup the simulation such that you can go back and run more replications of a particular solution. For most simulation packages, you will need the ability to set one or more random seeds such that running a replication with a solution produces new results, not the same results seen in the original replications.

This feature can shorten the total optimization time by allowing the user to run a minimal set of replications on the initial optimization and then go back and refine a set of solutions. For example, the user may run 3 replications per simulation on the initial optimization and then run additional replications on the top N solutions.

To use this feature, you identify the top N solutions that should have additional replications by calling the COptQuestOptimization.SetAdditionalReplicationsSolutions() method. You can also specify specific solutions by calling COptQuestOptimization.AddAdditionalReplicationsSolution(). The solution is identified by the iteration number that generated the solution.

The COptQuestOptimization.SetAdditionalReplications() method identifies how many additional replications should be run. The COptQuestOptimization.OptimizeAdditional() method runs the additional replications.

The Evaluate() method will be called for each additional replication.

Parallel implementation

Parallel implementation can be used to decrease the total optimization time by distributing the evaluations across multiple machines or processors. For example, if each evaluation requires a lengthy simulation, the total optimization time can be decreased by performing parallel simulations on multiple machines or processors.

Non-parallel optimization is a serial process where:

• The OptQuest Engine calculates possible solutions for the decision variables.

• A solution is evaluated and results are calculated for the objective and user controlled variables. The results are given back to the OptQuest Engine.

• The results are analyzed by the OptQuest Engine and a new set of possible solutions is calculated.

In a parallel optimization, multiple solutions are evaluated in parallel and the results are reported to the OptQuest Engine as each evaluation completes. As a machine or processor finishes its evaluation, the evaluation of another solution can begin.

To run parallel evaluations, you must:

• Tell the OptQuest Engine how many evaluations can be done in parallel by calling COptQuestOptimization.SetEvaluate(int totalEvaluators).

• Extend the COptQuestOptimization class and override the Evaluate(COptQuestSolution solution) method. You are responsible for managing the parallel evaluations and returning results to the OptQuest Engine by calling EvaluateComplete() with each completed evaluation.

If maximum number of solutions are out for evaluation, then the solution passed into Evaluate() method is null, OptQuest will not provide another solution to evaluate until it has received the results for an outstanding solution. You must wait for one of the processors to finish their evaluation and return the result of the evaluation.

In an environment with a dynamic number of available evaluators, the SetEvaluate(int) method may be called more than once during the optimization process to add additional evaluators. Evaluators cannot be removed once they have been added.

If you return from the Evaluate() method without waiting for an outstanding evaluation to complete, the OptQuest Engine will immediately call the Evaluate() method with a null solution.

• When an evaluation has completed. call the COptQuestOptimization.EvaluateComplete(COptQuestSolution) method to indicate the objective and user controlled values have been set.

• Override the COptQuestOptimization.MonitorStatus(COptQuestSolution) method to track the progress of the optimization. You can use the COptQuestOptimization.GetNumberOfCompletedIterations() method to track the progress of the optimization. If GetNumberOfCompletedIterations() returns a value greater than 0, you can retrieve the best solution using the COptQuestOptimization.GetBestSolution() method.

• Solutions may not return in iteration order. When MonitorStatus() is called for iteration 3, iterations 1 and 2 may still be out for evaluation.

COptQuestSolution objects and Parallel ID’s

During evaluation, each COptQuestSolution object contains a parallel ID. The parallel ID will be between 1 and the number of parallel processes you defined using COptQuestOptimization.SetEvaluate(). You can use the parallel ID to associate a solution with an evaluator.

Parallel optimization behavior

An optimization problem run in parallel mode will behave differently than the same optimization problem run in serial (non-parallel) mode.  In fact, the same optimization problem run in parallel mode may produce different results each time it is run.  To understand why this happens, you need some background information on the OptQuest Engine’s solution generation.

Overview of solution generation

The OptQuest Engine uses information from evaluated solutions to create a new set of solutions.  Depending on the solution generation algorithm, OptQuest may generate one new solution or many new solutions.  In a serial optimization, the OptQuest Engine waits until all the solutions in the previous list have been evaluated before using the solution results to generate a new set of solutions.

In a parallel optimization, you set the maximum number of solutions that the OptQuest Engine needs to provide.  When all solutions are out for evaluation, the OptQuest Engine waits for the user to return a solution before it provides another solution.

In a parallel optimization, OptQuest takes advantage of the parallel evaluators by generating new solutions when needed even though it is still waiting for some solutions to complete evaluation. Since the OptQuest Engine uses the results from evaluated solutions to create new solutions, the order of completion and the number of completed solutions will impact solution generation.  This means the number of evaluators and the processor speed of the evaluators affect the solution generation.

Implementation of a parallel optimization

In this implementation, the user takes full advantage of the parallel evaluators to increase the impact of the solution generation techniques of the OptQuest Engine. The results from this implementation are not necessarily reproducible.

1. Set the maximum number of parallel solutions to the number of evaluators you have available.  Optionally, you can ask for one extra and keep it in a queue to make sure you can immediately start an evaluator when it has completed.

2. Create two queues:

   • The “to be evaluated” queue will be used to distribute solutions to evaluators.

   • The “completed evaluation” queue will hold the solutions that have been evaluated.

3. During the optimization:

   • If the maximum number of parallel solutions has been provided by the OptQuest Engine, wait for a solution to be put on the “completed evaluation” queue.

   • Put the current solution on a “to be evaluated” queue.

   • As solutions complete evaluation, place them on the “completed evaluation” queue.

   • Return solutions from the “completed evaluation” queue.

If you require each run of the optimization to produce the same results, call COptQuestOptimization.RunRepeatableEvaluations(true). OptQuest will wait for all oustanding solutions to be evaluated before generating new solutions. This may impact performance if one of the evaluators is slower than the others.

To keep all evaluators busy, the number of parallel solutions must be larger than the number of evaluators.  If this number is too small, there may be times when faster evaluators are waiting on a slower one to complete it’s evaluation since it would be next in line to be returned.  A good rule of thumb is if the faster evaluator is “n” times faster than the slower, then multiply the number of evaluators by “n”.

It is important to note that the larger the number of parallel evaluators that are defined, the later the OptQuest Engine can start using the information from returned solutions in its generation algorithms.  This may cause the number of total iterations needed to get to the same quality of solution to be more than in the serial mode.

To get the best result with the most efficient use of the parallel evaluators, the typical implementation is recommended.  However, since it is not reproducible, the reproducible implementation is available for users that require reproducible results.

Parallel evaluation methods

OptQuest can provide the calling class with more than one solution to evaluate in parallel. The following methods are used for parallel evaluations.

Parallel implementation with replications

The parallel implementation of the OptQuest Engine supports replications. This feature is used if your evaluation requires multiple replications or trials and you want to use the replication features of the OptQuest Engine.

When you are using replications, OptQuest will evaluate the replications of a solution in parallel. If you have 3 parallel evaluators, OptQuest will send 3 replications of a solution for evaluation. The replications may not finish in replication order. If MonitorStatus() returns replication 3 of a solution, replications 1 and 2 may still be out for evaluation.

If you need replications to be run serially, use the method COptQuestOptimization.RunSerialReplications(true). When running replications serially, replication n+1 of a solution won't be sent for evaluation until replication n is returned.

To run parallel evaluations with replications, you must:

• Call COptQuestOptimization.SetUseReplications(True) to indicate you are using replications

• Call COptQuestOptimization.SetMinimumReplications() and COptQuestOptimization.SetMaximumReplications() to set the minimum and maximum number of replications.

• You can turn on replication confidence testing by calling COptQuestObjective.SetReplicationConfidence() to set the confidence testing parameters.

• Override the COptQuestOptimization.Evaluate(COptQuestSolution solution) method.

• Return the results of the evaluation by calling COptQuestOptimization.EvaluateComplete().

See General replication algorithm.

Stopping parallel evaluation

Optimizations with parallel evaluations stop when the stop criteria has been satisfied and all outstanding parallel evaluations have completed. If the stop criteria is 1000 iterations, no new solutions will be evaluated when iteration 1000 is complete, but the optimization will not terminate until all outstanding solutions have completed evaluation.

If the optimization is stopped by the COptQuestOptimization.StopOptimization() method, the optimization is stopped immediately.  All outstanding parallel evaluations are ignored.

The method COptQuestOptimization.StopSolutionGeneration() will tell OptQuest to stop generating new solutions but OptQuest will wait for outstanding parallel evaluations to complete before terminating.

Advanced topics

Exception handling

When the OptQuest Engine encounters an error condition, it will throw a COptQuestException. A COptQuestException contains the following information:

• An exception error code.

• A reason code that gives additional information about the error. For example, the exception code EXCEPT_BADCONEQUATION which indicates an error in a constraint expression, may have the reason code REASON_EQMISSINGCLOSEPAREN which indicates a missing closing parentheses.

• An error token which is a string. This is used in string expressions for constraints or objectives and identifies the token that caused the error.

The COptQuestException.Description() method will return a text string describing the error.

Throwing a COptQuestException

You may want to throw a COptQuestException when there is a failure in the Evaluate() method. For example, if you are doing simulation optimization and there is an unrecoverable error in the simulation, you may want to throw a COptQuestException to stop the optimization.

To throw a COptQuestException, create an instance of the COptQuestException object. The parameters are an error number and a text string describing the error. You will get the error number by calling the COptQuestOptimization.GetEvaluateException() method. The text string can be any descriptive text.

For example:

throw new COptQuestException(this.GetEvaluateException(), \"Error running simulation.\");

Constraints as goals

In some cases an optimization problem may have goals for a constraint bound.  For example, a project manager may have a target value for a performance factor but won't mind if the target is exceeded by 3% or less. In this case the project manager would not want solutions that violate the constraint marked as infeasible but he would want solutions that are close to the constraint bound to be considered better than solutions that are far away from the bound.

The OptQuest Engine allows you to identify contraints as goals using the COptQuestStringConstraint.SetGoal() method. Constraints that are goals will never be marked as infeasible.  

Goal constraints can be paired with hard constraints to set a limit on the target.   For example, you may want to target risk to be 5% or less but not accept risk over 8%.  You could define a constraint goal of "Risk <= .05" and a hard constraint of "Risk <= .08".  In this case, OptQuest would search for solutions that resulted in a risk less than .05, however, solutions with a risk <= .08 would be considered feasible.  Any solution that created a risk > .08 would be marked infeasible.

Modifying an optimization problem

The OptQuest Engine allows you to change an optimization problem “on the fly.” For example, the optimization could run for some number of iterations, you could modify the problem and then continue the optimization. You could also run a complete optimization, make modifications and then run additional iterations. When an optimization problem is modified, all evaluated solutions are rechecked. It is possible that the changes will make previously feasible solutions infeasible or vice versa. It is also possible the changes will make the optimization problem constraint infeasible. If this occurs, the OptQuest Engine will throw a COptQuestException.

When changes are made while an optimization is in progress, the changes are applied immediately and all evaluated solutions are rechecked. If the changes are made after an optimization completes, the COptQuestOptimization.Recalculate() method will apply the changes and recheck all evaluated solutions but not generate any new solutions. The COptQuestOptimization.OptimizeAdditional() method will apply the changes, recheck all evaluated solutions and then continue the solution search using the new information. The additional iterations will utilize the information from the previously evaluated solutions to generate new solutions.

If you want to analyze the effect of a change within a set of solutions, use the Recalculate() method. If you want to see if the change can drive the search to a better solution, use the OptimizeAdditional() method.

For example, you may want to know what impact a constraint has on a solution. You could:

• Setup the optimization problem with the constraint

• Run the optimization and retrieve the best solution

• Remove the constraint and call OptimizeAdditional() to run additional iterations, allowing OptQuest to search for better solutions with the new problem definition.

• Retrieve the best solution.

Alternatively, you could:

• Setup the optimization problem without the constraint

• Run the optimization and retrieve the best solution

• Add the constraint and call Recalculate() which will reevaluate all existing solutions.

• Retrieve the best solution

The following tables summarize the changes you can make for each optimization object.

Modifying decision variables: COptQuestContinuousVariable, COptQuestDesignVariable, COptQuestDiscreteVariable, COptQuestIntegerVariable

The OptQuest Engine will throw an EXCEPT_CONSTRAINTINFEASIBLE exception if changes to the variable bounds make the problem constraint infeasible.

Modifying string constraints: COptQuestStringConstraint:

The OptQuest Engine will throw an EXCEPT_CONSTRAINTINFEASIBLE exception if changes to the constraint make the problem constraint infeasible.

Modifying the objective

Additional optimization

When an optimization has completed (the Optimize() method has returned), you can analyze the solutions and determine if additional optimization is needed. You can continue the optimization by doing one of the following:

• If the original optimization used general replication, you can run additional replications on all solutions or a selected set of solutions. No new solutions are created. Running additional replications

• You can run additional iterations which will generate new solutions. Running additional iterations

• You can suggest specific solutions to be tried. To suggest a solution, get a new, empty solution by calling the COptQuestOptimization.CreateSolution() method. You set the suggested values by calling the COptQuestSolution.SetVariableValue() method. Use the COptQuestOptimization.AddSuggestedSolution() to add the suggested solution to the set of solutions that will be evaluated. Call the COptQuestOptimization.SetAdditionalIterations() methods giving it the number of suggested solutions you added. Call the COptQuestOptimization.OptimizeAdditional() method to evaluate the suggested solutions. Suggesting possible solutions

Permutation Variables and Groups

Permutation variables can be used to represent a step in a sequence, an order of priorities, or can be more generally used for an algebraic permutation group. For example, four permutation variables could be used to optimize the sequence in which four locations are visited. COptQuestSolution.GetVariableValue() will return which step in the itinerary each location should be - first through fourth.

If your optimization problem involves multiple sets of permutation variables, or multiple sequences, create a permutation group and add the permutation variables to the respective group to be ordered with. Permutation variables not added to a specific permutation group will be treated as though they were added to a common global permutation group.

Pause and continue

This COptQuestOptimization.ContinueOptimize() allows you to continue an optimization that was stopped before all iterations were completed or while there was time remaining.  The method will resume the optimization where it left off.

To pause an optimization, call COptQuestOptimization.StopOptimization();  Any outstanding solutions that have not completed evaluation will be saved as unevaluated solutions and evaluated when COptQuestOptimization.ContinueOptimize() is called.  Optionally, you can allow the user to extend the optimization by adding additional iterations COptQuestOptimization.SetAdditionalIterations() or additional time COptQuestOptimization.SetAdditionalTime().

If you set additional iterations after stopping the optimization, the additional iterations are added to the remaining iterations. If you set additional time, the additional time is added to the remaining time.

Maximum number of solutions

The OptQuest Engine keeps an in memory database of all evaluated solutions. This database does not have a fixed size and there is not a hard limit on the number of solutions that can be evaluated. By default, if no other stopping criteria is met, OptQuest will stop at an iteration limit of 250,000 solutions. For most practical problems, this is far more iterations than is needed to find the best solution. As the number of evaluated solutions grows, the amount of memory required by OptQuest will slowly grow. If a problem contains a large number of COptQuestVariables, or the amount of memory for your process is limited, you may need to stop the optimization process at a smaller iteration limit.

The method COptQuestOptimization.GetNumberOfCompletedIterations() returns the number of evaluated solutions that exist at any time.

The method COptQuestOptimization.GetApproxSolutionSize() returns the approximate size (in bytes) of a single solution.

Precision properties

When generating new solutions, the OptQuest Engine uses a variable precision value which is used to compare the values for decision variables and determine duplicate solutions. Two decision variables are considered to have the same value if their difference is <= the variable precision * the range of the variable.

The default starting value for the variable precision is .01. As the OptQuest Engine searches for new solutions, this value is decreased.

The OptQuest Engine allows you to modify the starting and ending value for the variable precision. Call the COptQuestOptimization.SetStartingVarPrecision() and COptQuestOptimization.SetEndingVarPrecision() methods to set precision values.

The OptQuest Engine also uses an objective precision value which is used to compare the objective value of solutions and determine if one solution is superior to another. The default starting value for the objective precision is .01. As the optimization progresses, the value is decreased.

The OptQuest Engine allows you to modify the starting objective precision. Call the COptQuestOptimization.SetObjPrecision() method to set a new value.

Tips

Setting up the model

If there are errors in the optimization setup, OptQuest will throw a COptQuestException. Be sure to put a try/catch block around your call to the COptQuestOptimization.Optimze() method.

Pick meaningful bounds for your decision variables so the OptQuest Engine doesn’t waste time exploring solutions that are not meaningful.

It is important that the value of a non-linear constraint provide a measure that can be used by the OptQuest Engine to determine a distance from feasibility. A constraint 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 non-linear constraint where a solution that is closer to the bound of the constraint can be treated as superior to a solution whose value is farther away from the bound.

You can ask OptQuest to sort infeasible solutions using an infeasibility index where a solution that is close to feasibility. To use the infeasibility index for sorting infeasible solutions, call COptQuestOptimization.SetUseInfeasibilityIndex(true).

Optimization Results

To determine if a solution is feasible (i.e., all constraints satisfy the constraint bounds) call COptQuestSolution.IsFeasible(). To check if a particular constraint is feasible, use COptQuestSolution.IsFeasible(COptQuestStringConstraint). When you display results to the user, you can display the left side and right side values for constraints by calling the methods COptQuestSolution.GetConstraintLHS(COptQuestStringConstraint) and COptQuestSolution.GetConstraintRHS(COptQuestStringConstraint).

You can define COptQuestUserControlledVariables for simulation outputs. For each solution, you can display the value of the simulaion output.

Goal constraints can be paired with hard constraints to set a limit on the target. For example, you may want to target risk to be 5% or less but not accept risk over 8%.
You could define a constraint goal of “Risk <= .05” and a hard constraint of “Risk <= .08”. In this case, OptQuest would search for solutions that resulted in a risk less than .05, however, solutions with a risk <= .08 would be considered feasible. Any solution that created a risk > .08 would be marked infeasible.
See Goal Constraints.

A solution hasn’t completed evaluation until MonitorStatus() is called. Check for the best solution and solution feasibility in MonitorStatus(), not in the Evaluate() method.

A COptQuestFrontierMultiObjective contains a list of solutions that are on the frontier. Graphs should display objectives on the X and Y axis.

OptQuest solution generation

The OptQuest Engine search algorithm is based on metaheuristics. A metaheuristic refers to a master strategy that guides and modifies other heuristics to produce solutions beyond those that are normally generated in a quest for local optimality. The heuristics used within the OptQuest Engine are many and are guided by such a meta-strategy. The individual heuristics may use the best solution, a reference set of solutions, a defined subset of evaluated solutions, or the entire set of evaluated solutions to create new solutions in the search for global optimality.

The OptQuest Engine maintains an in memory database of all unique solutions. Each solution contains the value for each decision variable. If the solution has been evaluated, the solution will also contain the values for each user-controlled variable, requirement and the objective.

Whenever OptQuest generates a new solution, it checks the database of solutions to be sure the new solution hasn’t already been evaluated. In some cases, you may want to turn off the duplicate solution checking. For example, if the evaluation of the objective is a fast calculation, it may be faster to evaluate a solution than to check the database to see if it has been evaluated.

Discrete variable enumeration

If an optimization problem uses only discrete variables, the OptQuest engine attempts to enumerate all possible solutions if OptQuest’s metaheuristic search algorithms fail to generate new solutions. If full enumeration would result in a set of solutions larger than the limit set on the number of iterations, the OptQuest Engine will enumerate a subset of the possible solutions to evaluate.

If a complete enumeration is accomplished, the OptQuest Engine reports that the optimal solution has been found. If the problem is requirement-infeasible, the OptQuest engine reports that the problem is infeasible.

Suggesting possible solutions

If you have a guess about the possible solutions for an optimization problem, you can give the solutions to the OptQuest Engine. Suggested solutions can shorten the time it takes to find an optimal solution. You can suggest a solution before the optimization is started or while the optimization is running.  If you add the suggested solutions before the optimization is started, they are evaluated before OptQuest generates solution. If you add the suggested solutions after the optimization has started, they will be evaluated as soon as an evaluator is available.

If your suggested solution violates one or more linear constraints, the solution is modified to make it constraint feasible before it is returned to you for evaluation.  As a result, you may not see your exact suggested values returned for evaluation, since they may have been changed to make your solution constraint feasible.

To add a suggested solution:

1. Use the COptQuestOptimization.CreateSolution() method to get a new empty COptQuestSolution

2. Set the value for each decision variable in the suggested solution using the COptQuestSolution.SetVariableValue() method

3. Call the COptQuestOptimization.AddSuggestedSolution() method to add the solution to the list of solutions to be evaluated

You can make multiple suggestions by repeating these steps. Any variables that you do not set will use the previously set suggested value. The default suggested value is the mid-point between the lower and upper bound.

Running only suggested solutions

If you want only your suggested solutions evaluated, do the following:

• Add the suggested solutions before calling the COptQuestOptimization.Optimize() method

• Call COptQuestOptimization.SetGenerateNewSolutions(false);

• Call the COptQuestOptimization.Optimize() method. No new solutions will be generated and the solutions you added will be evaluated

Modifying a solution

The OptQuest Engine allows you to modify the current solution suggested by the OptQuest Engine by changing the values of the decision variables. If you use a value other than the value suggested by OptQuest, it is important to change the OptQuest solution to match the values you used to calculate the objective. Use the COptQuestSolution.SetVariableValue() method to assign a new value to a decision variable.

You will need to modify solutions in the COptQuestOptimization.Evaluate(COptQuestSolution solution) method.

If your modifications violate a linear constraint, the OptQuest Engine will throw a COptQuestException and terminate the optimization.

Constraints and solution generation

The OptQuest Engine can determine feasibility of linear constraints when it generates a solution, because it has all the information it needs to calculate a value and ensure its feasibility. Linear constraints may improve optimization performance as infeasible solutions are eliminated within the OptQuest Engine.

Optimization performance may suffer when you include non-linear constraints in the optimization problem. Non-linear constraints can be time-consuming to evaluate if the constraint requires a lengthy evaluation, such as running a simulation. Also, the OptQuest Engine tries to rule out undesirable solutions by examining the results of feasible and infeasible non-linear constraints.

It is important that the value of a non-linear constraint 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.

If the optimization is set to run for a specified amount of time, it may be necessary to increase the amount of time to compensate for the additional overhead of non-linear constraints.

Rejecting solutions

The OptQuest Engine allows you to mark a solution as rejected. A solution that has been rejected will not be considered as a candidate for the best or Nth best solution. When new solutions are generated, rejected solutions are checked to make sure the new solution is not a duplicate of a rejected solution. To reject a solution, call the COptQuestSolution.RejectSolution() method from the Evaluate() method. Rejected solutions will not have valid values for objectives, constraints or user controlled variables.

Non-linear string constraints

If you have defined one or more constraints as COptQuestStringConstraint and the constraint equation is non-linear but contains only decision variables, by default the OptQuest engine will attempt to generate solutions that adhere to the non-linear constraints. This process of handling nonlinear constraints will increase the amount of time it takes OptQuest to generate solutions. If your simulation runs very fast and you do not want OptQuest to handle non-linear constraints, then you can turn this feature off.

Version and licensing information

Version information

You can determine the version of the OptQuest Engine by calling the COptQuestOptimization.GetVersion() method.  This method returns a string identifying the version number of the OptQuest Engine.  

Licensing

When you purchase the OptQuest Engine or request a trial version of the OptQuest Engine, you will be assigned a license ID.  Use this ID as the input parameter to COptQuestOptimization.SetLicenseID() .

OptQuest will throw an exception if the license is invalid or has not been set. If the license is invalid, OptQuest will delay 10 seconds before throwing the exception.

Glossary

Decision variable

A decision variable is a quantity that the decision-maker controls. For example, the number of nurses to employ during the morning shift in an emergency room may be a decision variable in an optimization model for labor scheduling. The OptQuest Engine manipulates decision variables in search of their optimal values.

Design variable

Used for decisions where value of the variable represents an alternative, and not a quantity. Design variables are useful in optimization problems where the decision variables consist of choosing the best alternative from a catalog, and a larger number may not imply the commitment of more resources. Therefore, choice #10 may not be a more costly or better choice than choice #1. These variables are defined by a lower bound, an upper bound, and a step size that controls the number of choices available within the specified range.

Discrete variable

A decision variable that begins at a lower bound and increments by a step size up to an upper bound.

Feasible

A feasible solution is one that satisfies all linear and non-linear constraints.

Infeasible

Infeasibility occurs when no combination of values for the decision variables can satisfy a set of constraints. An infeasible solution does not imply that the problem itself is infeasible.

Integer variable

A discrete variable with integer bounds and a step size of 1

Linear constraint

Linear constraints describe a linear relationship among decision variables. A linear constraint is a mathematical expression where linear terms (i.e., a coefficient multiplied by a decision variable) are added or subtracted and the resulting expression is forced to begreater-than-or-equal, less-than-or-equal, or exactly equal to a right-hand side value. For example, if the total budget for scanners ($2000 each) and printers ($1000 each) is $5000, you can define this as:

2000*scanners + 1000*printers <= 5000

In another example, if x1 represents the number of spaces in buffer 1 and x2 represents the number of spaces in buffer 2, the following constraint restricts the search to solutions for which buffer 2 has at least as many spaces as buffer 1.

x2 – x1 >= 0

Metaheuristics

A family of optimization approaches that includes scatter search, genetic algorithms, simulated annealing, Tabu search, and their hybrids.

Non-linear constraints

A mathematical expression describing a non-linear relationship among decision variables and/or user-controlled variables. A non-linear constraint can also be a restriction on a simulation output that requires its value to fall within a specified range.

Objective function

A mathematical expression describing a relationship among decision variables, or the result of an operation (such as simulation), that uses the decision variables as inputs.

Permutation variable

Permutation variables are used to solve sequencing problems, for example, the order in which paint should be mixed to minimize cleanup time between color changes. The value of a permutation variable represents the order within the sequence.

Scatter search

A population-based metaheuristic that operates on a collection of reference points with the goal of finding high-quality solutions to an optimization problem.

Tabu search

A metaheuristic that uses search history and memory management to guide the problem-solving process. In its simplest form, memory prohibits the search from reinvestigating solutions that have already been evaluated. In OptQuest, memory functions to encourage search diversification and intensification. These memory components divert the search from locally optimal solutions to find a globally optimal solution.