We study the maximum stable set problem. For a given graph, we establish several transformations among feasible solutions of different formulations of Lov{\’a}sz’s theta function. We propose reductions from feasible solutions corresponding to a graph to those corresponding to its subgraphs. We develop an efficient, polynomial-time algorithm to extract a maximum stable set in a … 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
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
We propose a new method for non-bijective graph matching for model-based pattern recognition. We formulate the search for the best correspondence between a model and an over-segmented image as a new combinatorial optimization problem, defined by the relational attributed graphs representing the model and the image where recognition has to be performed, together with the … Read more
A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. We propose a new neighborhood structure for the phylogeny problem. A GRASP heuristic based on this neighborhood structure and using VND for … Read more
A phylogeny is a tree that relates taxonomic units, based on their similarity over a set of characters. The problem of finding a phylogeny with the minimum number of evolutionary steps (the so-called parsimony criterion) is one of the main problems in comparative biology. In this work, we study different heuristic approaches to the phylogeny … Read more
Many oil wells in Brazilian onshore fields rely on artificial lift methods. Maintenance services such as cleaning, reinstatement, stimulation and others are essential to these wells. These services are performed by workover rigs, which are avaliable on a limited number with respect to the number of wells demanding service. The decision of which workover rig … 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
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
Representation of a given nonnegative multivariate polynomial in terms of a sum of squares of polynomials has become an essential subject in recent developments of sums of squares optimization and SDP (semidefinite programming) relaxation of polynomial optimization problems. We disscuss effective methods to obtain a simpler representation of a “sparse” polynomial as a sum of … Read more