An iterative approach for cone complementarity problems for nonsmooth multibody dynamics

Aiming at a fast and robust simulation of large multibody systems with contacts and friction, this work presents a novel method for solving large cone complementarity problems by means of a fixed-point iteration. The method is an extension of the Gauss-Seidel and Gauss-Jacobi method with overrelaxation for symmetric convex linear complementarity problems. The method is … Read more

MIP-based heuristic for non-standard 3D-packing problems

This paper is the continuation of a previous work (Fasano 2004), dedicated to a MIP formulation for non-standard three-dimensional packing issues, with additional conditions. The Single Bin Packing problem (Basic Problem) is considered and its MIP formulation shortly surveyed, together with some possible extensions, including balancing, tetris-like items and non-standard domains. A MIP-based heuristic is … Read more

Expressing Combinatorial Optimization Problems by Systems of Polynomial Equations and the Nullstellensatz

Systems of polynomial equations over the complex or real numbers can be used to model combinatorial problems. In this way, a combinatorial problem is feasible (e.g. a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution. In the first part of this paper, we construct new … Read more

Convergence Analysis of an Interior-Point Method for Nonconvex Nonlinear Programming

In this paper, we present global and local convergence results for an interior-point method for nonlinear programming. The algorithm uses an $\ell_1$ penalty approach to relax all constraints, to provide regularization, and to bound the Lagrange multipliers. The penalty problems are solved using a simplified version of Chen and Goldfarb’s strictly feasible interior-point method [6]. … Read more

Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem

We consider semidefinite programming relaxations of the quadratic assignment problem, and show how to exploit group symmetry in the problem data. Thus we are able to compute the best known lower bounds for several instances of quadratic assignment problems from the problem library: [R.E. Burkard, S.E. Karisch, F. Rendl. QAPLIB – a quadratic assignment problem … Read more

A MIP Approach for some Practical Packing Problems: Balancing Constraints and Tetris-like Items

This paper considers packing problems with balancing conditions and items consisting of clusters of parallelepipeds (mutually orthogonal, i.e. tetris-like items). This issue is quite frequent in space engineering and a real-world application deals with the Automated Transfer Vehicle project (funded by the European Space Agency), at present under development. A Mixed Integer Programming (MIP) approach … Read more

Satisficing measures for analysis of risky positions

In this work we introduce a class of measures for evaluating the quality of financial positions based on their ability to achieve desired financial goals. In the spirit of Simon (1959), we call these measures satisficing measures and show that they are dual to classes of risk measures. This approach has the advantage that aspiration … Read more

A view of algorithms for optimization without derivatives

Let the least value of a function of many variables be required. If its gradient is available, then one can tell whether search directions are downhill, and first order conditions help to identify the solution. It seems in practice, however, that the vast majority of unconstrained calculations do not employ any derivatives. A view of … Read more

On the strength of cut-based inequalities for capacitated network design polyhedra

In this paper we study capacitated network design problems, differentiating directed, bidirected and undirected link capacity models. We complement existing polyhedral results for the three variants by new classes of facet-defining valid inequalities and unified lifting results. For this, we study the restriction of the problems to a cut of the network. First, we show … Read more

Improving a Formulation of the Quadratic Knapsack Problem

The Quadratic Knapsack Problem can be formulated, using an idea of Glover, as a mixed 0-1 linear program with only 2n variables. We present a simple method for strengthening that formulation, which gives good results when the profit matrix is dense and non-negative. Citation Working Paper, Department of Management Science, Lancaster University, May 2007. Article … Read more