Minmax earliness–tardiness costs with unit processing time jobs

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.     

Safe scheduling: Setting due dates in single-machine problems

We consider single-machine stochastic scheduling models with due dates as decisions. In addition to showing how to satisfy given service-level requirements, we examine variations of a model in which the tightness of due-dates conflicts with the desire to minimize tardiness. We show that a general form of the trade-off includes the stochastic E/T model and gives rise to a challenging scheduling problem. We present heuristic solution methods based on static and dynamic sorting procedures. Our computational evidence identifies a static heuristic that routinely produces good solutions and a dynamic rule that is nearly always optimal. The dynamic sorting procedure is also asymptotically optimal, meaning that it can be recommended for problems of any size.     

An optimal stocking problem to minimize the expected time to sellout

We consider an assortment planning problem where the objective is to minimize the expected time to sell all items in the assortment. We provide several structural results for the optimal assortment. We present a heuristic policy, which we prove is asymptotically optimal. We also show that there are alternate objective criteria under which the problem simplifies considerably.     

Scheduling on same-speed processors with at most one downtime on each machine

We consider the problem of scheduling a set of independent tasks on multiple same-speed processors with planned shutdown times with the aim of minimizing the makespan. We give an LPT-based algorithm, LPTX, which yields a maximum completion time that is less than or equal to 3/2 the optimal maximum completion time or 3/2 the time that passes from the start of the schedule until the latest end of a downtime. For problems where the optimal schedule ends after the last downtime, and when the downtimes represent fixed jobs, the LPTX maximum completion time is within 3/2 of the optimal maximum completion time. In addition, we show that this result is asymptotically tight for the class of polynomial algorithms assuming that P≠NP. We also show that the bound obtained previously for a similar problem, when no more than half of the machines are shut down at the same time, for the LPT algorithm is asymptotically tight in the class of polynomial algorithms if P≠NP.     

A heuristic algorithm for the symmetric and asymmetric vehicle routing problems with backhauls

We consider an extension of the capacitated Vehicle Routing Problem (VRP), known as the Vehicle Routing Problem with Backhauls (VRPB), in which the set of customers is partitioned into two subsets: Linehaul and Backhaul customers. Each Linehaul customer requires the delivery of a given quantity of product from the depot, whereas a given quantity of product must be picked up from each Backhaul customer and transported to the depot. VRPB is known to be NP-hard in the strong sense, and many heuristic algorithms were proposed for the approximate solution of the problem with symmetric or Euclidean cost matrices. We present a cluster-first-route-second heuristic which uses a new clustering method and may also be used to solve problems with asymmetric cost matrix. The approach exploits the information of the normally infeasible VRPB solutions associated with a lower bound. The bound used is a Lagrangian relaxation previously proposed by the authors. The final set of feasible routes is built through a modified Traveling Salesman Problem (TSP) heuristic, and inter-route and intra-route arc exchanges. Extensive computational tests on symmetric and asymmetric instances from the literature show the effectiveness of the proposed approach.     

Solving the post enrolment course timetabling problem by ant colony optimization

In this work we present a new approach to tackle the problem of Post Enrolment Course Timetabling as specified for the International Timetabling Competition 2007 (ITC2007), competition track 2. The heuristic procedure is based on Ant Colony Optimization (ACO) where artificial ants successively construct solutions based on pheromones (stigmergy) and local information. The key feature of our algorithm is the use of two distinct but simplified pheromone matrices in order to improve convergence but still provide enough flexibility for effectively guiding the solution construction process. We show that by parallelizing the algorithm we can improve the solution quality significantly. We applied our algorithm to the instances used for the ITC2007. The results document that our approach is among the leading algorithms for this problem; in all cases the optimal solution could be found. Furthermore we discuss the characteristics of the instances where the algorithm performs especially well.     

On estimating the distribution of optimal traveling salesman tour lengths using heuristics

The traveling salesman problem is an important combinatorial optimization problem due to its significance in academic research and its real world applications. The problem has been extensively studied and much is known about its polyhedral structure and algorithms for exact and heuristic solutions. While most work is concentrated on solving the deterministic version of the problem, there also has been some research on the stochastic TSP. Research on the stochastic TSP has concentrated on asymptotic properties and estimation of the TSP-constant. Not much is, however, known about the probability distribution of the optimal tour length. In this paper, we present some empirical results based on Monte Carlo simulations for the symmetric Euclidean and Rectilinear TSPs. We derive regression equations for predicting the first four moments of the distribution of estimated TSP tour lengths using heuristics. We then show that a Beta distribution gives excellent fits for small to moderate sized TSP problems. We derive regression equations for predicting the parameters of the Beta distribution. Finally we predict the TSP constant using two alternative approaches.     

