Paper accepted for publication
The paper "A note on computational approaches for the antibandwidth problem" by M. Sinnl has been accepted for publication in Central European Journal of Operations Research. The journal is ranked C according to the VHB journal rankings.
The paper "A note on computational approaches for the antibandwidth problem" by M. Sinnla has been accepted for publication in Central European Journal of Operations Research. The journal is ranked C according to the VHB journal rankings.
a Johannes Kepler University Linz, Institute of Production and Logistics Management, Linz, Austria
In this note, we consider the antibandwidth problem, also known as dual bandwidthproblem, separation problem and maximum differential coloring problem. Given alabeled graph (i.e., a numbering of the vertices of a graph), the antibandwidth of anode is defined as the minimum absolute difference of its labeling to the labeling ofall its adjacent vertices. The goal in the antibandwidth problem is to find a labelingmaximizing the antibandwidth. The problem is NP-hard in general graphs and hasapplications in diverse areas like scheduling, radio frequency assignment, obnoxiousfacility location and map-coloring. There has been much work on deriving theoreticalbounds for the problem and also in the design of metaheuristics in recent years. How-ever, the optimality gaps between the best known solution values and reported upperbounds for the HarwellBoeing Matrix-instances, which are the commonly used bench-mark instances for this problem, are often very large (e.g., up to 577%). Moreover,only for three of these 24 instances, the optimal solution is known, leading the authorsof a state-of-the-art heuristic to conclude “HarwellBoeing instances are actually achallenge for modern heuristic methods”. The upper bounds reported in literature arebased on the theoretical bounds involving simple graph characteristics, i.e., size, orderand degree, and a mixed-integer programming (MIP) model. We present new MIPmodels for the problem, together with valid inequalities, and design a branch-and-cutalgorithm and an iterative solution algorithm based on them. These algorithms alsoinclude two starting heuristics and a primal heuristic. We also present a constraint programming approach, and calculate upper bounds based on the stability numberand chromatic number. Our computational study shows that the developed approachesallow to find the proven optimal solution for eight instances from literature, wherethe optimal solution was unknown and also provide reduced gaps for eleven addi-tional instances, including improved solution values for seven instances, the largestoptimality gap is now 46%.