Multigraph realizations of degree sequences: Maximization is easy, minimization is hard

The following minimization problem is shown to be NP-hard: Given a graphic degree sequence, find a realization of this degree sequence as loopless multigraph that minimizes the number of edges in the underlying support graph. The corresponding maximization problem is known to be solvable in polynomial time.     

Solving the maximum edge weight clique problem via unconstrained quadratic programming

The unconstrained quadratic binary program (UQP) is proving to be a successful modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing more traditional methods. In this paper we report on the application of UQP to the maximum edge-weighted clique problem. Computational experience is reported illustrating the attractiveness of the approach.     

The external constraint 4 nonempty part sandwich problem

List partitions generalize list colourings. Sandwich problems generalize recognition problems. The polynomial dichotomy (NP-complete versus polynomial) of list partition problems is solved for 4-dimensional partitions with the exception of one problem (the list stubborn problem) for which the complexity is known to be quasipolynomial. Every partition problem for 4 nonempty parts and only external constraints is known to be polynomial with the exception of one problem (the 2K₂-partition problem) for which the complexity of the corresponding list problem is known to be NP-complete. The present paper considers external constraint 4 nonempty part sandwich problems. We extend the tools developed for polynomial solutions of recognition problems obtaining polynomial solutions for most corresponding sandwich versions. We extend the tools developed for NP-complete reductions of sandwich partition problems obtaining the classification into NP-complete for some external constraint 4 nonempty part sandwich problems. On the other hand and additionally, we propose a general strategy for defining polynomial reductions from the 2K₂-partition problem to several external constraint 4 nonempty part sandwich problems, defining a class of 2K₂-hard problems. Finally, we discuss the complexity of the Skew Partition Sandwich Problem.     

A survey for the quadratic assignment problem

The quadratic assignment problem (QAP), one of the most difficult problems in the NP-hard class, models many real-life problems in several areas such as facilities location, parallel and distributed computing, and combinatorial data analysis. Combinatorial optimization problems, such as the traveling salesman problem, maximal clique and graph partitioning can be formulated as a QAP. In this paper, we present some of the most important QAP formulations and classify them according to their mathematical sources. We also present a discussion on the theoretical resources used to define lower bounds for exact and heuristic algorithms. We then give a detailed discussion of the progress made in both exact and heuristic solution methods, including those formulated according to metaheuristic strategies. Finally, we analyze the contributions brought about by the study of different approaches.     

A cooperative parallel tabu search algorithm for the quadratic assignment problem

In this study, we introduce a cooperative parallel tabu search algorithm (CPTS) for the quadratic assignment problem (QAP). The QAP is an NP-hard combinatorial optimization problem that is widely acknowledged to be computationally demanding. These characteristics make the QAP an ideal candidate for parallel solution techniques. CPTS is a cooperative parallel algorithm in which the processors exchange information throughout the run of the algorithm as opposed to independent concurrent search strategies that aggregate data only at the end of execution. CPTS accomplishes this cooperation by maintaining a global reference set which uses the information exchange to promote both intensification and strategic diversification in a parallel environment. This study demonstrates the benefits that may be obtained from parallel computing in terms of solution quality, computational time and algorithmic flexibility. A set of 41 test problems obtained from QAPLIB were used to analyze the quality of the CPTS algorithm. Additionally, we report results for 60 difficult new test instances. The CPTS algorithm is shown to provide good solution quality for all problems in acceptable computational times. Out of the 41 test instances obtained from QAPLIB, CPTS is shown to meet or exceed the average solution quality of many of the best sequential and parallel approaches from the literature on all but six problems, whereas no other leading method exhibits a performance that is superior to this.     

An algorithm for the generalized quadratic assignment problem

This paper reports on a new algorithm for the Generalized Quadratic Assignment problem (GQAP). The GQAP describes a broad class of quadratic integer programming problems, wherein M pair-wise related entities are assigned to N destinations constrained by the destinations’ ability to accommodate them. This new algorithm is based on a Reformulation Linearization Technique (RLT) dual ascent procedure. Experimental results show that the runtime of this algorithm is as good or better than other known exact solution methods for problems as large as M=20 and N=15. Current address of P.M. Hahn: 2127 Tryon Street, Philadelphia, PA 19146-1228, USA.     

The x-and-y-axes travelling salesman problem

