Laboratoire de Génie Informatique et d’Automatique de l’Artois


Fixed Cardinaliry Linear Ordering Problem : Polyhedral and algorithmic

The 21 May 2013 at 14:00 Seminars room of the LGI2A, FSA, Béthune
Rahimeh NEAMATIAN MONEMI Ph.D. student ISIMA / LIMOS - Clermont-Ferrand

Linear Ordering Problem (LOP) has received significant attention in different areas of application, ranging from archaeology 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 ordering (LO). Now let p be a fixed integer number less than or equal to n. Fixed Cardinality Linear Ordering Problem is looking for a subset of vertices containing p nodes and a linear order on this subset of nodes.
Graphically, there exist exactly one oriented arc between any pair of vertices in an LOP feasible solution, which is also a cycle free digraph and objective is to maximize the sum over the weights of all the arcs presented in the solution. In FCLOP, there exist a subset of vertices of which are active and there exist exactly one oriented arc between any pair of vertices belonging to it. Then the objective is to find the best subset of nodes which maximize the sum over the weights of all the arcs existed in the solution. Graphically a feasible solution is a complete cycle free digraph on p vertices plus a set of n − p vertices having no contact with any of the other vertices.
From theoretical point of view we have studied the polytope associated to the model. We have introduced some valid and not valid inequalities for strengthening the formulation. Also we have determined the minimal system of equations for different cases of the problem (with respect to the cardinality number) and obtained dimension of the polytope for different cases. We have introduced a set of facet defining inequalities. Also we have presented a set of dynamic symmetry breaking inequalities that are not valid with respect to the FCLOP polytope, to reduce the level of symmetry inherently presents in the model. In computational aspect, we have tried Lagrangian relaxation method to solve the model. Also Lagrangian decomposition aspect is implemented to solve the problem. In this work, we have decomposed the model to three sub-problems. We have also applied Bundle method to improve the dual bound. We have done some heuristics to discover primal bound alongside. We have implemented a benders decomposition to avoid having a large number of useless triangle-free inequalities. Also we have introduced a Semi-definite relaxation model. The numerical results are all done using CPLEX 12.4 on an”Intel Core2 Quad CPU 2.50” machine.