All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 4 Next

Displaying 61 – 80 of 219

Showing per page

Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut

Francisco Barahona, László Ladányi (2006)

RAIRO - Operations Research

We present a Branch-and-Cut algorithm where the volume algorithm is applied instead of the traditionally used dual simplex algorithm to the linear programming relaxations in the root node of the search tree. This means that we use fast approximate solutions to these linear programs instead of exact but slower solutions. We present computational results with the Steiner tree and Max-Cut problems. We show evidence that one can solve these problems much faster with the volume algorithm based...

Clique partitioning of interval graphs with submodular costs on the cliques

Dion Gijswijt, Vincent Jost, Maurice Queyranne (2007)

RAIRO - Operations Research

Given a graph G = (V,E) and a “cost function” f : 2 V → ℝ (provided by an oracle), the problem [PCliqW] consists in finding a partition into cliques of V(G) of minimum cost. Here, the cost of a partition is the sum of the costs of the cliques in the partition. We provide a polynomial time dynamic program for the case where G is an interval graph and f belongs to a subclass of submodular set functions, which we call “value-polymatroidal”. This provides a common solution for various generalizations of the...

Codings and operators in two genetic algorithms for the leaf-constrained minimum spanning tree problem

Bryant Julstrom (2004)

International Journal of Applied Mathematics and Computer Science

The features of an evolutionary algorithm that most determine its performance are the coding by which its chromosomes represent candidate solutions to its target problem and the operators that act on that coding. Also, when a problem involves constraints, a coding that represents only valid solutions and operators that preserve that validity represent a smaller search space and result in a more effective search. Two genetic algorithms for the leaf-constrained minimum spanning tree problem illustrate...

Combinatorial optimization in DNA mapping — A computational thread of the simplified partial digest problem

Jacek Blazewicz, Marta Kasprzak (2005)

RAIRO - Operations Research - Recherche Opérationnelle

In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O( n log n )-time algorithm is given, where n is a number of restriction...

Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem

Jacek Blazewicz, Marta Kasprzak (2006)

RAIRO - Operations Research

In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach — the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(nlogn)-time algorithm is given, where n is a number of...

Comparing classification tree structures: A special case of comparing q-ary relations II

I. C. Lerman, F. Rouxel (2010)

RAIRO - Operations Research

Comparing q-ary relations on a set 𝒪 of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches to tree comparison are discussed in the context...

Comparing classification tree structures: a special case of comparing q-ary relations

Israel-Cesar Lerman (2010)

RAIRO - Operations Research

Comparing q-ary relations on a set 𝒪 of elementary objects is one of the most fundamental problems of classification and combinatorial data analysis. In this paper the specific comparison task that involves classification tree structures (binary or not) is considered in this context. Two mathematical representations are proposed. One is defined in terms of a weighted binary relation; the second uses a 4-ary relation. The most classical approaches to tree comparison are discussed in the context...

Complexity of partial inverse assignment problem and partial inverse cut problem

Xiaoguang Yang (2001)

RAIRO - Operations Research - Recherche Opérationnelle

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Complexity of Partial Inverse Assignment Problem and Partial Inverse Cut Problem

Xiaoguang Yang (2010)

RAIRO - Operations Research

For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.

Configuration des lignes d'usinage à boîtiers multibroches : une approche mixte

Olga Guschinskaya, Alexandre Dolgui (2009)

RAIRO - Operations Research

Ce travail porte sur l'optimisation des lignes d'usinage pour la grande série. Une telle ligne comporte plusieurs postes de travail, chacun étant équipé avec boîtiers multibroches. Un boîtier multibroche exécute plusieurs opérations en parallèle. Lors de la conception en avant-projet, il est nécessaire d'affecter toutes les opérations à des boîtiers et des postes de travail de sorte à minimiser le nombre de postes et de boîtiers utilisés. Pour ce nouveau problème d'équilibrage des lignes de production,...

Constrained Steiner trees in Halin graphs

Guangting Chen, Rainer E. Burkard (2003)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

Constrained Steiner trees in Halin graphs

Guangting Chen, Rainer E. Burkard (2010)

RAIRO - Operations Research

In this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem.

Continuous reformulations and heuristics for the euclidean travelling salesperson problem

Tuomo Valkonen, Tommi Kärkkäinen (2009)

ESAIM: Control, Optimisation and Calculus of Variations

We consider continuous reformulations of the euclidean travelling salesperson problem (TSP), based on certain clustering problem formulations. These reformulations allow us to apply a generalisation with perturbations of the Weiszfeld algorithm in an attempt to find local approximate solutions to the euclidean TSP.

Continuous reformulations and heuristics for the Euclidean travelling salesperson problem

Tuomo Valkonen, Tommi Kärkkäinen (2008)

ESAIM: Control, Optimisation and Calculus of Variations

We consider continuous reformulations of the Euclidean travelling salesperson problem (TSP), based on certain clustering problem formulations. These reformulations allow us to apply a generalisation with perturbations of the Weiszfeld algorithm in an attempt to find local approximate solutions to the Euclidean TSP.

Currently displaying 61 – 80 of 219