Multi-depot rural postman problems

This paper studies multi-depot rural postman problems on an undirected graph. These problems extend the well-known undirected rural postman problem to the case where there are several depots instead of just one. Linear integer programming formulations that only use binary variables are proposed for the problem that minimizes the overall routing costs and for the model that minimizes the length of the longest route. An exact branch-and-cut algorithm is presented for each considered model, where violated constraints of both types are separated in polynomial time. Despite the difficulty of the problems, the numerical results from a series of computational experiments with various types of instances illustrate a quite good behavior of the algorithms. When the overall routing costs are minimized, over 43 % of the instances were optimally solved at the root node, and 95 % were solved at termination, most of them with a small additional computational effort. When the length of the longest route is minimized, over 25 % of the instances were optimally solved at the root node, and 99 % were solved at termination.     

GRASP strategies for a bi-objective commercial territory design problem

A bi-objective commercial territory design problem motivated by a real-world application from the bottled beverage distribution industry is addressed. The problem considers territory compactness and balancing with respect to number of customers as optimization criteria. Previous work has focused on exact methods for small- to medium-scale instances. In this work, a GRASP framework is proposed for tackling considerably large instances. Within this framework two general schemes are developed. For each of these schemes two strategies are studied: (i) keeping connectivity as a hard constraint during construction and post-processing phases and, (ii) ignoring connectivity during the construction phase and adding this as another minimizing objective function during the post-processing phase. These strategies are empirically evaluated and compared to NSGA-II, one of the most successful evolutionary methods known in literature. Computational results show the superiority of the proposed strategies. In addition, one of the proposed GRASP strategies is successfully applied to a case study from industry.     

Optimal Scheduling of a Two-stage Hybrid Flow Shop

We present an exact branch-and-bound algorithm for the two-stage hybrid flow shop problem with multiple identical machines in each stage. The objective is to schedule a set of jobs so as to minimize the makespan. This is the first exact procedure which has been specifically designed for this strongly -hard problem. Among other features, our algorithm is based on the exact solution of identical parallel machine scheduling problems with heads and tails. We report the results of extensive computational experiments on instances which show that the proposed algorithm solves large-scale instances in moderate CPU time.     

Solving the asymmetric traveling purchaser problem

The Asymmetric Traveling Purchaser Problem (ATPP) is a generalization of the Asymmetric Traveling Salesman Problem with several applications in the routing and the scheduling contexts. This problem is defined as follows. Let us consider a set of products and a set of markets. Each market is provided with a limited amount of each product at a known price. The ATPP consists in selecting a subset of markets such that a given demand of each product can be purchased, minimizing the routing cost and the purchasing cost. The aim of this article is to evaluate the effectiveness of a branch-and-cut algorithm based on new valid inequalities. It also proposes a transformation of the ATPP into its symmetric version, so a second exact method is also presented. An extensive computational analysis on several classes of instances from literature evaluates the proposed approaches. A previous work () solves instances with up to 25 markets and 100 products, while the here-presented approaches prove optimality on instances with up to 200 markets and 200 products. Partially supported by “Ministerio de Ciencia y Tecnología” (TIC2003-05982-C05-02), and by Vicerrectorado de Investigación y Desarrollo Tecnológico de la Universidad de La Laguna.     

An exact algorithm for side-chain placement in protein design

Computational protein design aims at constructing novel or improved functions on the structure of a given protein backbone and has important applications in the pharmaceutical and biotechnical industry. The underlying combinatorial side-chain placement (SCP) problem consists of choosing a SCP for each residue position such that the resulting overall energy is minimum. The choice of the side-chain then also determines the amino acid for this position. Many algorithms for this NP{\mathcal{NP}}-hard problem have been proposed in the context of homology modeling, which, however, reach their limits when faced with large protein design instances. In this paper, we propose a new exact method for the SCP problem that works well even for large instance sizes as they appear in protein design. Our main contribution is a dedicated branch-and-bound algorithm that combines tight upper and lower bounds resulting from a novel Lagrangian relaxation approach for SCP. Our experimental results show that our method outperforms alternative state-of-the-art exact approaches and makes it possible to optimally solve large protein design instances routinely.     

Minimizing the weighted number of tardy jobs on a single machine with release dates

In this paper, we describe an exact algorithm to minimize the weighted number of tardy jobs on a single machine with release dates. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate the proposed exact algorithm solves either weighted or unweighted problems. It solves the hardest problems to date. Indeed, it solves all previously unsolved instances. Its run time is the shortest to date.     

