Cooperative games on antimatroids

The aim of this paper is to introduce cooperative games with a feasible coalition system which is an antimatroid. These combinatorial structures generalize the permission structures, which have nice economical applications. With this goal, we first characterize the approaches from a permission structure with special classes of antimatroids. Next, we use the concept of interior … Read more

Benchmarking Optimization Software with COPS

We describe version 2.0 of the COPS set of nonlinearly constrained optimization problems. We have added new problems, as well as streamlined and improved most of the problems. We also provide a comparison of the LANCELOT, LOQO, MINOS, and SNOPT solvers on these problems. Citation Technical Report ANL/MCS-246 Mathematics and Computer Science Division Argonne National … Read more

GPCG: A case study in the performance and scalability of optimization algorithms

GPCG is an algorithm within the Toolkit for Advanced Optimization (TAO) for solving bound constrained, convex quadratic problems. Originally developed by More’ and Toraldo, this algorithm was designed for large-scale problems but had been implemented only for a single processor. The TAO implementation is available for a wide range of high-performance architecture, and has been … Read more

Augmented self concordant barriers and nonlinear optimization problems with finite complexity

In this paper we study special barrier functions for the convex cones, which are the sum of a self-concordant barrier for the cone and a positive-semidefinite quadratic form. We show that the central path of these augmented barrier functions can be traced with linear speed. We also study the complexity of finding the analytic center … Read more

Hyper-sparsity in the revised simplex method and how to exploit it

The revised simplex method is often the method of choice when solving large scale sparse linear programming problems, particularly when a family of closely-related problems is to be solved. Each iteration of the revised simplex method requires the solution of two linear systems and a matrix vector product. For a significant number of practical problems … Read more

Solving Large Quadratic Assignment Problems on Computational Grids

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n >= 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using … Read more

On the Value of Binary Expansions For General Mixed-Integer Linear Programs

We study the use of binary variables in reformulating general mixed-integer linear programs. We show that binary reformulations result in problems for which almost all the binary variables replacing a general integer variable need to be explored during branching. We also give computational results on the performance of such reformulations in solving the mixed-integer programs, … Read more

Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lov\’asz-Schrijver Lift-and-Project Procedure

We study how the lift-and-project method introduced by Lov\’az and Schrijver \cite{LS91} applies to the cut polytope. We show that the cut polytope of a graph can be found in $k$ iterations if there exist $k$ edges whose contraction produces a graph with no $K_5$-minor. Therefore, for a graph with $n\ge 4$ nodes, $n-4$ iterations … Read more

Symbolic-Algebraic Computations in a Modeling Language for Mathematical Programming

AMPL is a language and environment for expressing and manipulating mathematical programming problems, i.e., minimizing or maximizing an algebraic objective function subject to algebraic constraints. AMPL permits separating a model, i.e., a symbolic representation of a class of problems, from the data required to specify a particular problem instance. Once AMPL has a problem instance, … Read more

Feasibility Control in Nonlinear Optimization

We analyze the properties that optimization algorithms must possess in order to prevent convergence to non-stationary points for the merit function. We show that demanding the exact satisfaction of constraint linearizations results in difficulties in a wide range of optimization algorithms. Feasibility control is a mechanism that prevents convergence to spurious solutions by ensuring that … Read more