Solution methods

Network Optimization provides three methods for use in solving your problem:

• Branch and bound algorithm
• Linear programming approximation
• Multi-phase site selection

For most models, the branch and bound algorithm is effective. This method is the default.

Branch and bound algorithm

The branch and bound algorithm (called “Solve Optimally”) is the traditional method to solve mixed integer programs that involve binary or integer decisions. It performs linear programming for linear problems (see Formulating a linear program), and uses the branch and bound technique to solve problems with binary or integer variables (see Integer constraints). The solver identifies the best solution by evaluating the difference (gap) between the best integer solution and the best linear-only solution (best bound). When the gap between the two solutions meets the user-defined gap value, the solution is deemed optimal. For a description of the gap options, refer to Termination settings.

The branch and bound algorithm is a good method for most model problems. It guarantees optimality and returns a feasible solution. It can be used for any type of integer variable. However, if your model has a large number of binary variables, the run time with this method may be lengthy. This is the default solution method (called “Solve Optimally” in the General options for Network Optimization.)

Linear programming approximation

For linear or integer problems, the linear programming approximation method solves only the linear program for linear and integer problems. As a result, it can be much faster than the branch and bound algorithm due to the lack of integer variables. However, in some cases, it can return an infeasible solution.

Since linear programming approximation does not use integer variables, binary decisions, such as open/close decisions are not handled as they would be with branch and bound. For example, with linear programming approximation, you may see facilities flagged as closed, but with throughput.

When solving using the linear programming approximation method, the relative gap is disabled.

Multi-phase site selection

The multi-phase site selection solves the problem in two phases.

• First phase – In this phase, the program solves a linear programming relaxation. Constraints, such as conditional minimums and open/close decisions that are based on integers, are not enforced. During this phase, binary values with values close to zero or one are fixed.
• Second phase – This phase is used to prove the quality of the solution. It starts with the solution returned in the first phase, then adds reformulated constraints to the linear programming formulation to tighten the LP relaxation. The original problem is solved optimally.

This method guarantees optimality and returns a feasible solution. Depending on the type and number of binary variables in your model, the run time may be faster than with the branch and bound algorithm. If your model does not include integer variables, you should not use the multi-phase site selection.

Multi-phase site selection uses the relative gap as defined in Termination settings.

The multi-phase site selection is recommended in the following cases:

• Run time with the standard branch and bound algorithm is excessive.
• Your model requires the following decisions:
  • Site selection
  • Work center selection
  • Choose x out of y potential sites
  • Production planning decisions