A note on computational approaches for the antibandwidth problem

被引:4
|
作者
Sinnl, Markus [1 ,2 ]
机构
[1] Univ Vienna, Fac Business, Dept Stat & Operat Res Econ & Stat, Vienna, Austria
[2] Johannes Kepler Univ Linz, Inst Prod & Logist Management, Linz, Austria
关键词
Graph labeling; Integer programming; Constraint programming; Clique problem; Bandwidth; ALGORITHM; SEARCH; GRAPHS;
D O I
10.1007/s10100-020-00688-4
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
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%). Moreover, only for three of these 24 instances, the optimal solution is known, leading the authors of a state-of-the-art heuristic to conclude "HarwellBoeing instances are actually a challenge for modern heuristic methods". 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%.
引用
收藏
页码:1057 / 1077
页数:21
相关论文
共 50 条
  • [1] A note on computational approaches for the antibandwidth problem
    Markus Sinnl
    Central European Journal of Operations Research, 2021, 29 : 1057 - 1077
  • [2] Antibandwidth problem for itchy caterpillars
    Rahaman, Md. Sazzadur
    Eshan, Tousif Ahmed
    Al Abdullah, Sad
    Rahman, Md. Saidur
    2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014, 2014,
  • [3] Antibandwidth Problem for Itchy Caterpillars
    Rahaman, Md Sazzadur
    Eshan, Tousif Ahmed
    Al Abdullah, Sad
    Rahman, Md Saidur
    2014 INTERNATIONAL CONFERENCE ON INFORMATICS, ELECTRONICS & VISION (ICIEV), 2014,
  • [4] Memetic algorithm for the antibandwidth maximization problem
    Richa Bansal
    Kamal Srivastava
    Journal of Heuristics, 2011, 17 : 39 - 60
  • [5] A hybrid metaheuristic for the cyclic antibandwidth problem
    Lozano, Manuel
    Duarte, Abraham
    Gortazar, Francisco
    Marti, Rafael
    KNOWLEDGE-BASED SYSTEMS, 2013, 54 : 103 - 113
  • [6] Memetic algorithm for the antibandwidth maximization problem
    Bansal, Richa
    Srivastava, Kamal
    JOURNAL OF HEURISTICS, 2011, 17 (01) : 39 - 60
  • [7] A memetic algorithm for the cyclic antibandwidth maximization problem
    Bansal, Richa
    Srivastava, Kamal
    SOFT COMPUTING, 2011, 15 (02) : 397 - 412
  • [8] Computational Approaches to the Pragmatics Problem
    Cummins, Chris
    de Ruiter, Jan P.
    LANGUAGE AND LINGUISTICS COMPASS, 2014, 8 (04): : 133 - 143
  • [9] GRASP with Path Relinking Heuristics for the Antibandwidth Problem
    Duarte, A.
    Marti, R.
    Resende, M. G. C.
    Silva, R. M. A.
    NETWORKS, 2011, 58 (03) : 171 - 189
  • [10] Constraint Optimization Production Planning Problem. A Note on Theory, Selected Approaches and Computational Experiments
    Adrian, Weronika T.
    Leone, Nicola
    Ligeza, Antoni
    Manna, Marco
    Slazynski, Mateusz
    ARTIFICIAL INTELLIGENCE AND SOFT COMPUTING, PT II (ICAISC 2015), 2015, 9120 : 541 - 553