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.
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.
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.
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.
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...
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...
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...
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...
We give a new formulation for the problem of task scheduling into
unrelated processors under precedence constraints. This formulation
has a polynomial number of variables and does not require that the
processing times be integer valued.
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...
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...
Download Results (CSV)