Currently displaying 1 – 16 of 16

Showing per page

Order by Relevance | Title | Year of publication

A New Relaxation in Conic Form for the Euclidean Steiner Problem in ℜ

Marcia FampaNelson Maculan — 2010

RAIRO - Operations Research

In this paper, we present a new mathematical programming formulation for the Euclidean Steiner Tree Problem (ESTP) in ℜ. We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an -optimal solution for this latter problem using interior-point algorithm.

A new relaxation in conic form for the euclidean Steiner problem in n

Marcia FampaNelson Maculan — 2001

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we present a new mathematical programming formulation for the euclidean Steiner Tree Problem (ESTP) in n . We relax the integrality constrains on this formulation and transform the resulting relaxation, which is convex, but not everywhere differentiable, into a standard convex programming problem in conic form. We consider then an efficient computation of an ϵ -optimal solution for this latter problem using interior-point algorithm.

Un Algorithme pour la Bipartition d'un Graphe en Sous-graphes de Cardinalité Fixée

Philippe MichelonStéphanie RipeauNelson Maculan — 2010

RAIRO - Operations Research

A branch-and-bound method for solving the min cut with size constraint problem is presented. At each node of the branch-and-bound tree the feasible set is approximated by an ellipsoid and a lower bound is computed by minimizing the quadratic objective function over this ellipsoid. An upper bound is also obtained by a Tabu search method. Numerical results will be presented.

Un algorithme pour la bipartition d’un graphe en sous-graphes de cardinalité fixée

Philippe MichelonStéphanie RipeauNelson Maculan — 2001

RAIRO - Operations Research - Recherche Opérationnelle

Nous présentons une méthode de Séparation et Évaluation Progressive pour la bipartition d’un graphe en 2 sous-ensembles ayant une cardinalité fixée. À chaque nœud de l’arbre de recherche, nous calculons une borne inférieure en dualisant les contraintes d’intégralité et en approximant le domaine réalisable par un ellipsoïde. Une borne supérieure est également calculée par la méthode Tabou. Des résultats numériques sont présentés et commentés.

Minmax regret combinatorial optimization problems: an Algorithmic Perspective

Alfredo Candia-VéjarEduardo Álvarez-MirandaNelson Maculan — 2011

RAIRO - Operations Research

Uncertainty in optimization is not a new ingredient. Diverse models considering uncertainty have been developed over the last 40 years. In our paper we essentially discuss a particular uncertainty model associated with combinatorial optimization problems, developed in the 90's and broadly studied in the past years. This approach named (in particular our emphasis is on the robust deviation criteria) is different from the classical approach for handling uncertainty, , where uncertainty is modeled by...

Minmax regret combinatorial optimization problems: an Algorithmic Perspective

Alfredo Candia-VéjarEduardo Álvarez-MirandaNelson Maculan — 2011

RAIRO - Operations Research

Uncertainty in optimization is not a new ingredient. Diverse models considering uncertainty have been developed over the last 40 years. In our paper we essentially discuss a particular uncertainty model associated with combinatorial optimization problems, developed in the 90's and broadly studied in the past years. This approach named (in particular our emphasis is on the robust deviation criteria) is different from the classical approach for handling uncertainty, , where uncertainty is modeled by...

Acyclic orientations with path constraints

Rosa M. V. FigueiredoValmir C. BarbosaNelson MaculanCid C. de Souza — 2008

RAIRO - Operations Research - Recherche Opérationnelle

Many well-known combinatorial optimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use in the solution of the vertex coloring problem and some versions of the frequency...

Column-generation in integer linear programming

Nelson MaculanMarcos de Mendonça PassiniJosé André de Moura BritoIrene Loiseau — 2003

RAIRO - Operations Research - Recherche Opérationnelle

We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application of this approach...

Acyclic Orientations with Path Constraints

Rosa M. V. FigueiredoValmir C. BarbosaNelson MaculanCid C. de Souza — 2009

RAIRO - Operations Research

Many well-known combinatorial optimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use in the solution of the vertex coloring problem and some versions of the frequency...

Column-Generation in Integer Linear Programming

We present an exact method for integer linear programming problems that combines branch and bound with column generation at each node of the search tree. For the case of models involving binary column vectors only, we propose the use of so-called geometrical cuts to be added to the subproblem in order to eliminate previously generated columns. This scheme could be applied to general integer problems without specific structure. We report computational results on a successful application of this...

Page 1

Download Results (CSV)