  


A new formulation for the Hamiltonian pmedian problem
Tolga Bektaş(t.bektassoton.ac.uk) Abstract: This paper concerns the Hamiltonian pmedian problem defined on a directed graph, which consists of finding p mutually disjoint circuits of minimum total cost, such that each node of the graph is included in one of the circuits. Earlier formulations are based on viewing the problem as resulting from the intersection of two subproblems. The first subproblem states that at most p circuits are required, that are usually modeled by using subtour elimination constraints known from the traveling salesman problem. The second subproblem states that at least p circuits are required, for which this paper makes an explicit connection to the socalled path elimination constraints that arise in multidepot/locationrouting problems. A new extended formulation is proposed that builds on this connection, that allows the derivation of a stronger set of subtour elimination constraints for the first subproblem, and implies a stronger set of path elimination constraints for the second subproblem. The paper describes separation routines for the two sets of constraints that are used in a branchandcut algorithm to solve asymmetric instances with up to 150 nodes and symmetric instances with up to 100 nodes using the new formulation. Keywords: Combinatorial optimization; Hamiltonian pmedian; multicut inequalities; multidepot routing; branchandcut algorithm. Category 1: Combinatorial Optimization (Branch and Cut Algorithms ) Category 2: Integer Programming ((Mixed) Integer Linear Programming ) Category 3: Applications  OR and Management Sciences (Transportation ) Citation: Working paper  CMAFCIO Download: [PDF] Entry Submitted: 03/06/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  