Optimization Online


A new formulation for the Hamiltonian p-median problem

Tolga Bektaş(t.bektas***at***soton.ac.uk)
Luís Gouveia(legouveia***at***fc.ul.pt)
Daniel Santos(drsantos***at***fc.ul.pt)

Abstract: This paper concerns the Hamiltonian p-median 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 so-called path elimination constraints that arise in multi-depot/location-routing 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 branch-and-cut 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 p-median; multi-cut inequalities; multi-depot routing; branch-and-cut 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
Entry Accepted: 03/06/2018
Entry Last Modified: 03/06/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society