Box-inequalities for quadratic assignment polytopes

Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment problem several times in the recent years. Their quality has turned out to be quite good in practice. Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic assignment polytope) have been started during the last decade [34, 31, 21, 22]. They have lead to basic knowledge on these polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining) inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as for the symmetric quadratic assignment polytope. Received: April 17, 2000 / Accepted: July 3, 2001?Published online September 3, 2001     

Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem

The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient solution. In this work we propose a new approach that combines two existing procedures: the master problem of a simplicial decomposition algorithm is solved through the analytic center cutting plane method. Four variants are considered for solving the master problem. The third and fourth ones, which heuristically compute an appropriate initial point, provided the best results. The computational experience reported in the solution of real large-scale diagonal and difficult asymmetric problems—including a subset of the transportation networks of Madrid and Barcelona—show the effectiveness of the approach.     

A Polyhedral Approach for Nonconvex Quadratic Programming Problems with Box Constraints

We apply a linearization technique for nonconvex quadratic problems with box constraints. We show that cutting plane algorithms can be designed to solve the equivalent problems which minimize a linear function over a convex region. We propose several classes of valid inequalities of the convex region which are closely related to the Boolean quadric polytope. We also describe heuristic procedures for generating cutting planes. Results of preliminary computational experiments show that our inequalities generate a polytope which is a fairly tight approximation of the convex region.     

An Improved Heuristic for the Quadratic Assignment Problem

A technique is described whereby the computational efficiency of the Lashkari-Jaisingh heuristic for the quadratic assignment problem is greatly enhanced. Results for the modified heuristic are presented which demonstrate that it provides solutions of consistently high quality at relatively small computational cost.     

Cutting plane approach for the maximum flow interdiction problem

The maximum flow interdiction is a class of leader–follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.     

On the enumerative nature of Gomory’s dual cutting plane method

For 30 years after their invention half a century ago, cutting planes for integer programs have been an object of theoretical investigations that had no apparent practical use. When they finally proved their practical usefulness in the late eighties, that happened in the framework of branch and bound procedures, as an auxiliary tool meant to reduce the number of enumerated nodes. To this day, pure cutting plane methods alone have poor convergence properties and are typically not used in practice. Our reason for studying them is our belief that these negative properties can be understood and thus remedied only based on a thorough investigation of such procedures in their pure form. In this paper, the second in a sequence, we address some important issues arising when designing a computationally sound pure cutting plane method. We analyze the dual cutting plane procedure proposed by Gomory in 1958, which is the first (and most famous) convergent cutting plane method for integer linear programming. We focus on the enumerative nature of this method as evidenced by the relative computational success of its lexicographic version (as documented in our previous paper on the subject), and we propose new versions of Gomory’s cutting plane procedure with an improved performance. In particular, the new versions are based on enumerative schemes that treat the objective function implicitly, and redefine the lexicographic order on the fly to mimic a sound branching strategy. Preliminary computational results are reported.     

Static and Dynamic Layout Problems with Varying Areas

This paper describes a two-step algorithm for solving the layout problem while assuming the departments can have varying areas. The first step solves a quadratic assignment problem formulation of the problem using a heuristic cutting plane routine. The second step solves a mixed-integer linear programming prob- lem to find the desired block diagram layout. The algorithm incorporates two concepts to make the solu- tions more practical. First, rearrangement costs are simultaneously considered along with flow costs in solving a dynamic layout problem involving multiple time periods. It is the only algorithm to solve a general dynamic layout problem with varying department areas. Second, regular department shapes are maintained by requiring all departments to be rectangular. Its formulation for doing this is more efficient than previous algorithms.     

The Use of Specially Structured Models for Obtaining Bounds in the Quadratic Assignment Problem

In this paper we study a procedure for finding bounds for the quadratic assignment problem. This procedure may be used as a sub-routine in hybrid procedures for solving this problem. The approach is based upon a data decomposition method, linking the actual data to the data of a special class of assignment problems for which bounds are computationally tractable.     

Tabu search for graph partitioning

In this paper, we develop a tabu search procedure for solving the uniform graph partitioning problem. Tabu search, an abstract heuristic search method, has been shown to have promise in solving several NP-hard problems, such as job shop and flow shop scheduling, vehicle routing, quadratic assignment, and maximum satisfiability. We compare tabu search to other heuristic procedures for graph partitioning, and demonstrate that tabu search is superior to other solution approaches for the uniform graph partitioning problem both with respect to solution quality and computational requirements.     

Computational aspects of cutting-plane algorithms for geometric programming problems

This paper presents the results of computational studies of the properties of cutting plane algorithms as applied to posynomial geometric programs. The four cutting planes studied represent the gradient method of Kelley and an extension to develop tangential cuts; the geometric inequality of Duffin and an extension to generate several cuts at each iteration. As a result of over 200 problem solutions, we will draw conclusions regarding the effectiveness of acceleration procedures, feasible and infeasible starting point, and the effect of the initial bounds on the variables. As a result of these experiments, certain cutting plane methods are seen to be attractive means of solving large scale geometric programs.This author's research was supported in part by the Center for the Study of Environmental Policy, The Pennsylvania State University.     

