Combining very large scale and ILP based neighborhoods for a two-level location problem

In this paper we tackle a generalization of the Single Source Capacitated Facility Location Problem in which two sets of facilities, called intermediate level and upper level facilities, have to be located; the dimensioning of the intermediate set, the assignment of clients to intermediate level facilities, and of intermediate level facilities to upper level facilities, must be optimized, as well. Such problem arises, for instance, in telecommunication network design: in fact, in hierarchical networks the traffic arising at client nodes often have to be routed through different kinds of facility nodes, which provide different services. We propose a heuristic approach, based on very large scale neighborhood search to tackle the problem, in which both ad hoc algorithms and general purpose solvers are applied to explore the search space. We report on experimental results using datasets from the capacitated location literature. Such results show that the approach is promising and that Integer Linear Programming based neighborhoods are significantly effective.     

Genetic algorithms for the traveling salesman problem

This paper is a survey of genetic algorithms for the traveling salesman problem. Genetic algorithms are randomized search techniques that simulate some of the processes observed in natural evolution. In this paper, a simple genetic algorithm is introduced, and various extensions are presented to solve the traveling salesman problem. Computational results are also reported for both random and classical problems taken from the operations research literature.     

Dynamic tabu search strategies for the traveling purchaser problem

Tabu search is a metastrategy for guiding known heuristics to overcome local optimality with a large number of successful applications reported in the literature. In this paper we investigate two dynamic strategies, the reverse elimination method and the cancellation sequence method. The incorporation of strategic oscillation as well as a combination of these methods are developed. The impact of the different methods is shown with respect to the traveling purchaser problem, a generalization of the classical traveling salesman problem. The traveling purchaser problem is the problem of determining a tour of a purchaser buying several items in different shops by minimizing the total amount of travel and purchase costs. A comparison of the tabu search strategies with a simulated annealing approach is presented, too.     

A note on symmetry reduction for circular traveling tournament problems

The traveling tournament problem (TTP) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. Easton et al. (2001) introduced the so-called circular TTP instances, where venues of teams are located on a circle. The distance between neighboring venues is one, so that the distance between any pair of teams is the distance on the circle. It is empirically proved that these instances are very hard to solve due to the inherent symmetry. This note presents new ideas to cut off essentially identical parts of the solution space. Enumerative solution approaches, e.g. relying on branch-and-bound, benefit from this reduction. We exemplify this benefit by modifying the DFS∗ algorithm of Uthus et al. (2009) and show that speedups can approximate factor 4n.     

An effective greedy heuristic for the Social Golfer Problem

The Social Golfer Problem (SGP) is a combinatorial optimization problem that exhibits a lot of symmetry and has recently attracted significant attention. In this paper, we present a new greedy heuristic for the SGP, based on the intuitive concept of freedom among players. We use this heuristic in a complete backtracking search, and match the best current results of constraint solvers for several SGP instances with a much simpler method. We then use the main idea of the heuristic to construct initial configurations for a metaheuristic approach, and show that this significantly improves results obtained by local search alone. In particular, our method is the first metaheuristic technique that can solve the original problem instance optimally. We show that our approach is also highly competitive with other metaheuristic and constraint-based methods on many other benchmark instances from the literature.     

A new mixed integer linear programming model for the multi level uncapacitated facility location problem

This paper considers the multi level uncapacitated facility location problem (MLUFLP). A new mixed integer linear programming (MILP) formulation is presented and validity of this formulation is given. Experimental results are performed on instances known from literature. The results achieved by CPLEX and Gurobi solvers, based on the proposed MILP formulation, are compared to the results obtained by the same solvers on the already known formulations. The results show that CPLEX and Gurobi can optimally solve all small and medium sized instances and even some large-scale instances using the new formulation.     

On relaxations of the max k-cut problem formulations

A tight continuous relaxation is a crucial factor in solving mixed integer formulations of many NP-hard combinatorial optimization problems. The (weighted) max k-cut problem is a fundamental combinatorial optimization problem with multiple notorious mixed integer optimization formulations. In this paper, we explore four existing mixed integer optimization formulations of the max k-cut problem. Specifically, we show that the continuous relaxation of a binary quadratic optimization formulation of the problem is: (i) stronger than the continuous relaxation of two mixed integer linear optimization formulations and (ii) at least as strong as the continuous relaxation of a mixed integer semidefinite optimization formulation. We also conduct a set of experiments on multiple sets of instances of the max k-cut problem using state-of-the-art solvers that empirically confirm the theoretical results in item (i). Furthermore, these numerical results illustrate the advances in the efficiency of global non-convex quadratic optimization solvers and more general mixed integer nonlinear optimization solvers. As a result, these solvers provide a promising option to solve combinatorial optimization problems. Our codes and data are available on GitHub.     

Traveling salesman problem heuristics: Leading methods, implementations and latest advances

