The Delivery Man Problem with time windows

In this paper, a variant of the Traveling Salesman Problem with Time Windows is considered, which consists in minimizing the sum of travel durations between a depot and several customer locations. Two mixed integer linear programming formulations are presented for this problem: a classical arc flow model and a sequential assignment model. Several polyhedral results are provided for the second formulation, in the special case arising when there is a closed time window only at the depot, while open time windows are considered at all other locations. Exact and heuristic algorithms are also proposed for the problem. Computational results show that medium size instances can be solved exactly with both models, while the heuristic provides good quality solutions for medium to large size instances.     

An improved assignment lower bound for the euclidean traveling salesman problem

A simple transformation of the distance matrix for the Euclidean traveling salesman problem is presented that produces a tighter lower bound on the length of the optimal tour than has previously been attainable using the assignment relaxation. The improved lower bound is obtained by exploiting geometric properties of the problem to produce fewer and larger subtours on the first solution of the assignment problem. This research should improve the performance of assignment based exact procedures and may lead to improved heuristics for the traveling salesman problem.     

Reoptimization of minimum and maximum traveling salesman's tours

In this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.     

A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p

We introduce a new method of constructing approximation algorithms for combinatorial optimization problems using semidefinite programming. It consists of expressing each combinatorial object in the original problem as a constellation of vectors in the semidefinite program. When we apply this technique to systems of linear equations mod p with at most two variables in each equation, we can show that the problem is approximable within (1 − κ(p))p, where κ(p) > 0 for all p. Using standard techniques, we also show that it is NP-hard to approximate the problem within a constant ratio, independent of p.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

New lower bounds on the size of (n,r)‐arcs in PG(2,q)

An $\left(n,r\right)$‐arc in $\text{PG}\left(2,q\right)$ is a set of $n$ points such that each line contains at most $r$ of the selected points. It is well known that $\left(n,r\right)$‐arcs in $\text{PG}\left(2,q\right)$ correspond to projective linear codes. Let $m_r\left(2,q\right)$ denote the maximal number $n$ of points for which an $\left(n,r\right)$‐arc in $\text{PG}\left(2,q\right)$ exists. In this paper we obtain improved lower bounds on $m_r\left(2,q\right)$ by explicitly constructing $\left(n,r\right)$‐arcs. Some of the constructed $\left(n,r\right)$‐arcs correspond to linear codes meeting the Griesmer bound. All results are obtained by integer linear programming.     

Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming

We study lower bounding methods for indefinite integer quadratic programming problems. We first construct convex relaxations by D.C. (difference of convex functions) decomposition and linear underestimation. Lagrangian bounds are then derived by applying dual decomposition schemes to separable relaxations. Relationships between the convex relaxation and Lagrangian dual are established. Finally, we prove that the lower bound provided by the convex relaxation coincides with the Lagrangian bound of the orthogonally transformed problem.     

On the computation of all supported efficient solutions in multi-objective integer network flow problems

This paper presents a new algorithm for identifying all supported non-dominated vectors (or outcomes) in the objective space, as well as the corresponding efficient solutions in the decision space, for multi-objective integer network flow problems. Identifying the set of supported non-dominated vectors is of the utmost importance for obtaining a first approximation of the whole set of non-dominated vectors. This approximation is crucial, for example, in two-phase methods that first compute the supported non-dominated vectors and then the unsupported non-dominated ones. Our approach is based on a negative-cycle algorithm used in single objective minimum cost flow problems, applied to a sequence of parametric problems. The proposed approach uses the connectedness property of the set of supported non-dominated vectors/efficient solutions to find all integer solutions in maximal non-dominated/efficient facets.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

Models and algorithms for a staff scheduling problem

We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months. Mathematics Subject Classification (2000): 90B70, 90C10, 90C27, 90C39, 90C57, 90C59     

Layering strategies for creating exploitable structure in linear and integer programs