Convergent Outer Approximation Algorithms for Solving Unary Programs

Interesting cutting plane approaches for solving certain difficult multiextremal global optimization problems can fail to converge. Examples include the concavity cut method for concave minimization and Ramana's recent outer approximation method for unary programs which are linear programming problems with an additional constraint requiring that an affine mapping becomes unary. For the latter problem class, new convergent outer approximation algorithms are proposed which are based on sufficiently deep l-norm or quadratic cuts. Implementable versions construct optimal simplicial inner approximations of Euclidean balls and of intersections of Euclidean balls with halfspaces, which are of general interest in computational convexity. Computational behavior of the algorithms depends crucially on the matrices involved in the unary condition. Potential applications to the global minimization of indefinite quadratic functions subject to indefinite quadratic constraints are shown to be practical only for very small problem sizes.     

A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem

This paper is concerned with a new approach for solving quadratic assignment problems (QAP). We first reformulate QAP as a concave quadratic programming problem and apply an outer approximation algorithm. In addition, an improvement routine is incorporated in the final stage of the algorithm. Computational experiments on a set of standard data demonstrate that this algorithm can yield favorable results with a relatively low computational effort.     

Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs

Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computational study of a disjunctive cutting plane method for stochastic mixed 0-1 programs that uses lift-and-project cuts based on the extensive form of the two-stage SMIP problem. An extension of the method based on where the data uncertainty appears in the problem is made, and it is shown how a valid inequality derived for one scenario can be made valid for other scenarios, potentially reducing solution time. Computational results amply demonstrate the effectiveness of disjunctive cuts in solving several large-scale problem instances from the literature. The results are compared to the computational results of disjunctive cuts based on the subproblem space of the formulation and it is shown that the two methods are equivalently effective on the test instances.     

A Cutting Plane Approach to Solving Quadratic Infinite Programs on Measure Spaces

We study infinite dimensional quadratic programming (QP) problems of integral type. The decision variable is taken in the space of bounded regular Borel measures on compact Hausdorff spaces. An implicit cutting plane algorithm is developed to obtain an optimal solution of the infinite dimensional QP problem. The major computational tasks in using the implicit cutting plane approach to solve infinite dimensional QP problems lie in finding a global optimizer of a non-linear and non-convex program. We present an explicit scheme to relax this requirement and to get rid of the unnecessary constraints in each iteration in order to reduce the size of the computatioinal programs. A general convergence proof of this approach is also given.     

A New Heuristic for the Quadratic Assignment Problem

We propose a new heuristic for the solution of the quadratic assignment problem. The heuristic combines ideas from tabu search and genetic algorithms. Run times are very short compared with other heuristic procedures. The heuristic performed very well on a set of test problems.     

GRASP with path-relinking for the generalized quadratic assignment problem

The generalized quadratic assignment problem (GQAP) is a generalization of the NP-hard quadratic assignment problem (QAP) that allows multiple facilities to be assigned to a single location as long as the capacity of the location allows. The GQAP has numerous applications, including facility design, scheduling, and network design. In this paper, we propose several GRASP with path-relinking heuristics for the GQAP using different construction, local search, and path-relinking procedures. We introduce a novel approximate local search scheme, as well as a new variant of path-relinking that deals with infeasibilities. Extensive experiments on a large set of test instances show that the best of the proposed variants is both effective and efficient.     

On lower bounds for a class of quadratic 0, 1 programs

We present a new method of obtaining lower bounds for a class of quadratic 0, 1 programs that includes the quadratic assignment problem. The method generates a monotonic sequence of lower bounds and may be interpreted as a Lagrangean dual ascent procedure. We report on a computational comparison of our bounds with earlier work in [2] based on subgradient techniques.     

A comparison between a primal and a dual cutting plane algorithm for posynomial geometric programming problems

In this paper, primal and dual cutting plane algorithms for the solution of posynomial geometric programming problems are presented. It is shown that these cuts are deepest, in the sense that they cut off as much of the infeasible set as possible. Problems of nondifferentiability in the dual cutting plane are circumvented by the use of a subgradient. Although the resulting dual problem seems easier to solve, the computational experience seems to show that the primal cutting plane outperforms the dual.     

Lifting and separation procedures for the cut polytope

The max-cut problem and the associated cut polytope on complete graphs have been extensively studied over the last 25 years. However, in comparison, only little research has been conducted for the cut polytope on arbitrary graphs, in particular separation algorithms have received only little attention. In this study we describe new separation and lifting procedures for the cut polytope on general graphs. These procedures exploit algorithmic and structural results known for the cut polytope on complete graphs to generate valid, and sometimes facet defining, inequalities for the cut polytope on arbitrary graphs in a cutting plane framework. We report computational results on a set of well-established benchmark problems.