Optimization Online


Complexity and Exact Solution Approaches to the Minimum Changeover Cost Arborescence Problem

Stefano Gualandi (stefano.gualandi***at***unipv.it)
Giulia Galbiati (giulia.galbiati***at***unipv.it)
Emiliano Traversi (emiliano.traversi***at***math.tu-dortmund.de)
Frank Baumann (frank.baumann***at***math.tu-dortmund.de)

Abstract: We are given a digraph G = (N, A), where each arc is colored with one among k given colors. We look for a spanning arborescence T of G rooted at a given node and having minimum changeover cost. We call this the Minimum Changeover Cost Arborescence problem. To the authors’ knowledge, it is a new problem. The concept of changeover costs is similar to the one, already considered in the literature, of reload costs, but the latter depend also on the amount of commodity flowing in the arcs and through the nodes, whereas this is not the case for the changeover costs. Here, given any node j different from the root, if a is the color of the single arc entering node j in arborescence T , and b is the color of an arc (if any) leaving node j, then these two arcs contribute to the total changeover cost of T by the quantity dab, a non-negative entry of a k-dimensional square matrix D. We first prove that the problem is NPO-complete and very hard to approximate. Then we present a greedy heuristic together with combinatorial lower and upper bounds, a Binary Quadratic Programming formulation, and exact solution approaches based on branch-and-cut solvers. Finally, we report extensive computational results and exhibit a set of very challenging instances.

Keywords: network optimization, changeover cost, reload cost model, computational complexity,integer programming

Category 1: Combinatorial Optimization

Category 2: Integer Programming

Category 3: Network Optimization

Citation: Conference version of this paper, please cite: G. Galbiati, S. Gualandi, F. Maffioli. On Minimum Changeover Cost Arborescences. In Proc. of International Symposium on Experimental Algorithms (SEA), LNCS 6630, pp 112-123, 2011. DOI: 10.1007/978-3-642-20662-7_10

Download: [PDF]

Entry Submitted: 09/16/2011
Entry Accepted: 09/16/2011
Entry Last Modified: 09/23/2013

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