The x-and-y-axes travelling salesman problem forms a special case of the Euclidean TSP, where all cities are situated on the x-axis and on the y-axis of an orthogonal coordinate system of the Euclidean plane. By carefully analyzing the underlying combinatorial and geometric structures, we show that this problem can be solved in polynomial time. The running time of the resulting algorithm is quadratic in the number of cities.     

On the robust assignment problem under a fixed number of cost scenarios

We investigate the complexity of the min-max assignment problem under a fixed number of scenarios. We prove that this problem is polynomial-time equivalent to the exact perfect matching problem in bipartite graphs, an infamous combinatorial optimization problem of unknown computational complexity.     

Open problems around exact algorithms

We list a number of open questions around worst case time bounds and worst case space bounds for NP-hard problems. We are interested in exponential time solutions for these problems with a relatively good worst case behavior. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature.     

Gilmore-Lawler bound of quadratic assignment problem

The Gilmore-Lawler bound (GLB) is one of the well-known lower bound of quadratic assignment problem (QAP). Checking whether GLB is tight is an NP-complete problem. In this article, based on Xia and Yuan linearization technique, we provide an upper bound of the complexity of this problem, which makes it pseudo-polynomial solvable. We also pseudopolynomially solve a class of QAP whose GLB is equal to the optimal objective function value, which was shown to remain NP-hard.      

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

Comparative performance of tabu search and simulated annealing heuristics for the quadratic assignment problem

For almost two decades the question of whether tabu search (TS) or simulated annealing (SA) performs better for the quadratic assignment problem has been unresolved. To answer this question satisfactorily, we compare performance at various values of targeted solution quality, running each heuristic at its optimal number of iterations for each target. We find that for a number of varied problem instances, SA performs better for higher quality targets while TS performs better for lower quality targets.     

A well-solvable special case of the bounded knapsack problem

We identify a polynomially solvable special case of the bounded knapsack problem that is characterized by a set of simple inequalities relating item weight ratios to item profit ratios. Our result generalizes and extends a corresponding result of Zukerman, et al. [M. Zukerman, L. Jia, T. Neame, G.J. Woeginger, A polynomially solvable special case of the unbounded knapsack problem, Operations Research Letters 29 (2001) 13-16] for the unbounded knapsack problem.     

On the roots of Wiener polynomials of graphs

The Wiener polynomial of a connected graph $G$ is defined as $W(G;x)=\sum x^{d(u,v)}$, where $d(u,v)$ denotes the distance between $u$ and $v$, and the sum is taken over all unordered pairs of distinct vertices of $G$. We examine the nature and location of the roots of Wiener polynomials of graphs, and in particular trees. We show that while the maximum modulus among all roots of Wiener polynomials of graphs of order $n$ is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)?1$, the maximum modulus among all roots of Wiener polynomials of trees of order $n$ grows linearly in $n$. We prove that the closure of the collection of real roots of Wiener polynomials of all graphs is precisely $(?\infty ,0]$, while in the case of trees, it contains $(?\infty ,?1]$. Finally, we demonstrate that the imaginary parts and (positive) real parts of roots of Wiener polynomials can be arbitrarily large.     

On degree sequence optimization

We consider the problem of finding a subgraph of a given graph maximizing a given function evaluated at its degree sequence. While it is intractable already for convex functions, we show it is polynomial time solvable for convex multi-criteria objectives. We also consider a colored extension of the problem with separable objectives, which includes the notorious exact matching problem as a special case, and show that it is polynomial time solvable on graphs of bounded tree-depth for any vertex functions.     

Competitive subset selection with two agents

We address an optimization problem in which two agents, each with a set of weighted items, compete in order to maximize the total weight of their winning sets. The latter are built according to a sequential game consisting in a fixed number of rounds. In every round each agent submits one item for possible inclusion in its winning set. We study two natural rules to decide the winner of each round.For both rules we deal with the problem from different perspectives. From a centralized point of view, we investigate (i) the structure and the number of efficient (i.e. Pareto optimal) solutions, (ii) the complexity of finding such solutions, (iii) the best-worst ratio, i.e. the ratio between the efficient solution with largest and smallest total weight, and (iv) existence of Nash equilibria.Finally, we address the problem from a single agent perspective. We consider preventive or maximin strategies, optimizing the objective of the agent in the worst case, and best response strategies, where the items submitted by the other agent are known in advance either in each round (on-line) or for the whole game (off-line).