A two-phase method for selecting IMRT treatment beam angles: Branch-and-Prune and local neighborhood search

This paper presents a new two-phase solution approach to the beam angle and fluence map optimization problem in Intensity Modulated Radiation Therapy (IMRT) planning. We introduce Branch-and-Prune (B&P) to generate a robust feasible solution in the first phase. A local neighborhood search algorithm is developed to find a local optimal solution from the Phase I starting point in the second phase. The goal of the first phase is to generate a clinically acceptable feasible solution in a fast manner based on a Branch-and-Bound tree. In this approach, a substantially reduced search tree is iteratively constructed. In each iteration, a merit score based branching rule is used to select a pool of promising child nodes. Then pruning rules are applied to select one child node as the branching node for the next iteration. The algorithm terminates when we obtain a desired number of angles in the current node. Although Phase I generates quality feasible solutions, it does not guarantee optimality. Therefore, the second phase is designed to converge Phase I starting solutions to local optimality. Our methods are tested on two sets of real patient data. Results show that not only can B&P alone generate clinically acceptable solutions, but the two-phase method consistently generates local optimal solutions, some of which are shown to be globally optimal.     

On parallel Branch and Bound frameworks for Global Optimization

Branch and Bound (B&B) algorithms are known to exhibit an irregularity of the search tree. Therefore, developing a parallel approach for this kind of algorithms is a challenge. The efficiency of a B&B algorithm depends on the chosen Branching, Bounding, Selection, Rejection, and Termination rules. The question we investigate is how the chosen platform consisting of programming language, used libraries, or skeletons influences programming effort and algorithm performance. Selection rule and data management structures are usually hidden to programmers for frameworks with a high level of abstraction, as well as the load balancing strategy, when the algorithm is run in parallel. We investigate the question by implementing a multidimensional Global Optimization B&B algorithm with the help of three frameworks with a different level of abstraction (from more to less): Bobpp, Threading Building Blocks (TBB), and a customized Pthread implementation. The following has been found. The Bobpp implementation is easy to code, but exhibits the poorest scalability. On the contrast, the TBB and Pthread implementations scale almost linearly on the used platform. The TBB approach shows a slightly better productivity.     

Multi-dimensional pruning from the Baumann point in an Interval Global Optimization Algorithm

A new pruning method for interval branch and bound algorithms is presented. In reliable global optimization methods there are several approaches to make the algorithms faster. In minimization problems, interval B&B methods use a good upper bound of the function at the global minimum and good lower bounds of the function at the subproblems to discard most of them, but they need efficient pruning methods to discard regions of the subproblems that do not contain global minimizer points. The new pruning method presented here is based on the application of derivative information from the Baumann point. Numerical results were obtained by incorporating this new technique into a basic Interval B&B Algorithm in order to evaluate the achieved improvements. This work has been supported by the Ministry of Education and Science of Spain through grants TIC 2002-00228, TIN2005-00447, and research project SEJ2005-06273 and by the Integral Action between Spain and Hungary by grant HH2004-0014. Boglárka Tóth: On leave from the Research Group on Artificial Intelligence of the Hungarian Academy of Sciences and the University of Szeged, H-6720 Szeged, Aradi vértanúk tere 1., Hungary.     

On interval branch-and-bound for additively separable functions with common variables

Interval branch-and-bound (B&B) algorithms are powerful methods which look for guaranteed solutions of global optimisation problems. The computational effort needed to reach this aim, increases exponentially with the problem dimension in the worst case. For separable functions this effort is less, as lower dimensional sub-problems can be solved individually. The question is how to design specific methods for cases where the objective function can be considered separable, but common variables occur in the sub-problems. This paper is devoted to establish the bases of B&B algorithms for separable problems. New B&B rules are presented based on derived properties to compute bounds. A numerical illustration is elaborated with a test-bed of problems mostly generated by combining traditional box constrained global optimisation problems, to show the potential of using the derived theoretical basis.     

An exact depth-first algorithm for the pallet loading problem

This paper proposes a fast exact algorithm to solve the Pallet Loading Problem (PLP) using depth-first strategy. A new concept called Maximal Breadth Filling Sequence (MBFS) is introduced to bring down the size of the search tree. The algorithm makes use of two pruning rules — lower-bound pruning and state-dominance pruning. Although depth-first search, by itself, requires very little memory, the dominance pruning rule makes effective utilization of the available memory. For large problems, more the memory available, more effective is the dominance pruning. The algorithm has been tested on standard problem sets. It has been found to be quite fast in outputting optimal solutions. Empirical findings are given in detail.     

On estimating workload in interval branch-and-bound global optimization algorithms

In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.     

The design of corporate tax structures

