Max-Cut Optimization

This program try to solve the max-cut problem using various approaches.
It is divided in two parts:

1. Graph handling
2. Solver and optimization

Build instruction

On system running Nix

1. Run nix-shell
2. And build: cargo build --release

On linux or WSL

1. Make sure that rust 2024 is installed
2. Make sure that pkg-config and fontconfig are installed on your machine, for debian based os: apt install pkg-config libfontconfig1-dev
3. run cargo build --release

On windows

1. Make sure that rust 2024 is installed
2. Simply run cargo build --release

How to use

CLI

Every options can be listed using --help at any level

Example commands

To plot one graph of each automorphism group of 7 nodes connected graph:

• ./max-cut-optimization draw -n 7

To solve the max cut problem on a graph of 18 nodes build from 3 graph of 6 nodes each.
It will also plot the graph with each cut for different optimization process.

• ./max-cut-optimization solve -n 18 -d 3

To solve the max cut problem on a graph of 18 nodes build from 3 graph of 6 nodes each, and runs it 10 times
It won't plot any graph but display average figures for different optimization process.

• ./max-cut-optimization solve -n 18 -d 3 -b 10