A multi-space sampling heuristic for the vehicle routing problem with stochastic demands

The vehicle routing problem with stochastic demands consists in designing transportation routes of minimal expected cost to satisfy a set of customers with random demands of known probability distributions. This paper proposes a simple yet effective heuristic approach that uses randomized heuristics for the traveling salesman problem, a tour partitioning procedure, and a set partitioning formulation to sample the solution space and find high-quality solutions for the problem. Computational experiments on benchmark instances from the literature show that the proposed approach is competitive with the state-of-the-art algorithm for the problem in terms of both accuracy and efficiency. In experiments conducted on a set of 40 instances, the proposed approach unveiled four new best-known solutions (BKSs) and matched another 24. For the remaining 12 instances, the heuristic reported average gaps with respect to the BKS ranging from 0.69 to 0.15 % depending on its configuration.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

Models and algorithms for three-stage two-dimensional bin packing

We consider the three-stage two-dimensional bin packing problem (2BP) which occurs in real-world applications such as glass, paper, or steel cutting. We present new integer linear programming formulations: models for a restricted version and the original version of the problem are developed. Both only involve polynomial numbers of variables and constraints and effectively avoid symmetries. Those models are solved using CPLEX. Furthermore, a branch-and-price (B&P) algorithm is presented for a set covering formulation of the unrestricted problem, which corresponds to a Dantzig-Wolfe decomposition of the polynomially-sized model. We consider column generation stabilization in the B&P algorithm using dual-optimal inequalities. Fast column generation is performed by applying a hierarchy of four methods: (a) a fast greedy heuristic, (b) an evolutionary algorithm, (c) solving a restricted form of the pricing problem using CPLEX, and finally (d) solving the complete pricing problem using CPLEX. Computational experiments on standard benchmark instances document the benefits of the new approaches: The restricted version of the integer linear programming model can be used to quickly obtain near-optimal solutions. The unrestricted version is computationally more expensive. Column generation provides a strong lower bound for 3-stage 2BP. The combination of all four pricing algorithms and column generation stabilization in the proposed B&P framework yields the best results in terms of the average objective value, the average run-time, and the number of instances solved to proven optimality.     

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.     

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     

A proposal for a hybrid meta-strategy for combinatorial optimization problems

In this paper, we propose an algorithm named BDS (Bound-Driven Search) that combines features of exact and approximate methods. The proposed procedure may be seen as a local search algorithm that systematically explores (in a branch-and bound sense) the most promising nodes, thus preventing solutions from being reevaluated. Additionally, it can be regarded as an exact method as it may be able to guarantee that the solution found is optimal. We present the application of this new algorithm to a specific problem domain: the permutation flow shop scheduling problem with makespan objective. The subsequent computational experiments are encouraging, as the algorithm is able to yield exact or near exact solutions to most instances of the problem. Furthermore, the algorithm outperforms one of the best state-of-the-art algorithms for the problem.     

Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear optimization

We further improve our methodology for solving irregular packing and cutting problems. We deal with an accurate representation of objects bounded by circular arcs and line segments and allow their continuous rotations and translations within rectangular and circular containers. We formulate a basic irregular placement problem which covers a wide spectrum of packing and cutting problems. We provide an exact non-linear programming (NLP) model of the problem, employing ready-to-use phi-functions. We develop an efficient solution algorithm to search for local optimal solutions for the problem in a reasonable time. The algorithm reduces our problem to a sequence of NLP subproblems and employs optimization procedures to generate starting feasible points and feasible subregions. Our algorithm allows us to considerably reduce the number of inequalities in NLP subproblems. To show the benefits of our methodology we give computational results for a number of new challenger and the best known benchmark instances.     

A branch-and-price algorithm for a vehicle routing with demand allocation problem

