org.ddolibscala.example

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 andMichael Wooldridge. Springer, 2016.
• David Bergman et al. “Discrete Optimization with Decision Diagrams”.In: INFORMS Journal on Computing 28.1 (2016), pp. 47–66.

This package implements the acs, astar and ddo models for the Traveling Salesperson Problem with Time Window (TSPTW). The TSPTW (TSP with Time Windows) objective is to find the shortest possible route for a salesperson to visit a set of customers (or nodes) exactly once and return to the starting point, while respecting specified time windows for each customer.