Generalized Independent Set

The Generalized Independent Set Problem (GISP) is a graph optimization problem proposed for forestry management [Hochbaum97,Colombi17]. The input consists of a graph, a subset of removable edges with a removal cost, and a revenue for each vertex. The goal is to select a set of vertices and remove a subset of the removable edges so as to maximize the total revenue of the selected vertices minus the total cost of the removed edges, such that the selected vertices are independent in the graph after edge removal.

Notation

• \(G=(V,E)\): undirected graph with vertex set \(V\) and edge set \(E\).
• \(E' \subseteq E\): the set of removable edges. In the generator, each edge of \(E\) is made removable independently with probability \(\alpha\) (the removal probability).
• \(r_v\): revenue of selecting vertex \(v\) (\(r_v = 100\) for all \(v\) in all distributions).
• \(c_e\): cost of removing edge \(e \in E'\) (\(c_e = 1\) for all \(e\) in all distributions).
• \(x_v \in \{0,1\}\): 1 if vertex \(v\) is selected.
• \(y_e \in \{0,1\}\): 1 if removable edge \(e\) is removed.

MILP formulation [Colombi17]

\begin{align} \max_{x,y} \quad & \sum_{v \in V} r_v\, x_v - \sum_{e \in E'} c_e\, y_e \\ \text{s.t.} \quad & x_u + x_v \leq 1 && \forall \{u,v\} \in E \setminus E' \\ & x_u + x_v - y_{uv} \leq 1 && \forall \{u,v\} \in E' \\ & x_v \in \{0,1\} && \forall v \in V \\ & y_e \in \{0,1\} && \forall e \in E' \end{align}

The instance files state the equivalent minimization problem \(\min \sum_{e \in E'} c_e y_e - \sum_{v \in V} r_v x_v\). An instance has \(|V| + |E'|\) binary variables and \(|E|\) constraints (one per edge). The Erdős–Rényi distributions draw \(G\) from \(G(n,p)\); the Ext hard distribution uses fixed graphs from the DIMACS 1993 clique benchmark, following [Khalil17].

@misc{huang2024distributional,
      title={Distributional MIPLIB: a Multi-Domain Library for Advancing ML-Guided MILP Methods}, 
      author={Weimin Huang and Taoan Huang and Aaron M Ferber and Bistra Dilkina},
      year={2024},
      eprint={2406.06954},
      archivePrefix={arXiv},
      primaryClass={cs.LG}
}

@article{hochbaum1997gisp,
  title={Forest harvesting and minimum cuts: a new approach to handling spatial constraints},
  author={Hochbaum, Dorit S and Pathria, Anu},
  journal={Forest Science},
  volume={43},
  number={4},
  pages={544--554},
  year={1997},
  publisher={Oxford University Press}
}

@article{colombi2017gisp2,
  title={The generalized independent set problem: Polyhedral analysis and solution approaches},
  author={Colombi, Marco and Mansini, Renata and Savelsbergh, Martin},
  journal={European Journal of Operational Research},
  volume={260},
  number={1},
  pages={41--55},
  year={2017},
  publisher={Elsevier}
}

@inproceedings{khalil2017primalheuristics,
  title={Learning to Run Heuristics in Tree Search.},
  author={Khalil, Elias B and Dilkina, Bistra and Nemhauser, George L and Ahmed, Shabbir and Shao, Yufen},
  booktitle={Proceedings of the 26th International Joint Conference on Artificial Intelligence},
  pages={659--666},
  year={2017}
}

@inproceedings{ferber2022backdoors,
  title={Learning Pseudo-Backdoors for Mixed Integer Programs},
  author={Ferber, Aaron and Song, Jialin and Dilkina, Bistra and Yue, Yisong},
  booktitle={Integration of Constraint Programming, Artificial Intelligence, and Operations Research},
  pages={91--102},
  year={2022},
  organization={Springer}
}