An exact solution framework for the minimum cost dominating tree problem

The minimum cost dominating tree problem is a recently introduced NP-hard problem, which consists of finding a tree of minimal cost in a given graph, such that for every node of the graph, the node or one of its neighbours is in the tree. We present an exact solution framework combining a primal–dual heuristic with a branch-and-cut approach based on a transformation of the problem into a Steiner arborescence problem with an additional constraint. The effectiveness of our approach is evaluated on testbeds proposed in literature containing instances with up to 500 nodes. Our framework manages to solve all but four instances from literature to proven optimality within 3 h (most of them in a few seconds). We provide optimal solution values for 69 instances from literature for which the optimal solution was previously unknown.     

Learning heuristics for basic block instruction scheduling

Instruction scheduling is an important step for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block—a straight-line sequence of code with a single entry point and a single exit point—subject to precedence, latency, and resource constraints. Solving the problem exactly is known to be difficult, and most compilers use a greedy list scheduling algorithm coupled with a heuristic. The heuristic is usually hand-crafted, a potentially time-consuming process. In contrast, we present a study on automatically learning good heuristics using techniques from machine learning. In our study, a recently proposed optimal basic block scheduler was used to generate the machine learning training data. A decision tree learning algorithm was then used to induce a simple heuristic from the training data. The automatically constructed decision tree heuristic was compared against a popular critical-path heuristic on the SPEC 2000 benchmarks. On this benchmark suite, the decision tree heuristic reduced the number of basic blocks that were not optimally scheduled by up to 55% compared to the critical-path heuristic, and gave improved performance guarantees in terms of the worst-case factor from optimality.     

Parallel machine scheduling with general sum of processing time based models

In this paper, we analyse the parallel machine makespan minimization problem with the general sum of processing time based learning or aging effects. First, we prove that an optimal solution to the single machine case can be found by priority rules. Next, for the considered parallel machine problem, we construct the exact dynamic programming algorithm that can operate on real-valued job processing times, which is the only exact algorithm for the analysed problem. The computational analysis confirms that it can solve optimally moderate problem instances.     

A hybrid scatter search heuristic for personalized crew rostering in the airline industry

The crew scheduling problem in the airline industry is extensively investigated in the operations research literature since efficient crew employment can drastically reduce operational costs of airline companies. Given the flight schedule of an airline company, crew scheduling is the process of assigning all necessary crew members in such a way that the airline is able to operate all its flights and constructing a roster line for each employee minimizing the corresponding overall cost for personnel. In this paper, we present a scatter search algorithm for the airline crew rostering problem. The objective is to assign a personalized roster to each crew member minimizing the overall operational costs while ensuring the social quality of the schedule. We combine different complementary meta-heuristic crew scheduling combination and improvement principles. Detailed computational experiments in a real-life problem environment are presented investigating all characteristics of the procedure. Moreover, we compare the proposed scatter search algorithm with optimal solutions obtained by an exact branch-and-price procedure and a steepest descent variable neighbourhood search.     

A mixed integer linear programming formulation of the maximum betweenness problem

This paper considers the maximum betweenness problem. A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on randomly generated instances from the literature. The results of CPLEX solver, based on the proposed MILP formulation, are compared with results obtained by total enumeration technique. The results show that CPLEX optimally solves instances of up to 30 elements and 60 triples in a short period of time.     

A mathematical model and a metaheuristic approach for a memory allocation problem

Memory allocation in embedded systems is one of the main challenges that electronic designers have to face. This part, rather difficult to handle is often left to the compiler with which automatic rules are applied. Nevertheless, an optimal allocation of data to memory banks may lead to great savings in terms of running time and energy consumption. This paper introduces an exact approach and a vns-based metaheuristic for addressing a memory allocation problem. Numerical experiments have been conducted on real instances from the electronic community and on dimacs instances expanded for our specific problem.     

A dynamic programming algorithm for the space allocation and aisle positioning problem

The space allocation and aisle positioning problem (SAAPP) in a material handling system with gravity flow racks is the problem of minimizing the total number of replenishments over a period subject to practical constraints related to the need for aisles granting safe and easy access to storage locations. In this paper, we develop an exact dynamic programming algorithm for the SAAPP. The computational study shows that our exact algorithm can be used to find optimal solutions for numerous SAAPP instances of moderate size.     

Minimizing maximum lateness in a flow shop subject to release dates

