Reconsider the discrete nonlinear programming problem given in Prob. 12.4-5
(a) Use the following outline in designing the main features of a branch-and-bound algorithm for solving this problem (and similar problems) directly without reformulation.
(i) Specify the tightest possible nonlinear programming relaxation that has only continuous variables and so can be solved efficiently by nonlinear programming techniques. (The next chapter will describe how such nonlinear programming problems can be solved efficiently.)
(ii) Specify the fathoming tests.
(iii) Specify a branching procedure that involves specifying two ranges of values for a single variable.
(b) Use the algorithm designed in part (α) to solve this problem by using an available software package to solve the quadratic programming relaxation at each iteration. (As described in Sec. 13.7, Excel, LINDO, LINGO, and MPL/CPLEX all are able to solve quadratic programming problems.)
Prob. 12.4-5
Consider the following discrete nonlinear programming problem
The numbers along the links represent distances, and the objective is to find the shortest path from the origin to the destination. This problem also can be formulated as a BIP model involving both mutually exclusive alternatives and contingent decisions.
(a) Formulate this model. Identify the constraints that are for mutually exclusive alternatives and that are for contingent decisions.
(b) Use the computer to solve this problem