Package org.ddolib.examples.misp

package org.ddolib.examples.misp

This package implements the acs, astar and ddo models for the Maximum Independent Set Problem (MISP). Given a weighted graph 𝐺 = (𝑉,𝐸,𝑤) where 𝑉= {1,...,𝑛} is a set of vertices, 𝐸 \subset 𝑉 ×𝑉 the set of edges connecting those vertices and 𝑤 = {𝑤1,𝑤2,...,𝑤𝑛} is a set of weights s.t. 𝑤𝑖 is the weight of node 𝑖. The problem consists in finding a subset of vertices in a graph such that no edge exists in the graph that connects two of the selected nodes and the sum of the weight of the selected nodes is maximal.

• David Bergman et al. Decision Diagrams for Optimization. Ed. by Barry O’Sullivan and Michael Wooldridge. Springer, 2016.
• David Bergman et al. “Discrete Optimization with Decision Diagrams”. In: INFORMS Journal on Computing 28.1 (2016), pp. 47–66.

Related Packages

Package	Description
org.ddolib.examples	Package containing examples

Classes

Class	Description
MispAcsMain	The Maximum Independent Set Problem (MISP) with Acs.
MispAstarMain	The Maximum Independent Set Problem (MISP) with AsTar.
MispAwAstarMain	The Maximum Independent Set Problem (MISP) with Anytime Weighted A* (AWA*).
MispDdoMain	The Maximum Independent Set Problem (MISP) with Ddo.
MispDominance	Implementation of a dominance relation for the Maximum Independent Set Problem (MISP).
MispFastLowerBound	Computes a fast lower bound for the Maximum Independent Set Problem (MISP).
MispGenerator	Contains methods to generate instances of the MISP.
MispLnsMain	Entry point for solving the Maximum Independent Set Problem (MISP) using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).
MispProblem	Represents an instance of the Maximum Independent Set Problem (MISP) as a Problem.
MispRanking	Implements a ranking strategy for states in the Maximum Independent Set Problem (MISP).
MispRelax	Implements a relaxation strategy for the Maximum Independent Set Problem (MISP) to be used in decision diagram optimization (DDO) algorithms.