A computational comparison of compact MILP formulations for the zero forcing number

Agostinho Agra, Jorge Orestes Cerdeira, Cristina Requejo

Research output: Contribution to journalArticle

Abstract

Consider a graph where some of its vertices are colored. A colored vertex with a single uncolored neighbor forces that neighbor to become colored. A zero forcing set is a set of colored vertices that forces all vertices to become colored. The zero forcing number is the size of a minimum forcing set. Finding the minimum forcing set of a graph is NP-hard. We give a new compact mixed integer linear programming formulation (MILP) for this problem, and analyze this formulation and establish relation to an existing compact formulation and to two variants. In order to solve large size instances we propose a sequential search algorithm which can also be used as a heuristic to derive upper bounds for the zero forcing number. A computational study using Xpress (a MILP solver) is conducted to test the performances of the discussed compact formulations and the sequential search algorithm. We report results on cubic, Watts–Strogatz and randomly generated graphs with 10, 20 and 30 vertices.

Original languageEnglish
JournalDiscrete Applied Mathematics
DOIs
Publication statusPublished - 1 Jan 2019

Fingerprint

Zero-forcing
Mixed Integer Linear Programming
Linear programming
Formulation
Sequential Algorithm
Forcing
Search Algorithm
Graph in graph theory
NP-complete problem
Heuristics
Upper bound
Vertex of a graph

Keywords

  • Compact formulations
  • Graphs
  • Mixed integer linear programming
  • Valid inequalities
  • Zero forcing

Cite this

@article{5431bd1beadf484fa6d1b6698e8f7f1e,
title = "A computational comparison of compact MILP formulations for the zero forcing number",
abstract = "Consider a graph where some of its vertices are colored. A colored vertex with a single uncolored neighbor forces that neighbor to become colored. A zero forcing set is a set of colored vertices that forces all vertices to become colored. The zero forcing number is the size of a minimum forcing set. Finding the minimum forcing set of a graph is NP-hard. We give a new compact mixed integer linear programming formulation (MILP) for this problem, and analyze this formulation and establish relation to an existing compact formulation and to two variants. In order to solve large size instances we propose a sequential search algorithm which can also be used as a heuristic to derive upper bounds for the zero forcing number. A computational study using Xpress (a MILP solver) is conducted to test the performances of the discussed compact formulations and the sequential search algorithm. We report results on cubic, Watts–Strogatz and randomly generated graphs with 10, 20 and 30 vertices.",
keywords = "Compact formulations, Graphs, Mixed integer linear programming, Valid inequalities, Zero forcing",
author = "Agostinho Agra and Cerdeira, {Jorge Orestes} and Cristina Requejo",
year = "2019",
month = "1",
day = "1",
doi = "10.1016/j.dam.2019.03.027",
language = "English",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier Science B.V., Inc",

}

A computational comparison of compact MILP formulations for the zero forcing number. / Agra, Agostinho; Cerdeira, Jorge Orestes; Requejo, Cristina.

In: Discrete Applied Mathematics, 01.01.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A computational comparison of compact MILP formulations for the zero forcing number

AU - Agra, Agostinho

AU - Cerdeira, Jorge Orestes

AU - Requejo, Cristina

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Consider a graph where some of its vertices are colored. A colored vertex with a single uncolored neighbor forces that neighbor to become colored. A zero forcing set is a set of colored vertices that forces all vertices to become colored. The zero forcing number is the size of a minimum forcing set. Finding the minimum forcing set of a graph is NP-hard. We give a new compact mixed integer linear programming formulation (MILP) for this problem, and analyze this formulation and establish relation to an existing compact formulation and to two variants. In order to solve large size instances we propose a sequential search algorithm which can also be used as a heuristic to derive upper bounds for the zero forcing number. A computational study using Xpress (a MILP solver) is conducted to test the performances of the discussed compact formulations and the sequential search algorithm. We report results on cubic, Watts–Strogatz and randomly generated graphs with 10, 20 and 30 vertices.

AB - Consider a graph where some of its vertices are colored. A colored vertex with a single uncolored neighbor forces that neighbor to become colored. A zero forcing set is a set of colored vertices that forces all vertices to become colored. The zero forcing number is the size of a minimum forcing set. Finding the minimum forcing set of a graph is NP-hard. We give a new compact mixed integer linear programming formulation (MILP) for this problem, and analyze this formulation and establish relation to an existing compact formulation and to two variants. In order to solve large size instances we propose a sequential search algorithm which can also be used as a heuristic to derive upper bounds for the zero forcing number. A computational study using Xpress (a MILP solver) is conducted to test the performances of the discussed compact formulations and the sequential search algorithm. We report results on cubic, Watts–Strogatz and randomly generated graphs with 10, 20 and 30 vertices.

KW - Compact formulations

KW - Graphs

KW - Mixed integer linear programming

KW - Valid inequalities

KW - Zero forcing

UR - http://www.scopus.com/inward/record.url?scp=85064318649&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2019.03.027

DO - 10.1016/j.dam.2019.03.027

M3 - Article

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -