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

Page 1 Next

Displaying 1 – 20 of 22

Showing per page

Semi-definite positive programming relaxations for graph K 𝐧 -coloring in frequency assignment

Philippe Meurdesoif, Benoît Rottembourg (2001)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct n -uples of colors used to color a given set of n -complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible...

Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment

Philippe Meurdesoif, Benoît Rottembourg (2010)

RAIRO - Operations Research

In this paper we will describe a new class of coloring problems, arising from military frequency assignment, where we want to minimize the number of distinct n-uples of colors used to color a given set of n-complete-subgraphs of a graph. We will propose two relaxations based on Semi-Definite Programming models for graph and hypergraph coloring, to approximate those (generally) NP-hard problems, as well as a generalization of the works of Karger et al. for hypergraph coloring, to find good feasible...

Simultaneous solution of linear equations and inequalities in max-algebra

Abdulhadi Aminu (2011)

Kybernetika

Let a ø p l u s b = max ( a , b ) and a ø t i m e s b = a + b for a , b ∈ ℝ . Max-algebra is an analogue of linear algebra developed on the pair of operations ( ø p l u s , ø t i m e s ) extended to matrices and vectors. The system of equations A ø t i m e s x = b and inequalities C ø t i m e s x ł e q d have each been studied in the literature. We consider a problem consisting of these two systems and present necessary and sufficient conditions for its solvability. We also develop a polynomial algorithm for solving max-linear program whose constraints are max-linear equations and inequalities.

Solution of a fractional combinatorial optimization problem by mixed integer programming

Alain Billionnet, Karima Djebali (2006)

RAIRO - Operations Research

Fractionnal mathematical programs appear in numerous operations research, computer science and economic domains. We consider in this paper the problem of maximizing the sum of 0–1 hyperbolic ratios (SRH). In contrast to the single ratio problem, there has been little work in the literature concerning this problem. We propose two mixed-integer linear programming formulations of SRH and develop two different strategies to solve them. The first one consists in using directly a general-purpose mixed-integer...

Solving a permutation problem by a fully polynomial-time approximation scheme

Stanisław Gawiejnowicz, Wiesław Kurc, Lidia Pankowska (2010)

Discussiones Mathematicae, Differential Inclusions, Control and Optimization

For a problem of optimal discrete control with a discrete control set composed of vertices of an n-dimensional permutohedron, a fully polynomial-time approximation scheme is proposed.

Solving the Crop Allocation Problem using Hard and Soft Constraints

Mahuna Akplogan, Simon de Givry, Jean-Philippe Métivier, Gauthier Quesnel, Alexandre Joannon, Frédérick Garcia (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Application tools for the crop allocation problem (CAP) are required for agricultural advisors to design more efficient farming systems. Despite the extensive treatment of this issue by agronomists in the past, few methods tackle the crop allocation problem considering both the spatial and the temporal aspects of the CAP. In this paper, we precisely propose an original formulation addressing the crop allocation planning problem while taking farmers’ management choices into account. These choices...

Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic

Christian Laforest, Raksmey Phan (2013)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including...

Solving the simple plant location problem by genetic algorithm

Jozef Kratica, Dušan Tošic, Vladimir Filipović, Ivana Ljubić (2001)

RAIRO - Operations Research - Recherche Opérationnelle

The simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 facility sites and customers. Computational results are presented and compared to dual based algorithms.

Solving the simple plant location problem by genetic algorithm

Jozef Kratica, Dušan Tošic, Vladimir Filipović, Ivana Ljubić (2010)

RAIRO - Operations Research

The simple plant location problem (SPLP) is considered and a genetic algorithm is proposed to solve this problem. By using the developed algorithm it is possible to solve SPLP with more than 1000 facility sites and customers. Computational results are presented and compared to dual based algorithms.

Solving the Task Assignment Problem with a Variable Neighborhood Search

Kratica, Jozef, Savić, Aleksandar, Filipović, Vladimir, Milanović, Marija (2010)

Serdica Journal of Computing

In this paper a variable neighborhood search (VNS) approach for the task assignment problem (TAP) is considered. An appropriate neighborhood scheme along with a shaking operator and local search procedure are constructed specifically for this problem. The computational results are presented for the instances from the literature, and compared to optimal solutions obtained by the CPLEX solver and heuristic solutions generated by the genetic algorithm. It can be seen that the proposed VNS approach reaches...

Currently displaying 1 – 20 of 22

Page 1 Next