A multi-stop routing problem

The problem of determining the sequence of stops and the amount of load to carry in each segment route, named the Multi-Stop Routing Problem (MSRP) is addressed. A 0/1 mixed integer linear program and formulation refinements which facilitate the solution process are presented. Since the constraint set of the MSRP includes 0/1 mixed rows, valid inequalities for this type of regions are presented. Then these results are applied to the constraint set of the routing problem, presenting additional valid inequalities. In addition, polynomial separation algorithms associated with the valid inequalities are given, computational results are also included.     

Solving a minimum-power covering problem with overlap constraint for cellular network design

We consider a type of covering problem in cellular networks. Given the locations of base stations, the problem amounts to determining cell coverage at minimum cost in terms of the power usage. Overlap between adjacent cells is required in order to support handover. The problem we consider is NP-hard. We present integer linear models and study the strengths of their continuous relaxations. Preprocessing is used to reduce problem size and tighten the models. Moreover, we design a tabu search algorithm for finding near-optimal solutions effectively and time-efficiently. We report computational results for both synthesized instances and networks originating from real planning scenarios. The results show that one of the integer models leads to tight bounds, and the tabu search algorithm generates high-quality solutions for large instances in short computing time.     

Hybrid heuristics for a short sea inventory routing problem

We consider a short sea fuel oil distribution problem where an oil company is responsible for the routing and scheduling of ships between ports such that the demand for various fuel oil products is satisfied during the planning horizon. The inventory management has to be considered at the demand side only, and the consumption rates are given and assumed to be constant within the planning horizon. The objective is to determine distribution policies that minimize the routing and operating costs, while the inventory levels are maintained within their limits. We propose an arc-load flow formulation for the problem which is tightened with valid inequalities. In order to obtain good feasible solutions for planning horizons of several months, we compare different hybridization strategies. Computational results are reported for real small-size instances.     

A large scale machine loading problem in flexible assembly

Flexible manufacturing is characterized by versatile work stations with minimum change over times and a versatile material handling system. The loading problem in flexible manufacturing is to assign tools, material, operations and jobs to work stations in order to minimize the total number of job-to-work station assignments. In this paper, we describe a special case of the general loading problem applied to flexible assembly and develop a discrete optimization model. We then discuss approaches for obtaining good heuristic solutions and present results for a large scale study.     

A cutting plane procedure for the travelling salesman problem on road networks

A cutting plane algorithm for the exact solution of the symmetric travelling salesman problem (TSP) is proposed. The real tours on a usually incomplete road network, which are in general non-Hamiltonian, are characterized directly by an integer linear programming model. The algorithm generates special cutting planes for this model. Computational results for real road networks with up to 292 visiting places are reported, as well as for classical problems of the literature with up to 120 cities. Some of the latter problems have been solved for the first time with a pure cutting plane approach.     

The time constrained maximal covering salesman problem

We introduce the time constrained maximal covering salesman problem (TCMCSP) which is the generalization of the covering salesman and orienting problems. In this problem, we are given a set of vertices including a central depot, customer and facility vertices where each facility can supply the demand of some customers within its pre-determined coverage distance. Starting from the depot, the goal is to maximize the total number of covered customers by constructing a length constrained Hamiltonian cycle over a subset of facilities. We propose several mathematical programming models for the studied problem followed by a heuristic algorithm. The developed algorithm takes advantage of different procedures including swap, deletion, extraction-insertion and perturbation. Finally, an integer linear programming based improvement technique is designed to try to improve the quality of the solutions. Extensive computational experiments on a set of randomly generated instances indicate the effectiveness of the algorithm.     

A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem

In this paper, we consider an extension of the Markovitz model, in which the variance has been replaced with the Value-at-Risk. So a new portfolio optimization problem is formulated. We showed that the model leads to an NP-hard problem, but if the number of past observation T or the number of assets K are low, e.g. fixed to a constant, polynomial time algorithms exist. Furthermore, we showed that the problem can be formulated as an integer programming instance. When K and T are large and α^VaR is small—as common in financial practice—the computational results show that the problem can be solved in a reasonable amount of time.     

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.     

‘Multidimensional’ extensions and a nested dual approach for the m-median problem

