Search

In this paper, we study the quadratic assignment problem with a rank-one cost matrix (QAP-R1). Four integer-programming formulations are introduced of which three are assumed to have partial integer data. Unlike the standard quadratic assignment problem, some of our formulations can solve reasonably large instances of QAP-R1 with impressive running times and are faster than some metaheuristics. Pairwise relative strength of the LP relaxations of these formulations are also analyzed from theoretical and experimental points of view. Finally, we present a new metaheuristic algorithm to solve QAP-R1 along with its computational analysis. Our study offers the first systematic experimental analysis of integer-programming models and heuristics for QAP-R1. The benchmark instances with various characteristics generated for our study are made available to the public for future research work. Some new polynomially solvable special cases are also introduced. Summary of Contribution: This paper aims to advance our knowledge and ability in solving an important special case of the quadratic assignment problem. It shows how to exploit inherent properties of an optimization problem to achieve computational advantages, a strategy that was followed by researchers in model building and algorithm developments for decades. Our computational results attest to this time-tested general philosophy. The paper presents the first systematic computational study of the rank one quadratic assignment problem, along with new mathematical programming models and complexity analysis. We believe the theoretical and computational results of this paper will inspire further research on the topic and will be of significant value to practitioners using rank one quadratic assignment models. [ABSTRACT FROM AUTHOR]

This paper presents an efficient algorithm for an integrated operating room planning and scheduling problem. It combines the assignment of surgeries to operating rooms and scheduling over a short-term planning horizon. This integration results in more stable planning through consideration of the operational details at the scheduling level, and this increases the chance of successful implementation. We take into account the maximum daily working hours of surgeons, prevent the overlapping of surgeries performed by the same surgeon, allow time for the obligatory cleaning when switching from infectious to noninfectious cases, and respect the surgery deadlines. We formulate the problem using a mathematical programming model and develop a branch-and-price-and-cut algorithm based on a constraint programming model for the subproblem. We also develop dominance rules and a fast infeasibility-detection algorithm based on a multidimensional knapsack problem to improve the efficiency of the constraint programming model. The computational results show that our method has an average optimality gap of 2.81% and significantly outperforms a compact mathematical formulation in the literature. [ABSTRACT FROM AUTHOR]

We present a new computational approach to the problem of placing n identical nonoverlapping disks in the unit square in such a way that their radii are maximized. The problem has been studied in a large number of papers, from both a theoretical and a computational point of view. In this paper, we conjecture that the problem possesses a so-called funneling landscape, a feature that is commonly found in molecular conformation problems. Based on this conjecture, we develop a stochastic search algorithm that displays excellent numerical performance. Thanks to this algorithm, we could improve over previously known putative optima in the range n ≤ 130 in as many as 32 instances, the smallest of which is n=53. [ABSTRACT FROM AUTHOR]

This paper presents the spiral array model and its associated algorithms for tonal induction, approximation, and segmentation. The spiral array is a geometric model for tonality that clusters perceptually similar tonal entities. The model summarizes music information as interior points inside an array of spirals. Distances in the spiral array space are used to quantify tonal similarity. The paper traces the evolution, and presents general forms, of the existing algorithms for key finding, pitch spelling, and segmentation, and proposes a new O(n) algorithm, Argus, for tonal segmentation. The proposed algorithm computes a value that quantifies the discrepancy between the local contexts in the future and past at each point in time. Discrepancy values exceeding control thresholds are shown to mark the segmentation boundaries of the test set that concur with expert analyses. A number of window sizes and threshold settings are investigated. The algorithm is demonstrated using Edward MacDowell's To A Wild Rose and tested on Franz Schubert's Allegretto from Moment Musical D780 No. 6 and Thema from Impromptu D935 No. 4. The algorithm accurately locates tonal boundaries in all three case studies. [ABSTRACT FROM AUTHOR]