The strategy of subdividing optimization problems into layers by splitting variables into multiple copies has proved useful as a method for inducing exploitable structure in a variety of applications, particularly those involving embedded pure and generalized networks. A framework is proposed in this paper which leads to new relaxation and restriction methods for linear and integer programming based on our extension of this strategy. This framework underscores the use of constructions that lead to stronger relaxations and more flexible strategies than previous applications. Our results establish the equivalence of all layered Lagrangeans formed by parameterizing the equal value requirement of copied variables for different choices of the principal layers. It is further shown that these Lagrangeans dominate traditional Lagrangeans based on incorporating non-principal layers into the objective function. In addition a means for exploiting the layered Lagrangeans is provided by generating subgradients based on a simple averaging calculation. Finally, we show how this new layering strategy can be augmented by an integrated relaxation/restriction procedure, and indicate variations that can be employed to particular advantage in a parallel processing environment. Preliminary computational results on fifteen real world zero-one personnel assignment problems, comparing two layering approaches with five procedures previously found best for those problems, are encouraging. One of the layering strategies tested dominated all non-layering procedures in terms of both quality and solution time.This research was supported in part by the Office of Naval Research Contract N00014-78-C-0222 with the Center for Business Decision Analysis and by the US Department of Agriculture Contract 51-3142-4020 with Management Science Software Systems.     

Hybrid flexible flowshop problems: Models and solution methods

This paper considers the problem of hybrid flowshop scheduling. First, we review the shortcoming of the available model in the literature. Then, four different mathematical models are developed in form of mixed integer linear programming models. A complete experiment is conducted to compare the models for performance based on the size and computational complexities. Besides the models, the paper proposes a novel hybrid particle swarm optimization algorithm equipped with an acceptance criterion and a local search heuristic. The features provide a fine balance of diversification and intensification capabilities for the algorithm. Using Taguchi method, the algorithm is fine tuned. Then, two numerical experiments are performed to evaluate the performance of the proposed algorithm with three particle swarm optimization algorithms available in the scheduling literature and one well-known iterated local search algorithm in the hybrid flowshop literature. All the results show the high performance of the proposed algorithm.     

Duality in mathematics and linear and integer programming

Linear programming (LP) duality is examined in the context of other dualities in mathematics. The mathematical and economic properties of LP duality are discussed and its uses are considered. These mathematical and economic properties are then examined in relation to possible integer programming (IP) dualities. A number of possible IP duals are considered in this light and shown to capture some but not all desirable properties. It is shown that inherent in IP models are inequality and congruence constraints, both of which give on their own well-defined duals. However, taken together, no totally satisfactory dual emerges. The superadditive dual based on the Gomory and Chvátal functions is then described, and its properties are contrasted with LP duals and other IP duals. Finally, possible practical uses of IP duals are considered.The author is indebted to Professor H. B. Griffiths for many stimulating conversations on this topic.     

Detecting Embedded Networks in LP Using GUB Structures and Independent Set Algorithms

In this paper, we present an alternative multi-stage generalized upper bounds (GUB) based approach for detecting an embedded pure network structure in an LP problem. In order to identify a GUB structure, we use two different approaches; the first is based on the notion of Markowitz merit count and the second exploits independent sets in the corresponding graphs. Our computational experiments show that the multi-stage GUB algorithm based on these approaches performs favourably when compared with other well known algorithms.     

2-InterConnected Facility Location: Specification,Complexity, and Exact Solutions

Connected facility location combines cost-efficient facility placement and the requirement to connect the facilities among each other. Such problems arise, e.g., in telecommunication applications where networks consist of a central core and local clients connected to it. Reliability of the core is a central issue, and we may hence require the core to be at least 2-connected.We establish the problem class of 2-interConnected Facility Location (2-iCFL), categorize its central variants, and prove that they are hard to approximate. However, our computational results show that our orientation-based ILPs allow us to effectively solve such problems to optimality for hundreds of nodes. We also establish constructive characterizations for feasible problem instances, to be used for algorithmic feasibility checks, preprocessing, and heuristics.     