We consider the problem of minimizing the maximum lateness in a m-machine flow shop subject to release dates. The objective of this paper is to develop a new branch-and-bound algorithm to solve exactly this strongly NP-hard problem. The proposed branch-and-bound algorithm encompasses several features including a procedure for adjusting heads and tails, heuristics, and a lower bounding procedure, which is based on the exact solution of the two-machine flow shop problem with time lags, ready times, and delivery times. Extensive computational experiments show that instances with up to 6000 operations can be solved exactly in a moderate CPU time.     

An exact algorithm for minimizing resource availability costs in project scheduling

A new exact algorithm that solves the Resource Availability Cost Problem (RACP) in project scheduling is shown to yield a significant improvement over the existing algorithm in the literature. The new algorithm consists of a hybrid method where an initial feasible solution is found heuristically. The branching scheme solves a Resource-Constrained Project Scheduling Problem (RCPSP) at each node where the resources of the RACP are fixed. The knowledge of previously solved RCPSPs is used to produce cuts in the search tree. A worst-case-performance theorem is established for this new algorithm. Experiments are performed on instances adapted from the PSPLIB database. The new algorithm can be used to minimize any resource availability cost problem once a procedure for the underlying resource-constrained problem is available.     

A capacitated hub location problem in freight logistics multimodal networks

In this paper we deal with a capacitated hub location problem arising in a freight logistics context; in particular, we have the need of locating logistics platforms for containers travelling via road and rail. The problem is modelled on a weighed multimodal network. We give a mixed integer linear programming model for the problem, having the goal of minimizing the location and shipping costs. The proposed formulation presents some novel features for modelling capacity bounds that are given both for the candidate hub nodes and the arcs incident to them; further, the containerised origin-destination (\(o-d)\) demand can be split among several platforms and different travelling modes. Note that here the network is not fully connected and only one hub for each \(o-d\) pair is used, serving both to consolidate consignments on less transport connections and as reloading point for a modal change. Results of an extensive computational experimentation performed with randomly generated instances of different size and capacity values are reported. In the test bed designed to validate the proposed model all the instances up to 135 nodes and 20 candidate hubs are optimally solved in few seconds by the commercial solver CPLEX 12.5.     

Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints

In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-and-price approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem.     

Solving real-world sized container pre-marshalling problems with an iterative deepening branch-and-bound algorithm

Container terminals around the world regularly re-sort the containers they store according to their retrieval times in a process called pre-marshalling, thus ensuring containers are efficiently transferred through the terminal. State-of-the-art algorithms struggle to find optimal solutions for real-world sized pre-marshalling problems. To this end, we introduce an improved exact algorithm using an iterative deepening branch and bound search, including a novel lower bound computation, a new branching heuristic, new dominance rule and a new greedy partial solution completion heuristic. Our approach finds optimal solutions for 161 more instances than the state-of-the-art algorithm on two well known, difficult pre-marshalling datasets, and solves all instances in three other datasets in just several seconds. Furthermore, we find optimal solutions for a majority of real-world sized instances, and feasible solutions with very low relaxation gaps on those instances where no optimal could be found.     

Bicriteria optimisation of the makespan and mean flowtime on two identical parallel machines

This paper proposes an efficient algorithm to solve optimally the bicriteria problem of minimising the weighted sum of makespan and mean flowtime on two identical parallel machines. The proposed algorithm allows the decision-maker to minimise makespan and flowtime simultaneously according to his or her relative preference as reflected through the weights placed on makespan and flowtime. Our computational results show that the proposed algorithm can solve optimally problem instances with a large number of jobs in a reasonably small amount of CPU time.     

A local search heuristic for the Multi-Commodity k-splittable Maximum Flow Problem

The Multi-Commodity $k$ -splittable Maximum Flow Problem consists of maximizing the amount of flow routed through a network such that each commodity uses at most $k$ paths and such that edge capacities are satisfied. The problem is $\mathcal NP $ -hard and has application in a.o. telecommunications. In this paper, a local search heuristic for solving the problem is proposed. The heuristic is an iterative shortest path procedure on a reduced graph combined with a local search procedure to modify certain path flows and prioritize the different commodities. The heuristic is tested on benchmark instances from the literature and solves 83 % of the instances to optimality. For the remaining instances, the heuristic finds good solution values which on average are 1.04 % from the optimal. The heuristic solves all instances in less than a second. Compared to other heuristics, the proposed heuristic again shows superior performance with respect to solution quality.