We consider the corporate tax structuring problem (TaxSP), a combinatorial optimization problem faced by firms with multinational operations. The problem objective is nonlinear and involves the minimization of the firm's overall tax payments i.e. the maximization of shareholder returns. We give a dynamic programming (DP) formulation of this problem including all existing schemes of tax-relief and income-pooling. We apply state space relaxation and state space descent to the DP recursions and obtain an upper bound to the value of optimal TaxSP solutions. This bound is imbedded in a B&B tree search to provide another exact solution procedure. Computational results from DP and B&B are given for problems up to 22 subsidiaries. For larger size TaxSPs we develop a heuristic referred to as the Bionomic Algorithm (BA). This heuristic is also used to provide an initial lower bound to the B&B algorithm. We test the performance of BA firstly against the exact solutions of TaxSPs solvable by the B&B algorithm and secondly against results obtained for large-size TaxSPs by Simulated Annealing (SA) and Genetic Algorithms (GA). We report results for problems of up to 150 subsidiaries, including some real-world problems for corporations based in the US and the UK. Support for this work was provided by the IST Framework 5 Programme of the European Union, Contract IST2000-29405, Eurosignal ProjectMathematics Subject Classification (2000): 90C39, 91B28     

Global Optimization Issues in Multiparametric Continuous and Mixed-Integer Optimization Problems

In this paper, a number of theoretical and algorithmic issues concerning the solution of parametric nonconvex programs are presented. In particular, the need for defining a suitable overestimating subproblem is discussed in detail. The multiparametric case is also addressed, and a branch and bound (B&B) algorithm for the solution of parametric nonconvex programs is proposed.     

A local branching-based algorithm for the quay crane scheduling problem under unidirectional schedules

The quay crane scheduling problem (QCSP) is at the basis of a major logistic process in maritime container terminals: the process of discharging/loading containers from/on berthed vessels. Several groups of containers, laying in one or more stowage portions of a containership, have to be assigned to multiple cranes and discharge/loading operations have to be optimally sequenced, under some complicating constraints imposed by the practical working rules of quay cranes. The QCSP has been the object of a great deal of research work since the last decade and it is focused in this paper, with the aim of consolidating a promising solution approach based upon the combination of specialized branch & bound (B&B) and heuristic algorithms. A cost-effective solution technique that incorporates the local branching method within a refined B&B algorithm is proposed and its effectiveness is assessed by numerical comparisons against the latest algorithm available in literature.     

Dynamics for Linear Feedback Controlled Two-Dimensional Bénard Equations with Distributed Controls

The long-time behavior of solutions for some feedback distributed control problems associated with the Bénard equations is studied. Some linear feedback solutions for the Bénard equations are constructed. Then we prove that these feedback solutions possess the decay (in time) properties. Accepted 5 March 2001. Online publication 20 June 2001.     

Discrete and geometric Branch and Bound algorithms for?medical image registration

Aiming at the development of an exact solution method for registration problems, we present two different Branch & Bound algorithms for a mixed integer programming formulation of the problem. The first B&B algorithm branches on binary assignment variables and makes use of an optimality condition that is derived from a graph matching formulation. The second, geometric B&B algorithm applies a geometric branching strategy on continuous transformation variables. The two approaches are compared for synthetic test examples as well as for 2-dimensional medical data. The results show that medium sized problem instances can be solved to global optimality in a reasonable amount of time.     

Combining Metaheuristics and Exact Methods for Solving Exactly Multi-objective Problems on the Grid

This paper presents a parallel hybrid exact multi-objective approach which combines two metaheuristics – a genetic algorithm (GA) and a memetic algorithm (MA), with an exact method – a branch and bound (B&B) algorithm. Such approach profits from both the exploration power of the GA, the intensification capability of the MA and the ability of the B&B to provide optimal solutions with proof of optimality. To fully exploit the resources of a computational grid, the hybrid method is parallelized according to three well-known parallel models – the island model for the GA, the multi-start model for the MA and the parallel tree exploration model for the B&B. The obtained method has been experimented and validated on a bi-objective flow-shop scheduling problem. The approach allowed to solve exactly for the first time an instance of the problem – 50 jobs on 5 machines. More than 400 processors belonging to 4 different administrative domains have contributed to the resolution process during more than 6 days.      

Minimizing sum of completion times on a single machine with sequence-dependent family setup times

This paper presents a branch-and-bound (B&B) algorithm for minimizing the sum of completion times in a single-machine scheduling setting with sequence-dependent family setup times. The main feature of the B&B algorithm is a new lower bounding scheme that is based on a network formulation of the problem. With extensive computational tests, we demonstrate that the B&B algorithm can solve problems with up to 60 jobs and 12 families, where setup and processing times are uniformly distributed in various combinations of the [1,50] and [1,100] ranges.     

A co-operative parallel heuristic for mixed zero–one linear programming: Combining simulated annealing with branch and bound

