Solver Emphasis & Optimality

MSO employs a 'solver' to calculate optimal mineable stope shapes based on multiple input parameters. Such a solver is often further described with the prefix "MIP". MIP stands for "Mixed Integer (Linear) Programming". Mixed Integer Linear Programming problems are generally solved using a linear-programming based branch-and-bound algorithm..

On the basis that a linear programming model consists of an objective (grade or recovered metal), which is a linear equation that must be maximized or minimized (in MSO's case - maximized). Then there are a number of linear inequalities or constraints that govern how a solution (an ideal stope shape) can be created.

Feasibility

A linear program is infeasible if there exists no solution that satisfies all constraints. In other words, if no feasible solution can be constructed. Since any real operation that you are modelling must remain within the constraints of reality, infeasibility most often indicates an error of some kind.

The source of infeasibility is often difficult to track down. It may stem from an error in specifying some of the constraints in your model, or from some incorrect numbers in your data.

Emphasis

With regards to emphasis, you need to decide the ultimate goal of the solver. What does a solution have to be in order to be considered 'possible'?

By default, your solver will attempt to provide a 'balanced' solution, that is, one that respects both the feasibility of the solution and its optimality.

In MSO, you can choose the emphasis when you Define Processing Settings, choosing one of the following:

  • Balanced – balance optimality and feasibility. This causes the selected solver to work toward a rapid proof of an optimal solution, but balancing that with effort toward finding high quality feasible solutions early in the optimization.

  • Feasibility – Emphasize feasibility over optimality. This option will cause the solver to frequently generate more feasible solutions as it optimizes the problem, at some sacrifice in the speed to the proof ofoptimality.

  • Optimality – Emphasize optimality over feasibility. When selected, less effort may be applied to finding feasible solutions early.

  • Best Bound: – Emphasize moving best bound. With this setting, even greater emphasis is placed on proving optimality through moving the best bound value, so that the detection of feasible solutions along the way becomes almost incidental.

  • Hidden Feasibility – Emphasize finding hidden feasible solutions. With this setting, the optimizer works hard to find high quality feasible solutions that are otherwise very difficult to find, so consider this setting when the Feasibility option (see above) has difficulty finding solutions of acceptable quality.

Optimality

Optimality is another quality of an optimization calculation, and is best described as 'narrowing the gap': once you have an incumbent (the best integer solution found at any point in the search for a solution), the objective value for this incumbent, assuming the original MIP is a maximization problem (in MSO, it is), is a valid upper bound on the optimal solution of the given MIP. That is, we know that we will never have to accept an integer solution of value higher than this value.

Somewhat less obvious is that, at any time during the branch-and-bound search we also have a valid lower bound, sometimes call the Best Bound (see above). This bound is obtained by taking the minimum of the optimal objective values of all of the current leaf nodes. Finally, the difference between the current upper and lower bounds is known as the gap.

MSO provides control of this by providing Gap Tolerance and Integrality Tolerance settings.

  • Gap Tolerance – Sets an absolute tolerance on the gap between the best integer objective and the objective of the best node remaining. When this difference falls below the value of this parameter, the mixed integer optimization is stopped.

  • Integrality Tolerance – On some models, the integer solution returned by your solver at default settings may contain solution values for the discrete variables that violate integrality by a small amount. This parameter has a default value of 1e-5, which means that any discrete variable that violates integrality by no more than this amount will not be branched upon for resolution. For most model formulations, this situation is satisfactory and avoids branching that may be essentially meaningless, only consuming additional computing time.

See Define Processing Settings.

When the gap is zero we have demonstrated optimality.