CORMSIS Seminar - Fixed cardinality linear ordering problem, polyhedral study and solution methods Event

Event details

Linear Ordering Problem (LOP) has receive significant attention in different areas of application, and 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. Now let p be a fixed integer number less than or equal to n. Fixed Cardinality Linear Ordering Problem (FCLOP) 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 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 this subset. Then the objective is to find a subset of nodes, which maximizes the sum over the weights of all the arcs, between the nodes in this set. Evidently, an arc may appear only if both its end points are selected to be active. The FCLOP problem is introduced for the first time in this PhD study. A mathematical model is proposed for this problem and then several valid inequalities are introduced to improve the polyhedral description of the proposed model. We studied the polytope corresponds to the model, identified dimension of the polytope for different cardinality numbers and then proved that among the newly proposed valid inequalities, some valid inequalities are facet-defining inequalities. In addition, some non-valid inequalities are introduced to destruct the symmetry structure inherent in the problem. In terms of solution method, different relaxation strategies were studied to analyse properties of different sub-problems and compare dual bounds obtained from different Lagrangian relaxation algorithms. In addition, a Lagrangian decomposition algorithm is implied to solve the problem. A pure relaxation algorithm inspired from combinatorial Benders decomposition technique is also proposed to solve the problem. Finally, a relax-and-cut algorithm is implied to solve instances of the problem. Since to the best of our knowledge, there exist no other study on this subject in the literature, different proposed solution algorithms were all tested on the instances of linear ordering problem, available in the LOLIB online library and quality of obtained solutions and time needed to solve instances were compared to CPLEX.