In this study, a lifting procedure is applied to some existing formulations of the Diameter Constrained Minimum Spanning Tree Problem. This problem typically models network design applications where all vertices must communicate with each other at minimum cost, while meeting or surpassing a given quality requirement. An alternative formulation is also proposed for instances of … Read more
We present a unifying framework to establish a lower-bound on the number of semidefinite programming based, lift-and-project iterations (rank) for computing the convex hull of the feasible solutions of various combinatorial optimization problems. This framework is based on the maps which are commutative with the lift-and-project operators. Some special commutative maps were originally observed by … Read more
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