We investigate the vehicle routing with demand allocation problem where the decision-maker jointly optimizes the location of delivery sites, the assignment of customers to (preferably convenient) delivery sites, and the routing of vehicles operated from a central depot to serve customers at their designated sites. We propose an effective branch-and-price (B&P) algorithm that is demonstrated to greatly outperform the use of commercial branch-and-bound/cut solvers such as CPLEX. Central to the efficacy of the proposed B&P algorithm is the development of a specialized dynamic programming procedure that extends works on elementary shortest path problems with resource constraints in order to solve the more complex column generation pricing subproblem. Our computational study demonstrates the efficacy of the proposed approach using a set of 60 problem instances. Moreover, the proposed methodology has the merit of providing optimal solutions in run times that are significantly shorter than those reported for decomposition-based heuristics in the literature.     

A hybrid tabu search/branch & bound approach to solving the generalized assignment problem

A new approach for solving the generalized assignment problem (GAP) is proposed that combines the exact branch & bound approach with the heuristic strategy of tabu search (TS) to produce a hybrid algorithm for solving GAP. The algorithm described uses commercial software to solve sub-problems generated by the TS guiding strategy. The TS approach makes use of the concept of referent domain optimisation and introduces novel add/drop strategies. In addition, the linear programming relaxation of GAP that forms part of the branch & bound approach is itself helpful in suggesting which variables might take binary values. Computational results on benchmark test instances are presented and compared with results obtained by the standard branch & bound approach and also several other heuristic approaches from the literature. The results show the new algorithm performs competitively against the alternatives and is able to find some new best solutions for several benchmark instances.     

Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions

In this paper, we consider a capacitated single-level dynamic lot-sizing problem with sequence-dependent setup costs and times that includes product substitution options. The model is motivated from a real-world production planning problem of a manufacturer of plastic sheets used as an interlayer in car windshields. We develop a mixed-integer programming (MIP) formulation of the problem and devise MIP-based Relax&Fix and Fix&Optimize heuristics. Unlike existing literature, we combine Fix&Optimize with a time decomposition. Also, we develop a specialized substitute decomposition and devise a computation budget allocation scheme for ensuring a uniform, efficient usage of computation time by decompositions and their subproblems. Computational experiments were performed on generated instances whose structure follows that of the considered practical application and which have rather tight production capacities. We found that a Fix&Optimize algorithm with an overlapping time decomposition yielded the best solutions. It outperformed the state-of-the-art approach Relax&Fix and all other tested algorithm variants on the considered class of instances, and returned feasible solutions with neither overtime nor backlogging for all instances. It returned solutions that were on average only 5% worse than those returned by a standard MIP solver after 4 hours and 19% better than those of Relax&Fix.     

A three-phase matheuristic for capacitated multi-commodity fixed-cost network design with design-balance constraints

This paper proposes a three-phase matheuristic solution strategy for the capacitated multi-commodity fixed-cost network design problem with design-balance constraints. The proposed matheuristic combines exact and neighbourhood-based methods. Tabu search and restricted path relinking meta-heuristics cooperate to generate as many feasible solutions as possible. The two meta-heuristics incorporate new neighbourhoods, and computationally efficient exploration procedures. The feasible solutions generated by the two procedures are then used to identify an appropriate part of the solution space where an exact solver intensifies the search. Computational experiments on benchmark instances show that the proposed algorithm finds good solutions to large-scale problems 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.      

A decomposition approach for facility location and relocation problem with uncertain number of future facilities

In this paper, we discuss two challenges of long term facility location problem that occur simultaneously; future demand change and uncertain number of future facilities. We introduce a mathematical model that minimizes the initial and expected future weighted travel distance of customers. Our model allows relocation for the future instances by closing some of the facilities that were located initially and opening new ones, without exceeding a given budget. We present an integer programming formulation of the problem and develop a decomposition algorithm that can produce near optimal solutions in a fast manner. We compare the performance of our mathematical model against another method adapted from the literature and perform sensitivity analysis. We present numerical results that compare the performance of the proposed decomposition algorithm against the exact algorithm for the problem.     

A branch and price solution approach for order acceptance and capacity planning in make-to-order operations

