LaplacianOpt Documentation

Overview

LaplacianOpt is a Julia package which implements polyhedral relaxation-based algorithms for the maximimum algebraic connectivity augmentation problem on weighted graph Laplacians. More specifically, given a weighted base graph with existing edges (could be empty), a set of candidate weighted edges for augmentation, and an augmentation budget (K), this package finds a set of K edges to augment to the base graph such that the resulting graph has maximum algebraic conenctivity with optimality guarantees. For example, given a base graph with N vertices and 0 edges, set of candidate edges which form a complete graph, and K = (N-1), this packages finds a spanning tree with maximum algebraic connectivity.

Algebraic connectivity is the second smallest eigenvalue of the graph Laplacian. The magnitude of this value reflects how well connected the overall graph is. This connectivity measure has been used in analyzing the robustness and synchronizability of complex networks, and in graph sparsification techniques.

Installation

To use LaplacianOpt, first download and install Julia. Note that the current version of LaplacianOpt is compatible with Julia 1.0 and later.

The latest stable release of LaplacianOpt can be installed using the Julia package manager with

import Pkg
Pkg.add("LaplacianOpt")

At least one mixed-integer programming solver is required for running LaplacianOpt. The well-known CPLEX or the Gurobi solver is highly recommended, as it is fast, scaleable and can be used to solve on fairly large-scale graphs. However, the open-source GLPK solver is also compatible with LaplacianOpt which can be installed via the package manager with

import Pkg
Pkg.add("GLPK")

Unit Tests

To run the tests in the package, run the following command after installing the LaplacianOpt package.

import Pkg
Pkg.test("LaplacianOpt")

Citing LaplacianOpt

If you find LaplacianOpt.jl useful in your work, we request you to cite the following papers [link-1] [link-2]:

@inproceedings{LOpt_ECC2015,
  title={On maximizing algebraic connectivity of networks for various engineering applications},
  author={Nagarajan, Harsha and Rathinam, Sivakumar and Darbha, Swaroop},
  booktitle={European Control Conference (ECC)},
  pages={1626--1632},
  year={2015},
  organization={IEEE}
}

@article{LOpt_arXiv2023,
  title={Optimal Robust Network Design: Formulations and Algorithms for Maximizing Algebraic Connectivity},
  author={Somisetty, Neelkamal and Nagarajan, Harsha and Darbha, Swaroop},
  journal={arXiv preprint:2304.08571},
  url = {https://arxiv.org/abs/2304.08571},
  year={2023}
}