Multi-Item, Multi-Facility Supply Chain Planning: Models, Complexities, and Algorithms

We propose a planning model for products manufactured across multiple manufacturing facilities sharing similar production capabilities. The need for cross-facility capacity management is most evident in high-tech industries that have capital-intensive equipment and a short technology life cycle. We propose a multicommodity flow network model where each commodity represents a product and the network structure represents manufacturing facilities in the supply chain capable of producing the products. We analyze in depth the product-level (single-commodity, multi-facility) subproblem when the capacity constraints are relaxed. We prove that even the general-cost version of this uncapacitated subproblem is NP-complete. We show that there exists an optimization algorithm that is polynomial in the number of facilities, but exponential in the number of periods. We further show that under special cost structures the shortest-path algorithm could achieve optimality. We analyze cases when the optimal solution does not correspond to a source-to-sink path, thus the shortest path algorithm would fail. To solve the overall (multicommodity) planning problem we develop a Lagrangean decomposition scheme, which separates the planning decisions into a resource subproblem, and a number of product-level subproblems. The Lagrangean multipliers are updated iteratively using a subgradient search algorithm. Through extensive computational testing, we show that the shortest path algorithm serves as an effective heuristic for the product-level subproblem (a mixed integer program), yielding high quality solutions with only a fraction (roughly 2%) of the computer time.     

On the Interplay among Entropy, Variable Metrics and Potential Functions in Interior-Point Algorithms

We are motivated by the problem of constructing aprimal-dual barrier function whose Hessian induces the (theoreticallyand practically) popular symmetric primal and dual scalings forlinear programming problems. Although this goal is impossible toattain, we show that the primal-dual entropy function may provide asatisfactory alternative. We study primal-dual interior-pointalgorithms whose search directions are obtained from a potentialfunction based on this primal-dual entropy barrier. We providepolynomial iteration bounds for these interior-point algorithms. Thenwe illustrate the connections between the barrier function and areparametrization of the central path equations. Finally, we considerthe possible effects of more general reparametrizations oninfeasible-interior-point algorithms.     

Reliability in the acquisitions process: Douglas J. DePRIEST and Robert L. LAUNER (eds.) Volume 4 in: Lecture Notes in Statistics,Marcel Dekker,New York, 1983, viii + 199 pages

We correct a mistake in the Martello-Toth algorithm for the general one-dimensional knapsack problem.     

Frequency optimization in public transportation systems: Formulation and metaheuristic approach

We study the transit frequency optimization problem, which aims to determine the time interval between subsequent buses for a set of public transportation lines given by their itineraries, i.e., sequences of stops and street sections. The solution should satisfy a given origin–destination demand and a constraint on the available fleet of buses. We propose a new mixed integer linear programming (MILP) formulation for an already existing model, originally formulated as a nonlinear bilevel one. The proposed formulation is able to solve to optimality real small-sized instances of the problem using MILP techniques. For solving larger instances we propose a metaheuristic which accuracy is estimated by comparing against exact results (when possible). Both exact and approximated approaches are tested by using existing cases, including a real one related to a small-city which public transportation system comprises 13 lines. The magnitude of the improvement of that system obtained by applying the proposed methodologies, is comparable with the improvements reported in the literature, related to other real systems. Also, we investigate the applicability of the metaheuristic to a larger-sized real case, comprising more than 130 lines.     

Performance safety enforcement in stochastic event graphs against boost and slow attacks

This paper studies a performance safety enforcing problem in stochastic event graphs, a subclass of stochastic Petri net models. We assume that an intruder can attack part of the transitions to increase/decrease their firing rate such that the performance of the system violates a given safety interval. The difficulty in solving this problem is that the capability of the intruder, i.e., the number of transitions that can be simultaneously attacked, is limited. The control aim is to find a protecting policy such that the performance of the protected plant is guaranteed to be in a given safety interval. We show that this problem can be formulated as a two-player game between the intruder and the operator of the plant. By using mixed integer linear programming technique, we develop a heuristic method to compute a protecting policy that is locally optimal.