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
A greedy randomized adaptive search procedure (GRASP) is a multi-start metaheuristic which applies local search to starting solutions generated by a greedy randomized construction procedure. Until recently, most implementations of GRASP assumed independence of its iterations, thus making no use of memory structures. Path-relinking is an intensification strategy which explores trajectories between elite solutions. Using … Read more
A phylogenetic tree relates taxonomic units, based on their similarity over a set of characters. We propose a new genetic algorithm for the problem of building a phylogenetic tree under the parsimony criterion. This genetic algorithm makes use of an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originaly proposed … 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
A method for solving inequality constrained minimization problems is described. The algorithm is based on a primal-dual interior point approach, with a line search globalization strategy. A quasi-Newton technique (BFGS) with limited memory storage is used to approximate the second derivatives of the functions. The method is especially intended for solving problems with a large … Read more
In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPEC’s)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties, present an example … Read more
The homogeneous model for linear programs is an elegant means of obtaining the solution or certificate of infeasibility and has importance regardless of the method used for solving the problem, interior-point methods or other methods. In 1999, Andersen and Ye generalized this model to monotone complementarity problems (CPs) and showed that most of the desirable … Read more
We consider the scheduling problem of minimizing the average weighted completion time on identical parallel machines when jobs are arriving over time. For both the preemptive and the nonpreemptive setting, we show that straightforward extensions of Smith’s ratio rule yield smaller competitive ratios than the previously best-known deterministic on-line algorithms. CitationWorking Paper 4435-03, Sloan School … Read more
The low-rank semidefinite programming problem (LRSDP_r) is a restriction of the semidefinite programming problem (SDP) in which a bound r is imposed on the rank of X, and it is well known that LRSDP_r is equivalent to SDP if r is not too small. In this paper, we classify the local minima of LRSDP_r and … Read more