Branch-and-bound method

Also, it is possible to combine stochastic and deterministic methods as hybrid methods. For example, a stochastic method can be used to control the structural changes and a deterministic method to control the changes in the continuous variables. This can be useful if the problem involves a large number of integer variables, as for such problems, the tree required for branch and bound methods explodes in size. 

More generally, MILPs are solved with branch and bound algorithms, similar to the spatial branch and bound method of the previous section, that explore the search space. As seen in Fig. 3-61, binary variables are used to define the search tree, and a number of bounding properties can be noted from the structure of (3-110). 

LP software includes two related but fundamentally different kinds of programs. The first is solver software, which takes data specifying an LP or MILP as input, solves it, and returns the results. Solver software may contain one or more algorithms (simplex and interior point LP solvers and branch-and-bound methods for MILPs, which call an LP solver many times). Some LP solvers also include facilities for solving some types of nonlinear problems, usually quadratic programming problems (quadratic objective function, linear constraints see Section 8.3), or separable nonlinear problems, in which the objective or some constraint functions are a sum of nonlinear functions, each of a single variable, such as... 

Solving MINLP Problems Using Branch-and-Bound Methods.361... 

In this chapter, we discuss solution approaches for MILP and MINLP that are capable of finding an optimal solution and verify that they have done so. Specifically, we consider branch-and-bound (BB) and outer linearization (OL) methods. BB can be applied to both linear and nonlinear problems, but OL is used for nonlinear problems by solving a sequence of MILPs. Chapter 10 further considers branch-and-bound methods, and also describes heuristic methods, which often find very good solutions but are unable to verify optimality. 

SOLVING MINLP PROBLEMS USING BRANCH-AND-BOUND METHODS... 

Norkin, W.I., Pflug, G.Ch., and Ruszczysk, A. (1998) A branch and bound method for stochastic global optimization. Mathematical Programming, 83, 425. 

In the next section we will focus only on describing the basic principles of the branch and bound methods which are the most commonly used algorithms in large-scale mixed-integer linear programming solvers. 

In this section, (i) we will discuss the basic notions of separation, relaxation, and fathoming employed in a branch and bound method, (ii) we will present a general branch and bound algorithm, and (iii) we will discuss a branch and bound method which is based on linear programming relaxation. 

A general branch and bound method for MILP problems of the form (1) is based on the key ideas of separation, relaxation, and fathoming which are outlined in the following ... 

In the subsequent sections, we will concentrate on the algorithms that are based on decomposition and outer approximation, that is on 1., 3., 5., 6., 7., and 8.. This focus of our study results from the existing evidence of excellent performance of the aforementioned decomposition-based and outer approximation algorithms compared to the branch and bound methods and the feasibility approach. 

E. M. L. Beale. Branch and bound methods for mathematical programming systems. Ann. of Discrete Math., 5 201,1979. 

J. A. Tomlin. An improved branch and bound method for integer programming. Oper. Res., 19 1070, 1971. 

When the nonlinear discrete optimization problem is formulated as the generalized disjunctive program in (DPI), one can develop a corresponding logic-based branch-and-bound method. The basic difference is that the branching is performed... 

The global optimization algorithm described above uses a spatial branch-and-bound procedure (steps 2 to 4). Like many branch-and-bound methods, the algorithm consists of a set of branching rules, together with upper bounding and lower bounding procedures. 

Friedler, F., Tarjan, K., Huang, Y. W., and Fan, L. T. An Accelerated Branch and Bound Method for Process Synthesis, presented at the 4th World Congress of Chemical Engineering, Karlsruhe (1991). 

Under the vertex solution assumption, the flexibility index can be calculated by evaluating the maximum 8 along each vertex direction and taking the minimum of the results. This approach becomes computationally impractical for more than about 15-20 parameters, so two procedures are presented which give upper bounds on F more efficiently (a vertex search method and a branch-and-bound method). Of the two methods, the vertex search method is found to be more efficient on the examples considered and therefore seems the best candidate for use to get an approximate solution for the worst-case vertex where appropriate. The vertex search procedure is given below. 

The branch and bound method can be used for MINLP problems, but it requires solving a large number of NLP problems and is, therefore, computationally intensive. Instead, methods such as the Generalized Benders Decomposition and Outer Approximation algorithms are usually preferred. These methods solve a master MILP problem to initialize the discrete variables at each stage and then solve an NLP subproblem to optimize the continuous variables. Details of these methods are given in Biegler et al. (1997) and Diwekar (2003). 

Here only deterministie methods for global optimisation are considered. They are based on the generation of eonvex relaxations of the original non-eonvex problem (2). Numerous methods have been proposed for eonstrueting sueh relaxations [5-9]. In this work, the branch-and-bound method [5, 6, 10, 11] is exploited to guarantee the global optimality within e-toleranee to the solution of the non-eonvex NLP problem (2). 

---