Accelerating Branch-and-Bound through a Modeling Language Construct for Relaxation-Specific Constraints

In the tradition of modeling languages for optimization, a single model is passed to a solver for solution. In this paper, we extend BARON’s modeling language in order to facilitate the communication of problem-specific relaxation information from the modeler to the branch-and-bound solver. This effectively results into two models being passed from the modeling language to the solver. Three important application areas are identified and computational experiments are presented. In all cases, nonlinear constraints are provided only to the relaxation constructor in order to strengthen the lower bounding step of the algorithm without complicating the local search process. In the first application area, nonlinear constraints from the reformulation–linearization technique (RLT) are added to strengthen a problem formulation. This approach is illustrated for the pooling problem and computational results show that it results in a scheme that makes global optimization nearly as fast as local optimization for pooling problems from the literature. In the second application area, we communicate with the relaxation constructor the first-order optimality conditions for unconstrained global optimization problems. Computational experiments with polynomial programs demonstrate that this approach leads to a significant reduction of the size of the branch-and-bound search tree. In the third application, problem-specific nonlinear optimality conditions for the satisfiability problem are used to strengthen the lower bounding step and are found to significantly expedite the branch-and-bound algorithm when applied to a nonlinear formulation of this problem.     

A hybrid approach combining interior-point and branch-and-bound methods applied to the problem of sugar cane waste

This paper proposes a hybrid approach for solving the multi-objective model related to the minimisation of sugar cane waste collection costs and/or the maximisation of produced energy by this waste, with the aid of strategies for solving multi-objective problems, which transform the problem into a set of single-objective problems. This approach combines the predictor-corrector primal-dual interior-point and branch-and-bound methods in order to solve these single-objective problems. The model consists in identifying the sugar cane varieties with the lowest waste collection costs, while simultaneously it aims to obtain the greatest amount of produced energy by this waste. The hybrid methods are implemented in C++ programming language, and tests are performed to determine the efficient solutions in Pareto optimal sense of the multi-objective model and compare the performance of the hybrid method using the integrality test and without considering it. The mathematical results confirm that the proposed hybrid method for solving the aforementioned models presents good computational performance and reliable solutions.     

A heterogeneous cooperative parallel search of branch-and-bound method and tabu search algorithm

In this study, we present a heterogeneous cooperative parallel search that integrates branch-and-bound method and tabu search algorithm. These two algorithms perform searches in parallel and cooperate by asynchronously exchanging information about the best solutions found and new initial solutions for tabu search. The rapid production of a good solution from the tabu search process provides the branch-and-bound process with a better feasible solution to accelerate the elimination of subproblems that do not contain an optimal solution. The new initial solution produced from the subproblem with a least-cost lower bound of the branch-and-bound method suggests the best potential area for tabu search to explore. We use a master-slave model to reduce the complexity of communication and enhance the performance of data exchange. A branch-and-bound process is used as the master process to control the exchange of information and the termination of computation. Several tabu search processes are executed simultaneously as the slave processes and cooperate by asynchronously exchanging information on the best solutions found and the new initial solutions by the master process of branch-and-bound. Based on the computation experiments of solving traveling salesman problems (TSP), the proposed heterogeneous parallel search algorithm outperforms a conventional parallel branch-and-bound method and a conventional parallel tabu search. We also present the computational results showing the efficiency of heterogeneous cooperative parallel search when we use more processors to accelerate search time. Thus, the proposed heterogeneous parallel search algorithm achieves linear accelerations.     

A time-indexed LP-based approach for min-sum job-shop problems