On the random 2‐stage minimum spanning tree

It is known [A. M. Frieze, Discrete Appl Math 10 (1985), 47–56] that if the edge costs of the complete graph K_n are independent random variables, uniformly distributed between 0 and 1, then the expected cost of the minimum spanning tree is asymptotically equal to . Here we consider the following stochastic two‐stage version of this optimization problem. There are two sets of edge costs c_M: E → ? and c_T: E → ?, called Monday's prices and Tuesday's prices, respectively. For each edge e, both costs c_M(e) and c_T(e) are independent random variables, uniformly distributed in [0, 1]. The Monday costs are revealed first. The algorithm has to decide on Monday for each edge e whether to buy it at Monday's price c_M(e), or to wait until its Tuesday price c_T(e) appears. The set of edges X_M bought on Monday is then completed by the set of edges X_T bought on Tuesday to form a spanning tree. If both Monday's and Tuesday's prices were revealed simultaneously, then the optimal solution would have expected cost ζ(3)/2 + o(1). We show that, in the case of two‐stage optimization, the expected value of the optimal cost exceeds ζ(3)/2 by an absolute constant ε > 0. We also consider a threshold heuristic, where the algorithm buys on Monday only edges of cost less than α and completes them on Tuesday in an optimal way, and show that the optimal choice for α is α = 1/n with the expected cost ζ(3) ? 1/2 + o(1). The threshold heuristic is shown to be sub‐optimal. Finally we discuss the directed version of the problem, where the task is to construct a spanning out‐arborescence rooted at a fixed vertex r, and show, somewhat surprisingly, that in this case a simple variant of the threshold heuristic gives the asymptotically optimal value 1 ? 1/e + o(1). © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On the complexity of computing the handicap of a sufficient matrix

The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of P{\mathcal{P}} -matrices (where all principal minors are positive).     

A heuristic for decomposing traffic matrices in TDMA satellite communication

A heuristic for decomposing traffic matrices in TDMA satellite communication. With the time-division multiple access (TDMA) technique in satellite communication the problem arises to decompose a givenn×n traffic matrix into a weighted sum of a small number of permutation matrices such that the sum of the weights becomes minimal. There are polynomial algorithms when the number of permutation matrices in a decomposition is allowed to be as large asn ². When the number of matrices is restricted ton, the problem is NP-hard. In this paper we propose a heuristic based on a scaling technique which for each number of allowed matrices in the range fromn ton ² allows to give a performance guarantee with respect to the total weight of the solution. As a subroutine we use new heuristic methods for decomposing a matrix of small integers into as few matrices as possible without exceeding the lower bound on the total weight. Computational results indicate that the method might also be practical.This work was supported by the Fonds zur Förderung der wissenschaftlichen Forschung, Project S32/01.     

Experimental analysis of heuristics for the bottleneck traveling salesman problem

In this paper we develop efficient heuristic algorithms to solve the bottleneck traveling salesman problem (BTSP). Results of extensive computational experiments are reported. Our heuristics produced optimal solutions for all the test problems considered from TSPLIB, JM-instances, National TSP instances, and VLSI TSP instances in very reasonable running time. We also conducted experiments with specially constructed ‘hard’ instances of the BTSP that produced optimal solutions for all but seven problems. Some fast construction heuristics are also discussed. Our algorithms could easily be modified to solve related problems such as the maximum scatter TSP and testing hamiltonicity of a graph.     

Self-clique graphs and matrix permutations

The clique graph of a graph is the intersection graph of its (maximal) cliques. A graph is self-clique when it is isomorphic with its clique graph, and is clique-Helly when its cliques satisfy the Helly property. We prove that a graph is clique-Helly and self-clique if and only if it admits a quasi-symmetric clique matrix, that is, a clique matrix whose families of row and column vectors are identical. We also give a characterization of such graphs in terms of vertex-clique duality. We describe new classes of self-clique and 2-self-clique graphs. Further, we consider some problems on permuted matrices (matrices obtained by permuting the rows and/or columns of a given matrix). We prove that deciding whether a (0,1)-matrix admits a symmetric (quasi-symmetric) permuted matrix is graph (hypergraph) isomorphism complete. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 178–192, 2003     