Heuristics for the traveling salesman problem (TSP) have made remarkable advances in recent years. We survey the leading methods and the special components responsible for their successful implementations, together with an experimental analysis of computational tests on a challenging and diverse set of symmetric and asymmetric TSP benchmark problems. The foremost algorithms are represented by two families, deriving from the Lin-Kernighan (LK) method and the stem-and-cycle (S&C) method. We show how these families can be conveniently viewed within a common ejection chain framework which sheds light on their similarities and differences, and gives clues about the nature of potential enhancements to today’s best methods that may provide additional gains in solving large and difficult TSPs.     

Discrete-time, economic lot scheduling problem on multiple, non-identical production lines

This paper deals with a general discrete time dynamic demand model to solve real time resource allocation and lot-sizing problems in a multimachine environment. In particular, the problem of apportioning item production to distinct manufacturing lines with different costs (production, setup and inventory) and capabilities is considered. Three models with different cost definitions are introduced, and a set of algorithms able to handle all the problems are developed. The computational results show that the best of the developed approaches is able to handle problems with up to 10000 binary variables outperforming general-purpose solvers and other randomized approaches. The gap between lower and upper bound procedures is within 1.0% after about 500 seconds of CPU time on a 2.66 Ghz Intel Core2 PC.     

A General VNS heuristic for the traveling salesman problem with time windows

This paper presents a General Variable Neighborhood Search (GVNS) heuristic for the Traveling Salesman Problem with Time Windows (TSPTW). The heuristic is composed by both constructive and optimization stages. In the first stage, the heuristic constructs a feasible solution using VNS, and in the optimization stage the heuristic improves the feasible solution with a General VNS heuristic. Both constructive and optimization stages take advantage of elimination tests, partial neighbor evaluation and neighborhood partitioning techniques. Experimental results show that this approach is efficient, reducing significantly the computation time and improving some best known results from the literature.     

A comprehensive comparison of metaheuristics for the repetition-free longest common subsequence problem

This paper deals with an NP-hard string problem from the bio-informatics field: the repetition-free longest common subsequence problem. This problem has enjoyed an increasing interest in recent years, which has resulted in the application of several pure as well as hybrid metaheuristics. However, the literature lacks a comprehensive comparison between those approaches. Moreover, it has been shown that general purpose integer linear programming solvers are very efficient for solving many of the problem instances that were used so far in the literature. Therefore, in this work we extend the available benchmark set, adding larger instances to which integer linear programming solvers cannot be applied anymore. Moreover, we provide a comprehensive comparison of the approaches found in the literature. Based on the results we propose a hybrid between two of the best methods which turns out to inherit the complementary strengths of both methods.     

Deep Learning for Constrained Utility Maximisation

This paper proposes two algorithms for solving stochastic control problems with deep learning, with a focus on the utility maximisation problem. The first algorithm solves Markovian problems via the Hamilton Jacobi Bellman (HJB) equation. We solve this highly nonlinear partial differential equation (PDE) with a second order backward stochastic differential equation (2BSDE) formulation. The convex structure of the problem allows us to describe a dual problem that can either verify the original primal approach or bypass some of the complexity. The second algorithm utilises the full power of the duality method to solve non-Markovian problems, which are often beyond the scope of stochastic control solvers in the existing literature. We solve an adjoint BSDE that satisfies the dual optimality conditions. We apply these algorithms to problems with power, log and non-HARA utilities in the Black-Scholes, the Heston stochastic volatility, and path dependent volatility models. Numerical experiments show highly accurate results with low computational cost, supporting our proposed algorithms.

     

A conic quadratic formulation for a class of convex congestion functions in network flow problems

In this paper we consider a multicommodity network flow problem with flow routing and discrete capacity expansion decisions. The problem involves trading off congestion and capacity assignment (or expansion) costs. In particular, we consider congestion costs involving convex, increasing power functions of flows on the arcs. We first observe that under certain conditions the congestion cost can be formulated as a convex function of the capacity level and the flow. Then, we show that the problem can be efficiently formulated by using conic quadratic inequalities. As most of the research on this problem is devoted to heuristic approaches, this study differs in showing that the problem can be solved to optimum by branch-and-bound solvers implementing the second-order cone programming (SOCP) algorithms. Computational experiments on the test problems from the literature show that the continuous relaxation of the formulation gives a tight lower bound and leads to optimal or near optimal integer solutions within reasonable CPU times.     

Heuristics for the mirrored traveling tournament problem

Professional sports leagues are a major economic activity around the world. Teams and leagues do not want to waste their investments in players and structure in consequence of poor schedules of games. Game scheduling is a difficult task, involving several decision makers, different types of constraints, and multiple objectives to optimize. The traveling tournament problem abstracts certain types of sport timetabling issues, where the objective is to minimize the total distance traveled by the teams. In this work, we tackle the mirrored version of this problem. We first propose a fast and effective constructive algorithm. We also describe a new heuristic based on the combination of the GRASP and iterated local search metaheuristics. A strong neighborhood based on ejection chains is also proposed and leads to significant improvements in solution quality. Very good solutions are obtained for the mirrored problem, sometimes even better than those found by other approximate algorithms for the less constrained non-mirrored version. Computational results are shown for benchmark problems and for a large instance associated with the main division of the 2003 edition of the Brazilian soccer championship, involving 24 teams.     