Make-to-order (MTO) operations have to effectively manage their capacity to make long-term sustainable profits. This objective can be met by selectively accepting available customer orders and simultaneously planning for capacity. We model a MTO operation of a job-shop with multiple resources having regular and non-regular capacity. The MTO firm has a set of customer orders at time zero with fixed due-dates. The process route, processing times, and sales price for each order are given. Since orders compete for limited resources, the firm can only accept some orders. In this paper a Mixed-Integer Linear Program (MILP) is proposed to aid an operational manager to decide which orders to accept and how to allocate resources such that the overall profit is maximized. A branch-and-price (B&P) algorithm is devised to solve the MILP effectively. The MILP is first decomposed into a master problem and several sub-problems using Dantzig-Wolfe decomposition. Each sub-problem is represented as a network flow problem and an exact procedure is proposed to solve the sub-problems efficiently. We also propose an approximate B&P scheme, Lagrangian bounds, and approximations to fathom nodes in the branch-and-bound tree. Computational analysis shows that the proposed B&P algorithm can solve large problem instances with relatively short time.     

An application of the branch,bound, and remember algorithm to a new simple assembly line balancing dataset

The simple assembly line balancing problem (SALBP) is a well-studied NP-complete problem for which a new problem database of generated instances was published in 2013. This paper describes the application of a branch, bound, and remember (BB&R) algorithm using the cyclic best-first search strategy to this new database to produce provably exact solutions for 86% of the unsolved problems in this database. A new backtracking rule to save memory is employed to allow the BB&R algorithm to solve many of the largest problems in the database.     

Integrated location and two-echelon inventory network design under uncertainty

In this paper, we propose a two-stage stochastic model to address the design of an integrated location and two-echelon inventory network under uncertainty. The central issue in this problem is to design and operate an effective and efficient multi-echelon supply chain distribution network and to minimize the expected system-wide cost of warehouse location, the allocation of warehouses to retailers, transportation, and two-echelon inventory over an infinite planning horizon. We structure this problem as a two-stage nonlinear discrete optimization problem. The first stage decides the warehouses to open and the second decides the warehouse-retailer assignments and two-echelon inventory replenishment strategies. Our modeling strategy incorporates various probable scenarios in the integrated multi-echelon supply chain distribution network design to identify solutions that minimize the first stage costs plus the expected second stage costs. The two-echelon inventory cost considerations result in a nonlinear objective which we linearize with an exponential number of variables. We solve the problem using column generation. Our computational study indicates that our approach can solve practical problems of moderate-size with up to twenty warehouse candidate locations, eighty retailers, and ten scenarios efficiently.     

Hybrid algorithm for a vendor managed inventory system in a two-echelon supply chain

In this paper we address the issue of vendor managed inventory (VMI) by considering a two-echelon single vendor/multiple buyer supply chain network. We try to find the optimal sales quantity by maximizing profit, given as a nonlinear and non-convex objective function. For such complicated combinatorial optimization problems, exact algorithms and optimization commercial software such as LINGO are inefficient, especially on practical-size problems. In this paper we develop a hybrid genetic/simulated annealing algorithm to deal with this nonlinear problem. Our results demonstrate that the proposed hybrid algorithm outperforms previous methodologies and achieves more robust solutions.     

Scatter search for project scheduling with resource availability cost

This paper considers a project scheduling problem with the objective of minimizing resource availability costs, taking into account a deadline for the project and precedence relations among the activities. Exact methods have been proposed for solving this problem, but we are not aware of existing heuristic methods. Scatter search is used to tackle this problem, and our implementation incorporates advanced strategies such as dynamic updating of the reference set, the use of frequency-based memory within the diversification generator, and a combination method based on path relinking. We also analyze the merit of employing a subset of different types when combining solutions. Extensive computational experiments involving more than 2400 instances are performed. For small instances, the performance of the proposed procedure is compared to optimal solutions generated by an exact cutting plane algorithm and upper and lower bounds from the literature. For medium and larger size instances, we developed simple multi-start heuristics and comparative results are reported.