In recent years, many algorithms have been proposed to extract process models from process execution logs. The process models describe the ordering relationships between tasks in a process in terms of standard constructs like sequence, parallel, choice, and loop. Most algorithms assume that each trace in a log represents a correct execution sequence based on a model. In practice, logs are often noisy, and algorithms designed for correct logs are not able to handle noisy logs. In this paper we share our key insights from a study of noise in process logs both real and synthetic. We found that all process logs can be explained by a block-structured model with two special self-loop and optional structures, making it trivial to build a fully accurate process model for any given log, even one with inaccurate data or noise present in it. However, such a model suffers from low quality. By controlling the use of self-loop and optional structures of tasks and blocks of tasks, we can balance the quality and accuracy trade-off to derive high-quality process models that explain a given percentage of traces in the log. Finally, new quality metrics and a novel quality-based algorithm for model extraction from noisy logs are described. The results of the experiments with the algorithm on real and synthetic data are reported and analyzed at length. [ABSTRACT FROM AUTHOR]

The many-to-many stable matching problem (MM), defined in the context of a job market, asks for an assignment of workers to firms satisfying the quota of each agent and being stable, pairwise or setwise, with respect to given preference lists or relations. In this paper, we propose a time-optimal algorithm that identifies all stable worker-firm pairs and all stable assignments under pairwise stability, individual preferences, and the max-min criterion. We revisit the poset graph of rotations to obtain an optimal algorithm for enumerating all solutions to the MM and an improved algorithm finding the minimum-weight one. Furthermore, we establish the applicability of all aforementioned algorithms under more complex preference and stability criteria. In a constraint programming context, we introduce a constraint that models the MM and an encoding of the MM as a constraint satisfaction problem. Finally, we provide a series of computational results, including the case where side constraints are imposed. [ABSTRACT FROM AUTHOR]

Route planning in large-scale time-dependent road networks is an important practical application of the shortest-path problem that greatly benefits from speedup techniques. In this paper, we extend a two-level hierarchical approach for point-to-point shortest-path computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, consists of the selection of a small subnetwork where most of the computations can be carried out, thus reducing the search space. We combine this approach with bidirectional goal-directed search to obtain an algorithm capable of finding shortest paths in a matter of milliseconds on continental-sized networks. Moreover, we tackle the dynamic scenario where the piecewise linear functions that we use to model time-dependent arc costs are not fixed but can have their coefficients updated requiring only a small computational effort. [ABSTRACT FROM AUTHOR]

Despite the fact that no polynomial-time algorithm is known for solving mixed-integer programming (MIP) problems, there has been remarkable success in recent years in solving a wide range of difficult MIPs. In this paper, we take a look at some of the hardest problems in the MIPLIB 2003 test set and show how Xpress-MP can be used to solve some of the problems that were previously thought to be intractable. [ABSTRACT FROM AUTHOR]

In this paper, we develop a unified framework for approximating open and closed queueing networks under any general blocking protocol by extending and generalizing the approximation algorithm for open tandem queues under minimal blocking presented in Di Mascolo et al. (1996). The proposed framework is based on decomposition. We develop decomposition structures and analysis algorithms for any general blocking system using the framework. The proposed algorithms have been extensively tested using simulations as a benchmarking device. The results show that the proposed framework yields robust, reliable, and accurate estimates of system characteristics, such as throughput and Work-In-Process inventory in a wide range of system configurations. The computational load is minimal. The unified framework presents a highly useful set of tools of analysis for queueing-system designers to use in evaluating the performance under numerous design alternatives. Directions for future research are presented, with a focus on critical application areas such as packet-switching-network design and cellular manufacturing. [ABSTRACT FROM AUTHOR]

Placement of inspection stations is a common task in transportation and communication networks. In this paper, two categories of problems involving placement of inspection stations are studied. The first category deals with the selection of inspection stations along a given path from an origin to a destination. The second considers simultaneous selection of both a path and inspection stations along that path. We formulate these problems under a variety of minimization objectives such as the maximum gap between two consecutive inspection stations, the expected penalty cost of failure along the path, and the total inspection cost. Our results include efficient algorithms for many formulations and complexity results as well as fully polynomial approximation schemes for other formulations. When considering cost objectives, we identify a core problem and show that the complexity of many formulations is directly related to the complexity of the core problem. [ABSTRACT FROM AUTHOR]

We consider the 1-median problem on a network with uncertain weights of nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find the "minimax regret" location, i.e., to minimize the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. We present the first polynomial algorithm for this problem on a general network. For the problem on a tree network, we discuss an algorithm with an order of complexity improved over the algorithms known in the literature. [ABSTRACT FROM AUTHOR]