Monge properties,discrete convexity and applications

Starting from Monge’s mass transportation problem we review the role Monge properties play in optimization. In particular we discuss transportation problems whose cost functions fulfill a Monge property, Monge sequences, algebraic Monge properties, the recognition of permuted Monge arrays and multidimensional Monge arrays and the connections between Monge properties and discrete convexity. Finally we discuss Prékopa’s recent approach using Monge arrays in bounding multivariate probability distribution functions.     

An Order-theoretic Framework for the Greedy Algorithm with Applications to the Core and Weber Set of Cooperative Games

An algebraic model generalizing submodular polytopes is presented, where modular functions on partially ordered sets take over the role of vectors in R ⁿ . This model unifies various generalizations of combinatorial models in which the greedy algorithm and the Monge algorithm are successful and generalizations of the notions of core and Weber set in cooperative game theory.As a further application, we show that an earlier model of ours as well as the algorithmic model of Queyranne, Spieksma and Tardella for the Monge algorithm can be treated within the framework of usual matroid theory (on unordered ground-sets), which permits also the efficient algorithmic solution of the intersection problem within this model.     

Algorithms for the universal and a priori TSP

We present two simple results for generalizations of the traveling salesman problem (TSP): for the universal TSP, we show that one can compute a tour that is universally optimal whenever the input is a tree metric. A (randomized) O(logn)-approximation algorithm for the a priori TSP follows as a corollary.     

On the n-Coupling Problem

In this paper we obtain based on an idea of M. Knott and C. S. Smith (1994, Linear Algebra Appl.199, 363–371) characterizations of solutions of three-coupling problems by reduction to the construction of optimal couplings of each of the variables to the sum. In the case of normal distributions this leads to a complete solution. Under a technical condition this idea also works for general distributions and one obtains explicit results. We extend these results to the n-coupling problem and derive a characterization of optimal n-couplings by several 2-coupling problems. This leads to some constructive existence results for Monge solutions.     

Convergence of a fourth-order singular perturbation of the n-dimensional radially symmetric Monge–Ampère equation

This paper concerns with the convergence analysis of a fourth-order singular perturbation of the Dirichlet Monge–Ampère problem in the n-dimensional radial symmetric case. A detailed study of the fourth- order problem is presented. In particular, various a priori estimates with explicit dependence on the perturbation parameter ε are derived, and a crucial convexity property is also proved for the solution of the fourth-order problem. Using these estimates and the convexity property, we prove that the solution of the perturbed problem converges uniformly and compactly to the unique convex viscosity solution of the Dirichlet Monge–Ampère problem. Rates of convergence in the H^k-norm for k = 0, 1, 2 are also established.     

Partial Regularity for Singular Solutions to the Monge‐Ampère Equation

We prove that solutions to the Monge‐Ampère inequality in ?ⁿ are strictly convex away from a singular set of Hausdorff (n‐1)‐dimensional measure zero. Furthermore, we show this is optimal by constructing solutions to det D²u = 1 with singular set of Hausdorff dimension as close as we like to n‐1. As a consequence we obtain W^2,1 regularity for the Monge‐Ampère equation with bounded right‐hand side and unique continuation for the Monge‐Ampère equation with sufficiently regular right‐hand side. © 2015 Wiley Periodicals, Inc.     

From the Schrödinger problem to the Monge–Kantorovich problem

The aim of this article is to show that the Monge–Kantorovich problem is the limit, when a fluctuation parameter tends down to zero, of a sequence of entropy minimization problems, the so-called Schrödinger problems. We prove the convergence of the entropic optimal values to the optimal transport cost as the fluctuations decrease to zero, and we also show that the cluster points of the entropic minimizers are optimal transport plans. We investigate the dynamic versions of these problems by considering random paths and describe the connections between the dynamic and static problems. The proofs are essentially based on convex and functional analysis. We also need specific properties of Γ-convergence which we didn?t find in the literature; these Γ-convergence results which are interesting in their own right are also proved.     

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n^{2 + max(α, β)}) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(n^max(α, β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a “Monge property” and that the SMAWK algorithm on monotone matrices can therefore be applied.