In this paper we propose two time-indexed IP formulations for job-shop scheduling problems with a min-sum objective. The first model has variables associated to job scheduling patterns. The exponential number of variables calls for a column generation scheme which is carried out by a dynamic programming procedure. The second model is of network flow type with side constraints. This model can be strengthened by adding cutting inequalities of clique type. It turns out that the two models are equivalent, since the dual of the second formulation is equivalent to the compact dual of the first model. However, they require significantly different solution approaches and may behave differently in terms of computing time and memory usage. Good upper bounds are found by a heuristic procedure that randomly generates schedules from fractional solutions. These features allow for an effective pruning of the branch-and-bound tree and narrowing the gap between lower and upper bounds. However, the size of both models is critically affected by the time-indexed formulation which may heavily slow down the computation.     

A global optimization algorithm for reliable network design

In this paper, we consider the problem of designing reliable networks that satisfy supply/demand, flow balance, and capacity constraints, while simultaneously allocating certain resources to mitigate the arc failure probabilities in such a manner as to minimize the total cost of network design and resource allocation. The resulting model formulation is a nonconvex mixed-integer 0-1 program, for which a tight linear programming relaxation is derived using RLT-based variable substitution strategies and a polyhedral outer-approximation technique. This LP relaxation is subsequently embedded within a specialized branch-and-bound procedure, and the proposed approach is proven to converge to a global optimum. Various alternative partitioning strategies that could potentially be employed in the context of this branch-and-bound framework, while preserving the theoretical convergence property, are also explored. Computational results are reported for a hypothetical scenario based on different parameter inputs and alternative branching strategies. Related optimization models that conform to the same class of problems are also briefly presented.     

Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations

In this work, we take advantage of the powerful quadratic programming theory to obtain optimal solutions of scheduling problems. We apply a methodology that starts, in contrast to more classical approaches, by formulating three unrelated parallel machine scheduling problems as 0–1 quadratic programs under linear constraints. By construction, these quadratic programs are non-convex. Therefore, before submitting them to a branch-and-bound procedure, we reformulate them in such a way that we can ensure convexity and a high-quality continuous lower bound. Experimental results show that this methodology is interesting by obtaining the best results in literature for two of the three studied scheduling problems.     

Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation

We present a novel generic programming implementation of a column-generation algorithm for the generalized staff rostering problem. The problem is represented as a generalized set partitioning model, which is able to capture commonly occurring problem characteristics given in the literature. Columns of the set partitioning problem are generated dynamically by solving a pricing subproblem, and constraint branching in a branch-and-bound framework is used to enforce integrality. The pricing problem is formulated as a novel three-stage nested shortest path problem with resource constraints that exploits the inherent problem structure. A very efficient implementation of this pricing problem is achieved by using generic programming principles in which careful use of the C++ pre-processor allows the generator to be customized for the target problem at compile-time. As well as decreasing run times, this new approach creates a more flexible modeling framework that is well suited to handling the variety of problems found in staff rostering. Comparison with a more-standard run-time customization approach shows that speedups of around a factor of 20 are achieved using our new approach. The adaption to a new problem is simple and the implementation is automatically adjusted internally according to the new definition. We present results for three practical rostering problems. The approach captures all features of each problem and is able to provide high-quality solutions in less than 15 minutes. In two of the three instances, the optimal solution is found within this time frame.     

Modeling target volume flows in forest harvest scheduling subject to maximum area restrictions

In forest harvest scheduling problems, one must decide which stands to harvest in each period during a planning horizon. A typical requirement in these problems is a steady flow of harvested timber, mainly to ensure that the industry is able to continue operating with similar levels of machine and labor utilizations. The integer programming approaches described use the so-called volume constraints to impose such a steady yield. These constraints do not directly impose a limit on the global deviation of the volume harvested over the planning horizon or use pre-defined target harvest levels. Addressing volume constraints generally increases the difficulty of solving the integer programming formulations, in particular those proposed for the area restriction model approach. In this paper, we present a new type of volume constraint as well as a multi-objective programming approach to achieve an even flow of timber. We compare the main basic approaches from a computational perspective. The new volume constraints seem to more explicitly control the global deviation of the harvested volume, while the multi-objective approach tends to provide the best profits for a given dispersion of the timber flow. Neither approach substantially changed the computational times involved.     