This paper considers the exact approach of branch and bound (B&B) and the metaheuristic known as simulated annealing (SA) for processing integer programs (IP). We extend an existing SA implementation (GPSIMAN) for pure zero–one integer programs (PZIP) to process a wider class of IP models, namely mixed zero–one integer programs (MZIP). The extensions are based on depth-first B&B searches at different points within the SA framework. We refer to the resultant SA implementation as MIPSA. Furthermore, we have exploited the use of parallel computers by designing a co-operative parallel heuristic whereby concurrent executions of B&B and MIPSA, linked through a parallel computer, exchange information in order to influence their searches. Results reported for a wide range of models taken from a library of MIP benchmarks demonstrate the effectiveness of using a parallel computing approach which combines B&B with SA.     

Matching Stochastic Algorithms to Objective Function Landscapes

Large scale optimisation problems are frequently solved using stochastic methods. Such methods often generate points randomly in a search region in a neighbourhood of the current point, backtrack to get past barriers and employ a local optimiser. The aim of this paper is to explore how these algorithmic components should be used, given a particular objective function landscape. In a nutshell, we begin to provide rules for efficient travel, if we have some knowledge of the large or small scale geometry.     

Bounds on the size of branch-and-bound proofs for integer knapsacks

Using a direct counting argument, we derive lower and upper bounds for the number of nodes enumerated by linear programming-based branch-and-bound (B&B) method to prove the integer infeasibility of a knapsack. We prove by example that the size of the B&B tree could be exponential in the worst case.     

A Global Optimization RLT-based Approach for Solving the Fuzzy Clustering Problem

The field of cluster analysis is primarily concerned with the partitioning of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the fuzzy clustering problem, where each data point is to be assigned to (possibly) several clusters, with a membership grade assigned to each data point that reflects the likelihood of the data point belonging to that cluster. The fuzzy clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities. This construct is embedded within a specialized branch-and-bound (B&B) algorithm to solve the problem to global optimality. Computational experience is reported using several standard data sets from the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular fuzzy c-means algorithmic technique and the commercial global optimizer BARON.     

An exact algorithm for the fixed-charge multiple knapsack problem

We formulate the fixed-charge multiple knapsack problem (FCMKP) as an extension of the multiple knapsack problem (MKP). The Lagrangian relaxation problem is easily solved, and together with a greedy heuristic we obtain a pair of upper and lower bounds quickly. We make use of these bounds in the pegging test to reduce the problem size. We also present a branch-and-bound (B&B) algorithm to solve FCMKP to optimality. This algorithm exploits the Lagrangian upper bound as well as the pegging result for pruning, and at each terminal subproblem solve MKP exactly by invoking MULKNAP code developed by Pisinger [Pisinger, D., 1999. An exact algorithm for large multiple knapsack problems. European Journal of Operational Research 114, 528–541]. As a result, we are able to solve almost all test problems with up to 32,000 items and 50 knapsacks within a few seconds on an ordinary computing environment, although the algorithm remains some weakness for small instances with relatively many knapsacks.     

A branch-and-bound algorithm for a two-machine flowshop scheduling problem with limited waiting time constraints

In this paper, we consider a two-machine flowshop scheduling problem in which the waiting time of each job between the two machines cannot be greater than a certain time period. For the problem with the objective of minimizing makespan, we identify several dominance properties of the problem and develop a branch-and-bound (B&B) algorithm using the dominance properties. Computational tests are performed on randomly generated test problems for evaluation of performance of the B&B algorithm, and results show that the algorithm can solve problems with up to 150 jobs in a reasonable amount of CPU time.     

The two-echelon production-routing problem

This paper introduces the Two-Echelon Production-Routing Problem. This problem is motivated from the petrochemical industry, enlarging the supply chain integration by taking into account production, inventory, and routing decisions in a two-echelon vendor-managed inventory system. We describe, model, and design a branch-and-cut (B&C) to solve the problem under different inventory policies. We also propose a novel exact algorithm, by employing parallel computing techniques, in order to combine local search procedures within a traditional B&C scheme. We evaluate the performance of our methods through extensive computational experiments, both by comparing the algorithms, the effectiveness of the different inventory policies, and the impact of these policies on the partial costs. We derive many managerial insights based on the results. We also validate our new exact algorithm by solving similar problems from the literature, such as the two-echelon multi-depot inventory-routing (2E-MDIRP) and the classical multi-vehicle production-routing problem (MV-PRP). Computational experiments show that our method is very competitive. Based on 512 experiments for the 2E-MDIRP, our algorithm was able to find 111 new best known solutions (BKS), besides proving 412 optimal solutions, against 298 from the literature. For 336 experiments over small and medium size MV-PRP instances, we proved 242 optimal solutions, 11 more than the exact methods from the literature, besides providing 95 new BKS. Moreover, we were the first to tackle large MV-PRP instances exactly, and in this case, our algorithm provides all BKS for instances up to 50 customers, 20 periods and 5 vehicles, outperforming all meta/matheuristics procedures from the literature.