## Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more

## Primal-dual algorithms and infinite-dimensional Jordan algebras of finite rank

We consider primal-dual algorithms for certain types of infinite-dimensional optimization problems. Our approach is based on the generalization of the technique of finite-dimensional Euclidean Jordan algebras to the case of infinite-dimensional JB-algebras of finite rank. This generalization enables us to develop polynomial-time primal-dual algorithms for “infinite-dimensional second-order cone programs.” We consider as an example a … Read more

## Effective reformulations of the truss topology design problem

We present a new formulation of the truss topology problem that results in unique design and unique displacements of the optimal truss. This is reached by adding an upper level to the original optimization problem and formulating the new problem as an MPCC (Mathematical Program with Complementarity Constraints). We derive optimality conditions for this problem … Read more

## Partition of a Set of Integers into Subsets with Prescribed Sums

A nonincreasing sequence of positive integers $\langle m_1,m_2,\cdots,m_k \rangle$ is said to be {\em $n$-realizable\/} if the set $I_n=\{ 1,2,\cdots,n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,\cdots, S_k$ such that $\sum\limits_{x\in S_i}x=m_i$ for each $1\le i\le k$. In this paper, we will prove that a nonincreasing sequence of positive integers $\langle m_1,m_2,\cdots,m_k\rangle$ is … Read more

## Computational study of large-scale p-Median problems

Given a directed graph G(V,A), the p-Median problem consists of determining p nodes (the median nodes) minimizing the total distance from the other nodes of the graph. We present a Branch-and-Cut algorithm yielding provably good solutions for instances up to 3795 nodes (14,402,025 variables). Key ingredients of our approach are: lagrangian relaxation, a simple procedure … Read more

## Numerical Stability of Path Tracing in Polyhedral Homotopy Continuation Methods

The reliability of polyhedral homotopy continuation methods for solving a polynomial system becomes increasingly important as the dimension of the polynomial system increases. High powers of the homotopy continuation parameter $t$ and ill-conditioned Jacobian matrices encountered in tracing of homotopy paths affect the numerical stability. We present modified homotopy functions with a new homotopy continuation … Read more

## When the greedy algorithm fails

We provide a characterization of the cases when the greedy algorithm may produce the unique worst possible solution for the problem of finding a minimum weight base in a uniform independence system when the weights are taken from a finite range. We apply this theorem to TSP and the minimum bisection problem. The practical message … Read more

## Design and analysis of an approximation algorithm for Stackelberg network pricing

We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of $\frac{1}{2}\log m_T+1$, where … Read more

## New global optima for Morse clusters at $\rho=8$

We recently discovered 5 new putative globally optimum configurations for Morse clusters at $\rho=8$. This report contains some algorithmic details as well as the structures determined with our method. Citation Technical Report DSI 3-2003, Dipartimento di Sistemi e Informatica, Università degli Studi di Firenze, Firenze, 2003. Article Download View New global optima for Morse clusters … Read more

## Stable Sets of Weak Tournaments

The purpose of this paper is to obtain conditions on weak tournaments, which guarantee that every non-empty subset of alternatives admits a stable set. We show that every stable set always contains the core. We also show that there exists a unique stable set for each non-empty subset of alternatives which coincides with its core … Read more