Combined vehicle routing and scheduling with temporal precedence and synchronization constraints

We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where in the literature the temporal constraints are usually remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usefulness. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct use of a commercial solver against the proposed heuristic, where the latter approach can find high quality solutions within specific time limits.     

A time indexed formulation of non-preemptive single machine scheduling problems

We consider the formulation of non-preemptive single machine scheduling problems using time-indexed variables. This approach leads to very large models, but gives better lower bounds than other mixed integer programming formulations. We derive a variety of valid inequalities, and show the role of constraint aggregation and the knapsack problem with generalised upper bound constraints as a way of generating such inequalities. A cutting plane/branch-and-bound algorithm based on these inequalities has been implemented. Computational experience on small problems with 20/30 jobs and various constraints and objective functions is presented.The research of this author was partially supported by JNICT/INVOTAN under grant No. 30/A/85/PO and by the PAC, contract No. 87/92-106, for computation.     

Valid inequalities and restrictions for stochastic programming problems with first order stochastic dominance constraints

Stochastic dominance relations are well studied in statistics, decision theory and economics. Recently, there has been significant interest in introducing dominance relations into stochastic optimization problems as constraints. In the discrete case, stochastic optimization models involving second order stochastic dominance constraints can be solved by linear programming. However, problems involving first order stochastic dominance constraints are potentially hard due to the non-convexity of the associated feasible regions. In this paper we consider a mixed 0–1 linear programming formulation of a discrete first order constrained optimization model and present a relaxation based on second order constraints. We derive some valid inequalities and restrictions by employing the probabilistic structure of the problem. We also generate cuts that are valid inequalities for the disjunctive relaxations arising from the underlying combinatorial structure of the problem by applying the lift-and-project procedure. We describe three heuristic algorithms to construct feasible solutions, based on conditional second order constraints, variable fixing, and conditional value at risk. Finally, we present numerical results for several instances of a real world portfolio optimization problem. This research was supported by the NSF awards DMS-0603728 and DMI-0354678.     

Human resources management at a marine container terminal

We consider the manpower planning problem in the real context of a marine container terminal. The main features of this problem are the uncertainty of workforce demand and the need of ensuring a time continuous efficiency of the terminal, which enforces to decompose the problem into two phases: a long-period planning first and then a daily planning.We propose mathematical programming models for both problems and suitably tailor them to the container terminal at the Gioia Tauro port. We derive solution algorithms by exploiting the mathematical properties of the models: a heuristic approach to a set-covering type problem for the long-term planning, and a branch-and-bound algorithm for the short-term planning. Finally, we report computational results on some real instances.     

A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems

This paper presents a hybrid multi-objective model that combines integer programming (IP) and variable neighbourhood search (VNS) to deal with highly-constrained nurse rostering problems in modern hospital environments. An IP is first used to solve the subproblem which includes the full set of hard constraints and a subset of soft constrains. A basic VNS then follows as a postprocessing procedure to further improve the IP’s resulting solutions. The satisfaction of the excluded constraints from the preceding IP model is the major focus of the VNS. Very promising results are reported compared with a commercial genetic algorithm and a hybrid VNS approach on real instances arising in a Dutch hospital. The comparison results demonstrate that our hybrid approach combines the advantages of both the IP and the VNS to beat other approaches in solving this type of problems. We also believe that the proposed methodology can be applied to other resource allocation problems with a large number of constraints.     

Reducing costs of backhaul networks for PCS networks using genetic algorithms