A general framework for modeling median type locational decisions, where (i) travel costs and demands may be stochastic, (ii) multiple services or commodities need to be considered, and/or (iii) multiple median type objectives might exist, is presented—using the concept of “multidimensional networks”. The classical m-median problem, the stochastic m-median problem, the multicommodity m-median problem and and multiobjective m-median problem are defined within this framework.By an appropriate transformation of variables, the multidimensional m-median problem simplifies to the classical m-median problem but with a K-fold increase in the number of nodes, where K is the number of dimensions of the network. A nested dual approach to solve the resulting classical m-median problem, that uses Erlenkotter's facility location scheme as a subroutine, is presented. Computational results indicate that the procedure may perhaps be the best available one to solve the m-median problem exactly.     

A linear programming formulation for the maximum complete multipartite subgraph problem

Let G be a simple undirected graph with node set V(G) and edge set E(G). We call a subset independent if F is contained in the edge set of a complete multipartite (not necessarily induced) subgraph of G, F is dependent otherwise. In this paper we characterize the independents and the minimal dependents of G. We note that every minimal dependent of G has size two if and only if G is fan and prism-free. We give a 0-1 linear programming formulation of the following problem: find the maximum weight of a complete multipartite subgraph of G, where G has nonnegative edge weights. This formulation may have an exponential number of constraints with respect to |V(G)| but we show that the continuous relaxation of this 0-1 program can be solved in polynomial time.     

Integrating modeling,algorithm design,and computational implementation to solve a large-scale nonlinear mixed integer programming problem

This paper describes the formulation of a nonlinear mixed integer programming model for a large-scale product development and distribution problem and the design and computational implementation of a special purpose algorithm to solve the model. The results described demonstrate that integrating the art of modeling with the sciences of solution methodology and computer implementation provides a powerful approach for attacking difficult problems. The efforts described here were successful because they capitalized on the wealth of existing modeling technology and algorithm technology, the availability of efficient and reliable optimization, matrix generation and graphics software, and the speed of large-scale computer hardware. The model permitted the combined use of decomposition, general linear programming and network optimization within a branch and bound algorithm to overcome mathematical complexity. The computer system reliably found solutions with considerably better objective function values 30 to 50 times faster than had been achieved using general purpose optimization software alone. Throughout twenty months of daily use, the system was credited with providing insights and suggesting strategies that led to very large dollar savings. This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222, by the Center for Business Decision Analysis*, by the University of Texas at Austin, and by the David Bruton, Jr., Centennial Chair in Business Decision Support Systems. Reproduction in whole or in part is permitted for any purpose of the U.S. Government. Center for Business Decision Analysis, Graduate School of Business — GSB 3.126, University of Texas, Austin, Texas 78712, USA.     

Integrating modeling,algorithm design,and computational implementation to solve a large-scale non-linear mixed integer programming problem

This paper describes the formulation of a nonlinear mixed integer programming model for a large-scale product development and distribution problem and the design and computational implementation of a special purpose algorithm to solve the model. The results described demonstrate that integrating the art of modeling with the sciences of solution methodology and computer implementation provides a powerful approach for attacking difficult problems. The efforts described here were successful because they capitalized on the wealth of existing modeling technology and algorithm technology, the availability of efficient and reliable optimization, matrix generation and graphics software, and the speed of large-scale computer hardware. The model permitted the combined use of decomposition, general linear programming and network optimization within a branch and bound algorithm to overcome mathematical complexity. The computer system reliably found solutions with considerably better objective function values 30 to 50 times faster than had been achieved using general purpose optimization software alone. Throughout twenty months of daily use, the system was credited with providing insights and suggesting strategies that led to very large dollar savings.This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222, by the Center for Business Decision Analysis, by the University of Texas at Austin, and by the David Bruton, Jr., Centennial Chair in Business Decision Support Systems. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.Center for Business Decision Analysis, Graduate School of Business — GSB 3.126, University of Texas, Austin, Texas 78712, USA.     

Calculating distances for dissimilar strings: The shortest path formulation revisited