A branch-and-bound algorithm for hard multiple knapsack problems

The multiple knapsack problem (MKP) is a classical combinatorial optimization problem. A recent algorithm for some classes of the MKP is bin-completion, a bin-oriented, branch-and-bound algorithm. In this paper, we propose path-symmetry and path-dominance criteria for pruning nodes in the MKP branch-and-bound search space. In addition, we integrate the ??bound-and-bound?? upper bound validation technique used in previous MKP solvers. We show experimentally that our new MKP solver, which successfully integrates dominance based pruning, symmetry breaking, and bound-and-bound, significantly outperforms previous solvers on some classes of hard problem instances.     

A modeling framework and local search solution methodology for a production-distribution problem with supplier selection and time-aggregated quantity discounts

Supplier selection with quantity discounts has been an active research problem in the literature. In this paper, we focus on a new real-world quantity discounts scheme, where suppliers are selected in the beginning of a strategic planning period (e.g., 5 years). Monthly orders are placed from the selected suppliers, but the quantity discounts are based on the aggregated annual order quantities. We incorporate this type of cost structure in a multi-period, multi-product, multi-echelon supply chain planning problem, and develop a mixed integer linear programming (MIP) model for it. Our model is highly intractable; leading commercial solvers cannot construct high quality feasible solutions for realistic instances even after multiple hours of solution time. We develop an algorithm that constructs an initial feasible solution and a large neighborhood search method that combines two customized iterative algorithms based on MIP-based local search and improves such solution. We report numerical results for a food supply chain application and show the efficiency of using our methodology in getting very high quality primal solutions quickly.     

An Improved Bernstein Global Optimization Algorithm for MINLP Problems with Application in Process Industry

We present an improved Bernstein global optimization algorithm to solve polynomial mixed-integer nonlinear programming (MINLP) problems. The algorithm is of branch-and-bound type, and uses the Bernstein form of the polynomials for the global optimization. The new ingredients in the algorithm include a modified subdivision procedure, a vectorized Bernstein cut-off test and a new branching rule for the decision variables. The performance of the improved algorithm is tested and compared with earlier reported Bernstein global optimization algorithm (to solve polynomial MINLPs) and with several state-of-the-art MINLP solvers on a set of 19 test problems. The results of the tests show the superiority of the improved algorithm over the earlier reported Bernstein algorithm and the state-of-the-art solvers in terms of the chosen performance metrics. Similarly, efficacy of the improved algorithm in handling a real-world MINLP problem is brought out via a trim-loss minimization problem from the process industry.     

Interior Epigraph Directions method for nonsmooth and nonconvex optimization via generalized augmented Lagrangian duality

We propose and study a new method, called the Interior Epigraph Directions (IED) method, for solving constrained nonsmooth and nonconvex optimization. The IED method considers the dual problem induced by a generalized augmented Lagrangian duality scheme, and obtains the primal solution by generating a sequence of iterates in the interior of the dual epigraph. First, a deflected subgradient (DSG) direction is used to generate a linear approximation to the dual problem. Second, this linear approximation is solved using a Newton-like step. This Newton-like step is inspired by the Nonsmooth Feasible Directions Algorithm (NFDA), recently proposed by Freire and co-workers for solving unconstrained, nonsmooth convex problems. We have modified the NFDA so that it takes advantage of the special structure of the epigraph of the dual function. We prove that all the accumulation points of the primal sequence generated by the IED method are solutions of the original problem. We carry out numerical experiments by using test problems from the literature. In particular, we study several instances of the Kissing Number Problem, previously solved by various approaches such as an augmented penalty method, the DSG method, as well as several popular differentiable solvers. Our experiments show that the quality of the solutions obtained by the IED method is comparable with (and sometimes favourable over) those obtained by the differentiable solvers.     

A multi-round generalization of the traveling tournament problem and its application to Japanese baseball

In a double round-robin tournament involving n teams, every team plays 2(n − 1) games, with one home game and one away game against each of the other n − 1 teams. Given a symmetric n by n matrix representing the distances between each pair of home cities, the traveling tournament problem (TTP) seeks to construct an optimal schedule that minimizes the sum total of distances traveled by the n teams as they move from city to city, subject to several natural constraints to ensure balance and fairness. In the TTP, the number of rounds is set at r = 2. In this paper, we generalize the TTP to multiple rounds (r = 2k, for any k ? 1) and present an algorithm that converts the problem to finding the shortest path in a directed graph, enabling us to apply Dijkstra’s Algorithm to generate the optimal multi-round schedule. We apply our shortest-path algorithm to optimize the league schedules for Nippon Professional Baseball (NPB) in Japan, where two leagues of n = 6 teams play 40 sets of three intra-league games over r = 8 rounds. Our optimal schedules for the Pacific and Central Leagues achieve a 25% reduction in total traveling distance compared to the 2010 NPB schedule, implying the potential for considerable savings in terms of time, money, and greenhouse gas emissions.     

An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.