We describe strong mixed-integer programming formulations for robust mixed 0-1 programming with uncertainty in the objective coefficients. In particular, we focus on an objective uncertainty set described as a polytope with a budget constraint. We show that for a robust 0-1 problem, there is a tight linear programming formulation with size polynomial in the size … Read more
Interior-point methods (IPMs), originally conceived in the context of linear programming have found a variety of applications in integer programming, and combinatorial optimization. This survey presents an up to date account of IPMs in solving NP-hard combinatorial optimization problems to optimality, and also in developing approximation algorithms for some of them. The surveyed approaches include … Read more
In the context of integer programming, we develop a polyhedral method for linearizing a product of a pair of real linear functions in 0/1 variables. As an example, by writing a pair of integer variables in binary expansion, we have a technique for linearizing their product. We give a complete linear description for the resulting … Read more
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
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
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
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
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
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
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