Fast detection of string differences is a prerequisite for string clustering problems. An example of such a problem is the identification of duplicate information in the data cleansing stage of the data mining process. The relevant algorithms allow the application of large-scale clustering techniques in order to create clusters of similar strings. The vast majority of comparisons, in such cases, is between very dissimilar strings, therefore methods that perform better at detecting large differences are preferable. This paper presents approaches which comply with this requirement, based on reformulation of the underlying shortest path problem. It is believed that such methods can lead to a family of new algorithms. An upper bound algorithm is presented, as an example, which produces promising results.     

A note on a symmetrical set covering problem: The lottery problem

In a lottery, n numbers are drawn from a set of m numbers. On a lottery ticket we fill out n numbers. Consider the following problem: what is the minimum number of tickets so that there is at least one ticket with at least p matching numbers? We provide a set-covering formulation for this problem and characterize its LP solution. The existence of many symmetrical alternative solutions, makes this a very difficult problem to solve, as our computational results indicate.     

The minimum Manhattan network problem: Approximations and exact solutions

Given a set of points in the plane and a constant t1, a Euclidean t-spanner is a network in which, for any pair of points, the ratio of the network distance and the Euclidean distance of the two points is at most t. Such networks have applications in transportation or communication network design and have been studied extensively.

In this paper we study 1-spanners under the Manhattan (or L₁-) metric. Such networks are called Manhattan networks. A Manhattan network for a set of points is a set of axis-parallel line segments whose union contains an x- and y-monotone path for each pair of points. It is not known whether it is NP-hard to compute minimum Manhattan networks (MMN), i.e., Manhattan networks of minimum total length. In this paper we present an approximation algorithm for this problem. Given a set P of n points, our algorithm computes in O(nlogn) time and linear space a Manhattan network for P whose length is at most 3 times the length of an MMN of P.

We also establish a mixed-integer programming formulation for the MMN problem. With its help we extensively investigate the performance of our factor-3 approximation algorithm on random point sets.     

A hybrid Outer-Approximation/Benders Decomposition algorithm for the single allocation hub location problem under congestion

An efficient procedure that concurrently generates Outer-Approximation and Benders cuts is devised to tackle the single allocation hub location problem under congestion, an MINLP. The proposed method is able to optimally solve large instances (up to 200 nodes) in reasonable time. The combination of both cuts is an algorithmic novelty.     

A generic auction algorithm for the minimum cost network flow problem

In this paper we broadly generalize the assignment auction algorithm to solve linear minimum cost network flow problems. We introduce a generic algorithm, which contains as special cases a number of known algorithms, including the -relaxation method, and the auction algorithm for assignment and for transportation problems. The generic algorithm can serve as a broadly useful framework for the development and the complexity analysis of specialized auction algorithms that exploit the structure of particular network problems. Using this framework, we develop and analyze two new algorithms, an algorithm for general minimum cost flow problems, called network auction, and an algorithm for thek node-disjoint shortest path problem.     

The vehicle routing problem with flexible time windows and traveling times

We generalize the standard vehicle routing problem by allowing soft time window and soft traveling time constraints, where both constraints are treated as cost functions. With the proposed generalization, the problem becomes very general. In our algorithm, we use local search to determine the routes of vehicles. After fixing the route of each vehicle, we must determine the optimal start times of services at visited customers. We show that this subproblem is NP-hard when cost functions are general, but can be efficiently solved with dynamic programming when traveling time cost functions are convex even if time window cost functions are non-convex. We deal with the latter situation in the developed iterated local search algorithm. Finally we report computational results on benchmark instances, and confirm the benefits of the proposed generalization.     

Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints

When vehicle routing problems with additional constraints, such as capacity or time windows, are solved via column generation and branch-and-price, it is common that the pricing subproblem requires the computation of a minimum cost constrained path on a graph with costs on the arcs and prizes on the vertices. A common solution technique for this problem is dynamic programming. In this paper we illustrate how the basic dynamic programming algorithm can be improved by bounded bi-directional search and we experimentally evaluate the effectiveness of the enhancement proposed. We consider as benchmark problems the elementary shortest path problems arising as pricing subproblems in branch-and-price algorithms for the capacitated vehicle routing problem, the vehicle routing problem with distribution and collection and the capacitated vehicle routing problem with time windows.