Optimizing the two-dimensional bandwidth problem under the maximum norm using exact and heuristic approaches

Abstract

This paper addresses the Two-dimensional Bandwidth Minimization Problem (2D-BMP) using the $L_\infty$-norm distance, focusing on embedding a guest graph into a grid-like host graph to minimize the maximum edge distance. While previous research has emphasized theoretical aspects and regular graphs, practical methods for complex graphs remain underexplored. Solving 2D-BMP is crucial for applications such as VLSI design, network simulation, and scheduling, though its NP-hard nature poses significant challenges. We propose three exact Constraint Satisfaction Problem (CSP) models—arithmetic, finite domain, and dichotomic optimization to efficiently solve the 2D-BMP. Additionally, we introduce the Convergence-Based Multi-start Algorithm (CBMA), a heuristic combining greedy construction and local search for approximate solutions. Our CSP exact methods found optimal solutions for 70 small benchmark instances from diverse standard graph topologies, including 21 previously unknown. On the other hand, the CBMA achieved new upper bounds, expending moderate computational times, for 113 graphs extracted from the Harwell-Boeing Sparse Matrix Collection which present larger and more complex structures.

Authors

• Sergio Cavero Díaz¹

• Eduardo G. Pardo¹ *

• Eduardo Rodriguez-Tello²

• Eric Monfroy³

• Claudia Vasconcellos-Gaete³

Affiliations

1. Departamento de Informática y Estadística, Universidad Rey Juan Carlos — C. Tulipán, s/n, Móstoles, 28933, Madrid, Spain

2. Cinvestav, Unidad Tamaulipas — Km. 5.5 Carretera Victoria - Soto La Marina, Victoria, 87130, Tamaulipas, Mexico

3. LERIA, Université d'Angers — 2 Bd de Lavoisier, Angers, 49000, France

*Corresponding author.

Datasets

Instances are categorized in different datasets inside the instances folder. All instances are either from the https://archive.ics.uci.edu/ml/index.php, the Harwell-Boeing Sparse Matrix Collection, or generated based on graph families described in the paper.

Instance format

Each instance is encoded as a plain text file representing a graph:

• The first line contains the number of vertices n and edges m.
• Each subsequent line contains a pair of integers u v representing an edge between vertex u and vertex v.
• Vertices are indexed from 0 to n-1.

Example:

10 15
0 1
0 2
1 3
...

Methods

CSP

Execution of the CSP algorithm specifying the path to the instances directory. Note that you need to have pycsp3 installed.

python3 matrix_bandwidth.py -k=<K> -data=<instance> -dataparser=mtx_parser.py

Or specifying bounds:

python3 matrix_bandwidth.py -lb=<LB> -ub=<UB> -data=<instance> -dataparser=mtx_parser.py

CBMA

Execution of the CBMA algorithm specifying the path to the instances directory:

java -jar CBMA.jar --instances.path.default=<path_to_instances_directory>

MA (Unified)

Execution of the MA algorithm specifying the path to the instances directory:

java -jar MATDBMP.jar <path_to_instances_directory>

DRSA

Once generated in DRSA.jar, you can execute it highlighting standard Java syntax. Main.java accepts up to 4 optional arguments:

java -jar DRSA.jar [instances_path] [num_runs] [seed] [max_time_seconds]

Example: Run 5 times per instance, with seed 42, and a maximum time of 3600 seconds (1 hour).

java -jar target/DRSA.jar instances/prelim2 5 42 3600

MDO

Pre-requisites

1. Python 3.10+
2. PyCSP3

   sudo pip3 install pycsp3
   sudo apt-get install openjdk-11-jdk

   or

   sudo pip3 install --upgrade pycsp3

Running the code

```bash
python3 matrix_bandwidth.py -lb=<lower> -ub=<upper> -data=<instance> -parser=mtx_parser.py
```

Cite

Consider citing our paper if used in your own work:

DOI

https://doi.org/XXXXXXX

Bibtex

@article{cavero2025heuristic,
  title={Heuristic and Exact Approaches for the Two-Dimensional Bandwidth Problem},
  author={Cavero, Sergio and Pardo, Eduardo G. and Rodriguez-Tello, Eduardo and Monfroy, Eric and Vasconcellos-Gaete, Claudia},
  journal={XXXXXX},
  year={202X},
  doi={XXXXXXX}
}

Powered by MORK (Metaheuristic Optimization framewoRK)

	Mork is a Java framework for easily solving hard optimization problems. You can create a project and try the framework in under one minute. See the documentation or the source code.