An exact algorithm for solving the ring star problem

Safia Kedad-Sidhoum(safia.kedad-sidhoumlip6.fr)
Viet Hung Nguyen(Hung.Nguyenlip6.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