Package org.ddolib.examples.mcp

package org.ddolib.examples.mcp

This package implements the acs, astar and ddo models for the Maximum Cut Problem (MCP). Given an undirected weighted graph 𝐺 = (𝑉,𝐸) in which the weight of the edge (𝑖,𝑗) ∈ 𝐸 is denoted 𝑤_{i,j} the MCP consists in finding a bi-partition (𝑆,𝑇) of the vertices of some given graph that maximizes the total weight of edges whose endpoints are in different partitions. This problem is considered in the papers:

• 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

Class	Description
Graph	Represents a Graph with adjacency matrix.
MCPAcsMain	Maximum Cut Problem (MCP) with Acs.
MCPAstarMain	Maximum Cut Problem (MCP) with AsTar.
MCPDdoMain	Main class for solving the Maximum Cut Problem (MCP) using a DDO (Decision Diagram Optimization) approach.
MCPFastLowerBound	Implementation of fast lower bound heuristic for the MCP.
MCPGenerator	Contains methods to generates and write instances.
MCPLnsMain	Entry point for solving the Maximum Cut Problem (MCP) using a Large Neighborhood Search (LNS) approach combined with Decision Diagram Optimization (DDO).
MCPProblem	Represents an instance of the Maximum Cut Problem (MCP).
MCPRanking	Class used to compare two states for the MCP problem.
MCPRelax	Implements a relaxation strategy for the Maximum Cut Problem (MCP).
MCPState	Class to contain data for the MCP state.
NaiveMCPSolver	Naive MCP solver which enumerates all the solution to find the best one.