p-Fixed Cardinality Linear Ordering Problem

Je voudrai bien vous signaler que le version préliminaire de l'article sera disponible online a partir de la semaine prochain.International audienceLinear Ordering Problem (LOP) has receive significant attention in different areas of application, ranging from archeology and scheduling to economics and even mathematical psychology. It is classified as a NP-hard problem. Assume a complete oriented graph on n vertices. A permutation of the elements of this finite set of vertices is a linear order (LO). Now let p be a fixed integer number less than or equal to n. p-Fixed Cardinality Linear Ordering Problem (p-FCLOP) is looking for a subset of vertices containing p nodes and a linear order on this subset of nodes.Graphically, there exists exactly one oriented arc between any pair of vertices in an LOP feasible solution, which is also a cycle free digraph and the objective is to maximize the sum of the weights of all the arcs present in the solution. In p-FCLOP, there exists a subset of vertices of which are selected to be active and exactly one oriented arc between any pair of active vertices. The objective is to find the best subset of nodes that maximize the sum of the weights of all the arcs in the solution. Graphically, a feasible solution is a complete cycle-free digraph on p vertices plus a set of n-p vertices not connected to any of the other vertices. There are several studies available in the literature focused on polyhedral aspects of linear ordering problem as well as various exact methods and heuristics.Linear ordering problem is already known as a NP-hard problem. However one sees that there exist many instances in the literature which CPLEX can solve them in less than 10 seconds for the case when p = n, but it runs out of memory once the cardinality number is limited to be less than n. In this study, we have focused on Lagrangian Relaxation to solve these difficult instances. We have studied different relaxation strategies and compared the dual bound obtained from each case to detect the most suitable one. Numerical results show that we could find very high quality dual bounds. We have also implemented a Lagrangian Decomposition decomposing the p-FCLOP model to three subproblems (instead of only two subproblem). The interest of decomposing the p-FCLOP model to three subproblems was mostly the nature of the three subproblems, which are relatively quite easy to solve compared to the initial p-FCLOP model. Numerical results show a significant improve in quality of dual bounds for several instances. We have also studied p-FCLOP polytope and identified some facet defining inequalities and introduced a relax-and-cut algorithm based on these results to solve instances of p-FCLOP. The numerical results were carried out using CPLEX 12.4 on an "Intel Core2 Quad CPU 2.50" machine.