A permutation of the elements of a finite set is a linear order. Linear Ordering Problem (LOP) is a well known combinatorial optimization problem
and is known to be NP-hard. The Fixed Cardinality Linear ordering Problem (FCLOP) is an extension of the LOP in which the number of vertices in a feasible solution is limited to p (the cardinality number that is less than or equal to the number of nodes). In the graph associated to a feasible solution of the FCLOP, there exist an arc from the vertex i to the vertex j if and only if (1) the vertices i and j both are among the p selected vertices and (2) the vertex i be ordered before the vertex j. The objective function is to maximize the sum of the weights of all the arcs
presented in this graph. The FCLOP is presented for the first time in this PhD study.
In this study, we have introduced an integer programming formulation for the problem, determined dimension of the Polytope for any choice (integer) of p, introduced several classes of valid inequalities and characterized some classes of facet defining inequalities. We have also developed several solution algorithms to solve instances of the problem.
• M. Ali Ridha Mahjoub, Professeur, Université Paris Dauphine (Paris 9)
• M. Philippe Michelon, Professeur, Université d’Avignon et des Pays de Vaucluse LIA – CERI
• M. Herve Kerivin, maître de conférence, Universite Blaise Pascal, Clermont-Ferrand, France
• M. Mohamed Didi Biha, Professeur, Universite de Caen Basse-Normandie, France
• M. Mourad Baiou, Chargé de recherche, LIMOS, Universite Blaise Pascal, Clermont-Ferrand, France
• M. Philippe Mahey, Professeur, Universite Blaise Pascal, Clermont-Ferrand, France