Lift-and-project for 0–1 programming via algebraic geometry

Recently, tools from algebraic geometry have been successfully applied to develop solution schemes for new classes of optimization problems. A central idea in these constructions is to express a polynomial that is positive on a given domain in terms of polynomials of higher degree so that its positivity is readily revealed. This resembles the “lifting” … Read more

On the Complexity of Scheduling with Elastic Times

We consider the problem of scheduling hypermedia documents with elastic times. The objects have variable durations characterized by ideal, minimum, and maximum values. A schedule is a set of tensions on the arcs of the precedence graph which also represents synchronization constraints. We consider the problem of deciding if there exists a schedule in which … Read more

Multiprocessor Scheduling under Precedence Constraints: Polyhedral Results

We consider the problem of scheduling a set of tasks related by precedence constraints to a set of processors, so as to minimize their makespan. Each task has to be assigned to a unique processor and no preemption is allowed. A new integer programming formulation of the problem is given and strong valid inequalities are … Read more

Automatic Scheduling of Hypermedia Documents with Elastic Times]

The problem of automatic scheduling hypermedia documents consists in finding the optimal starting times and durations of objects to be presented, to ensure spatial and temporal consistency of a presentation while respecting limits on shrinking and stretching the ideal duration of each object. The combinatorial nature of the minimization of the number of objects whose … Read more

An application of integer programming to playoff elimination in football championships

Football is the most followed and practiced sport in Brazil, with a major economic importance. Thousands of jobs depend directly from the activity of the football teams. The Brazilian national football championship is followed by millions of people, who attend the games in the stades, follow radio and TV transmissions, and check newspapers, radio, TV, … Read more

An Exact Algorithm for the Capacitated Vertex p-Center Problem

We develop a simple and practical exact algorithm for the problem of locating $p$ facilities and assigning clients to them within capacity restrictions in order to minimize the maximum distance between a client and the facility to which it is assigned (capacitated $p$-center). The algorithm iteratively sets a maximum distance value within which it tries … Read more

The Quadratic Selective Travelling Saleman Problem

A well-known extension of the Travelling Salesman Problem (TSP) is the Selective TSP (STSP): Each node has an associated profit and instead of visiting all nodes, the most profitable set of nodes, taking into account the tour cost, is visited. The Quadratic STSP (QSTSP) adds the additional complication that each pair of nodes have an … Read more

An Efficient Exact Algorithm for the Vertex hBcCenter Problem and Computational Experiments for Different Set Covering Subproblems

We develop a simple and yet very efficient exact algorithm for the problem of locating $p$ facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility to which it is assigned. The algorithm iteratively sets a maximum distance value within which it tries to assign all … Read more

On Robust 0-1 Optimization with Uncertain Cost Coefficients

Based on the recent approach of Bertsimas and Sim \cite{bs1, bs2} to robust optimization in the presence of data uncertainty, we prove a bound on the probability that the robust solution gives an objective function value worse than the robust objective function value, under the assumption that only cost coefficients are subject to uncertainty. A … Read more

Semidefinite programming and integer programming

We survey how semidefinite programming can be used for finding good approximative solutions to hard combinatorial optimization problems. CitationPreliminary version appeared as Report PNA-R0210, CWI, Amsterdam, April 2002. To appear as Chapter in the Handbook on Discrete Optimization, K. Aardal, G. Nemhauser, R. Weismantel, eds., Elsevier Publishers.ArticleDownload View PDF