In this paper we present a filter algorithm for nonlinear programming and prove its global convergence to stationary points. Each iteration is composed of a restoration phase, which reduces a measure of infeasibility, and an optimality phase, which reduces the objective function in a tangential approximation of the feasible set. These two phases are totally … Read more
The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges … Read more
The classical non-linear mixed integer formulation of the transmission network expansion problem cannot guarantee finding the optimal solution due to its non-convex nature. We propose an alternative mixed integer linear disjunctive formulation, which has better conditioning properties than the standard disjunctive model. The mixed integer program is solved by a commercial Branch and Bound code, … Read more
In this paper we study practical solution methods for finding the maximum-volume ellipsoid inscribing a given full-dimensional polytope in $\Re^n$ defined by a finite set of linear inequalities. Our goal is to design a general-purpose algorithmic framework that is reliable and efficient in practice. To evaluate the merit of a practical algorithm, we consider two … Read more
We describe the object-oriented software package OOQP for solving convex quadratic programming problems (QP). The primal-dual interior point algorithms supplied by OOQP are implemented in a way that is largely independent of the problem structure. Users may exploit problem structure by supplying linear algebra, problem data, and variable classes that are customized to their particular … Read more
In 1961 Leon Steinberg formulated a “backboard wiring” problem that has resisted solution for 40 years. Steinberg’s wiring problem is to determine the locations of 34 computer components on a 4 by 9 grid so as to minimize the total length of the wiring required to interconnect them. The problem is an example of a … Read more
We study convex conic optimization problems in which the right-hand side and the cost vectors vary linearly as a function of a scalar parameter. We present a unifying geometric framework that subsumes the concept of the optimal partition in linear programming (LP) and semidefinite programming (SDP) and extends it to conic optimization. Similar to the … Read more
We compare several semidefinite relaxations for the cut polytope obtained by applying the lift and project methods of Lov\’asz and Schrijver and of Lasserre. We show that the tightest relaxation is obtained when aplying the Lasserre construction to the node formulation of the max-cut problem. This relaxation $Q_t(G)$ can be defined as the projection on … Read more
We describe extensions to algebraic modeling languages and their solver interfaces that will be needed to take advantage of constraint programming solvers, particularly in the area of combinatorial optimization. CitationTechnical Report, Department of Industrial Engineering and Management Sciences, Northwestern University (2001); based on a shorter version that appeared in the Proceedings of the Third International … Read more
In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of … Read more