Optimization Online


An exact algorithm for solving the ring star problem

Safia Kedad-Sidhoum(safia.kedad-sidhoum***at***lip6.fr)
Viet Hung Nguyen(Hung.Nguyen***at***lip6.fr)

Abstract: This paper deals with the ring star problem that consists in designing a ring that pass through a central depot, and then assigning each non visited customer to a node of the ring. The objective is to minimize the total routing and assignment costs. A new chain based formulation is proposed. Valid inequalities are proposed to strengthen the linear programming relaxation and are used as cutting planes in a branch-and-cut approach. A large set of instances are tested and show the effectiveness of the method that outperforms the results previously obtained on the problem.

Keywords: network design, polyhedral combinatorics, facets, mixed integer programming, branch-and-cut

Category 1: Applications -- OR and Management Sciences (Telecommunications )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Network Optimization

Citation: submitted

Download: [PDF]

Entry Submitted: 03/31/2008
Entry Accepted: 03/31/2008
Entry Last Modified: 03/31/2008

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 Programming Society