Designing cost-effective telecommunications networks often involves solving several challenging, interdependent combinatorial optimization problems simultaneously. For example, it may be necessary to select a least-cost subset of locations (network nodes) to serve as hubs where traffic is to be aggregated and switched; optimally assign other nodes to these hubs, meaning that the traffic entering the network at these nodes will be routed to the assigned hubs while respecting capacity constraints on the links; and optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these three combinatorial optimization problems must be solved while taking into account its impacts on the other two. This paper introduces a genetic algorithm (GA) approach that has proved effective in designing networks for carrying personal communications services (PCS) traffic. The key innovation is to represent information about hub locations and their interconnections as two parts of a chromosome, so that solutions to both aspects of the problem evolve in parallel toward a globally optimal solution. This approach allows realistic problems that take 4–10 hours to solve via a more conventional branch-and-bound heuristic to be solved in 30–35 seconds. Applied to a real network design problem provided as a test case by Cox California PCS, the heuristics successfully identified a design 10% less expensive than the best previously known design. Cox California PCS has adopted the heuristic results and plans to incorporate network optimization in its future network designs and requests for proposals.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem

In this paper, we present a branch-and-bound approach for solving a two-machine flow shop scheduling problem, in which the objective is to minimize a weighted combination of job flowtime and schedule makespan. Experimental results show that the algorithm works very well for certain special cases and moderately well for others. In fact, it is able to produce optimal schedules for 500-job problems in which the second machine dominates the first machine. It is also shown that the algorithm developed to provide an upper bound for the branch-and-bound is optimal when processing times for jobs are the same on both machines. The primary reason for developing the branch-and-bound approach is that its results can be used to guide other heuristic techniques, such as simulated annealing, tabu search and genetic algorithms, in their search for optimal solutions for larger problems.     

Nonsmooth exclusion test for finding all solutions of nonlinear equations

A new approach is proposed for finding all real solutions of systems of nonlinear equations with bound constraints. The zero finding problem is converted to a global optimization problem whose global minima with zero objective value, if any, correspond to all solutions of the original problem. A branch-and-bound algorithm is used with McCormick’s nonsmooth convex relaxations to generate lower bounds. An inclusion relation between the solution set of the relaxed problem and that of the original nonconvex problem is established which motivates a method to generate automatically, starting points for a local Newton-type method. A damped-Newton method with natural level functions employing the restrictive monotonicity test is employed to find solutions robustly and rapidly. Due to the special structure of the objective function, the solution of the convex lower bounding problem yields a nonsmooth root exclusion test which is found to perform better than earlier interval-analysis based exclusion tests. Both the componentwise Krawczyk operator and interval-Newton operator with Gauss-Seidel based root inclusion and exclusion tests are also embedded in the proposed algorithm to refine the variable bounds for efficient fathoming of the search space. The performance of the algorithm on a variety of test problems from the literature is presented, and for most of them, the first solution is found at the first iteration of the algorithm due to the good starting point generation.     

A Global Optimization Approach to a Water Distribution Network Design Problem

In this paper, we address a global optimization approach to a waterdistribution network design problem. Traditionally, a variety of localoptimization schemes have been developed for such problems, each new methoddiscovering improved solutions for some standard test problems, with noknown lower bound to test the quality of the solutions obtained. A notableexception is a recent paper by Eiger et al. (1994) who present a firstglobal optimization approach for a loop and path-based formulation of thisproblem, using a semi-infinite linear program to derive lower bounds. Incontrast, we employ an arc-based formulation that is linear except forcertain complicating head-loss constraints and develop a first globaloptimization scheme for this model. Our lower bounds are derived through thedesign of a suitable Reformulation-Linearization Technique (RLT) thatconstructs a tight linear programming relaxation for the given problem, andthis is embedded within a branch-and-bound algorithm. Convergence to anoptimal solution is induced by coordinating this process with an appropriatepartitioning scheme. Some preliminary computational experience is providedon two versions of a particular standard test problem for the literature forwhich an even further improved solution is discovered, but one that isverified for the first time to be an optimum, without any assumed boundson the flows. Two other variants of this problem are also solved exactly forillustrative purposes and to provide researchers with additional test caseshaving known optimal solutions. Suggestions on a more elaborate study involving several algorithmic enhancements are presented for futureresearch.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.