Skip to main navigationSkip to main content
The University of Southampton
CORMSIS Centre for Operational Research, Management Sciences and Information Systems

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

16:00 - 17:00
23 June 2016
Room 3041 Building 2, Southampton Business School

For more information regarding this event, please email Dr Yuan Huang at .

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.

Speaker information

Dr. Rahimeh Neamatian Monemi,Southampton Business School ,Bio: DR. Rahimeh Neamatian Monemi has joined the University of Southampton, as a research fellow on January 2016. She has done her PhD at the LIMOS research laboratory, in Blaise Pascal University, Clermont-Ferrand, France. During her PhD, she was working on the fixed cardinality linear ordering problem. Before doing her PhD, she has done her master on Optimisation in Iran, Chamran University of Ahvaz. Then as a research assistant, she joined the Centre for Maritime Studies of the National University of Singapore. In this period, she was working on simulation of a port operation in a container terminal. In particular, she was analysing the impact of mega vessels on efficiency of operations in a container terminal. She has started her PhD in October 2009. After her graduation, she has worked as an assistant professor at Artois University in Bethune, France for one year. Then, she has started working as a postdoctoral researcher at IFSTTAR (The French institute of science and technology for transport, spatial planning, development and networks) in Villeneuve d’Ascq, France. In this period, she was working on train scheduling problem under uncertainty.

Privacy Settings