  In this note, we consider the antibandwidth problem, also known as dual
bandwidth problem, separation problem and maximum differential coloring
problem. Given a labeled graph (i.e., a numbering of the vertices of a graph),
the antibandwidth of a node is defined as the minimum absolute difference of
its labeling to the labeling of all its adjacent vertices. The goal in the
antibandwidth problem is to find a labeling maximizing the antibandwidth. The
problem is NP-hard in general graphs and has applications in diverse areas like
scheduling, radio frequency assignment, obnoxious facility location and
map-coloring. There has been much work on deriving theoretical bounds for the
problem and also in the design of metaheuristics in recent years. However, the
optimality gaps between the best known solution values and reported upper
bounds for the HarwellBoeing Matrix-instances, which are the commonly used
benchmark instances for this problem, are often very large (e.g., up to 577%).
The upper bounds reported in literature are based on the theoretical bounds
involving simple graph characteristics, i.e., size, order and degree, and a
mixed-integer programming (MIP) model. We present new MIP models for the
problem, together with valid inequalities, and design a branch-and-cut
algorithm and an iterative solution algorithm based on them. These algorithms
also include two starting heuristics and a primal heuristic. We also present a
constraint programming approach, and calculate upper bounds based on the
stability number and chromatic number. Our computational study shows that the
developed approaches allow to find the proven optimal solution for eight
instances from literature, where the optimal solution was unknown and also
provide reduced gaps for eleven additional instances, including improved
solution values for seven instances, the largest optimality gap is now 46%.