We examine the optimal location of Integrated Air Defense System (IADS) missile batteries to protect a country's assets, formulated as a Defender-Attacker-Defender three-stage sequential, perfect information, zero-sum game between two opponents. We formulate a trilevel nonlinear integer program for this Defender-Attacker-Defender model and seek a subgame perfect Nash equilibrium (i.e., a set of attacker and defender strategies from which neither player has an incentive to deviate). Such a trilevel formulation is not solvable via conventional optimization software, and an exhaustive enumeration of the game tree based on the discrete set of strategies is only tractable for small instances. We develop and test a customized heuristic over a set of small instances having deliberate parametric variations in a designed experiment, comparing its performance to an exhaustive enumeration algorithm. Testing results indicate the enumeration approach to be severely limited for realistically sized instances, so we demonstrate the heuristic on a larger instance from the literature for which it maintains computational efficiency. [ABSTRACT FROM AUTHOR]

We present a branch-and-price algorithm to solve personalized multi-activity shift scheduling problems. The subproblems in the column generation method are formulated using grammars and solved with dynamic programming. The expressiveness of context-free grammars is exploited to easily model restrictions over shifts, allowing the branch-and-price algorithm to solve large-scale problem instances. We present computational experiments on two types of multi-activity shift scheduling problems and compare our approach with existing methods in the literature. These experiments show that our approach can efficiently solve large-scale instances and is flexible enough to model different classes of problems. [ABSTRACT FROM AUTHOR]

We study the problem of (re)designing the regional network by which cadaveric livers are allocated. Whereas W prior research focused mainly on maximizing a measure of efficiency of the network that was based on aggregate patient survival, we explicitly account for the trade-off between efficiency and a measure of geographical equity in the allocation process. To this end, we extend earlier optimization models to incorporate both objectives and develop an exact branch-and-price approach to solve this problem, generalizing a solution approach studied for the case where only efficiency is taken into account. In addition, we propose an effective solution algorithm that approximates the (generally nonconcave) frontier of Pareto-efficient solutions with respect to the two objectives by simultaneously generating and successively improving upper and lower bounds on this frontier. We implement and test our approach on observed data and show that solutions significantly dominating the current configuration in both efficiency and equity can be found. Of course, other subjective criteria are needed to choose among the different Pareto-efficient candidate solutions. [ABSTRACT FROM AUTHOR]

We consider a network where nodes communicate by exchanging information packets whose fields include the address of the sending node and that of the destination node. In the absence of some verification mechanism, an attacking node can send packets to another node using a forged origin address. In this study, we consider an optimization problem of identifying a minimum cardinality subset of verification nodes on a tree such that the number of attacks from any forged origin to any destination is limited to a prescribed level. For the case in which communication is permitted between every node in the tree, we develop an optimal polynomial-time dynamic programming algorithm for this problem. We compare the performance of the dynamic programming algorithm against a mixed-integer programming model on randomly generated tree networks at varied levels of security. [ABSTRACT FROM AUTHOR]

We consider the problem of determining a set of optimal tariffs for an agent in the network, who owns a subset of all the arcs, and who receives revenue by setting the tariffs on the arcs he owns. Multiple rational clients are active in the network, who route their demands on the least expensive paths from source to destination. The cost of a path is determined by fixed costs and tariffs on the arcs of the path. We introduce a remodeling of the network, using shortest paths. We develop three algorithms based on this shortest-path graph model: a combinatorial branch-and-bound algorithm, a path-oriented mixed integer program, and a known-arc-oriented mixed integer program. Combined with reduction methods, this remodeling enables us to solve the problem to optimality, for quite large instances. We provide computational results for the methods developed and compare them with the results of the arc-oriented mixed integer programming formulation of the problem, applied to the original network. [ABSTRACT FROM AUTHOR]

We consider both branch-and-cut and column-generation approaches for the problem of finding a minimum-cost assignment of jobs with release dates and deadlines to unrelated parallel machines. Results are presented for several variants both with and without constraint programming. Among the variants, the most effective strategy is to combine a tight and compact, but approximate, mixed integer programming (MIP) formulation with a global constraint testing single machine feasibility. Instances with up to nine machines and 54 jobs have been solved. All the algorithms have been implemented in the Mosel modeling and optimization language. [ABSTRACT FROM AUTHOR]