Max Cut¶

Principles learned¶

  • Create a generic model that uses data

  • Use of comparison operators outside a constraint

Problem¶

../_images/maxcut.svg

Given a graph G=(V,E), a cut is a partition of V into two subsets S and V-S. The size of a cut is the number of edges with one extremity in S and the other in V-S. The MAX CUT problem is to find a cut with a size larger or equal to the size of any other cut.

Download the example


Data¶

Each data file contains:

  • the number of vertices

  • the number of edges

  • the adjacency list with the edge weights

The instances are from the Biq Mac Library. Optimal solutions and description of each dataset can be found here.

Program¶

The decisions variables are binaries x[i], equal to 1 if the vertex i is in the subset S, 0 if it is in V-S. Each edge is described by its origin and destination. An edge e is in the cut if x[origin[e]] != x[dest[e]]. The objective is to maximize the total weight of the edges in the cut.

Execution:
hexaly maxcut.hxm inFileName=instances/g05_60.0 [hxTimeLimit=] [solFileName=]
use io;

/* Read instance data */
function input() {
    local usage = "Usage: hexaly maxcut.hxm "
            + "inFileName=inputFile [solFileName=outputFile] [hxTimeLimit=timeLimit]";

    if (inFileName == nil) throw usage;

    local inFile = io.openRead(inFileName);
    n = inFile.readInt();
    m = inFile.readInt();

    for [e in 1..m] {
        origin[e] = inFile.readInt();
        dest[e] = inFile.readInt();
        w[e] = inFile.readInt();
    }
}

/* Declare the optimization model */
function model() {
    // Decision variables x[i]
    // True if vertex x[i] is on the right side of the cut
    // and false if it is on the left side of the cut
    x[i in 1..n] <- bool();

    // An edge is in the cut-set if it has an extremity in each class of the bipartition
    incut[e in 1..m] <- x[origin[e]] != x[dest[e]];

    // Size of the cut
    cutWeight <- sum[e in 1..m](w[e] * incut[e]);
    maximize cutWeight;
}

/* Parametrize the solver */
function param() {
    if (hxTimeLimit == nil) hxTimeLimit = 10;
}

/* Write the solution in a file with the following format: 
 *  - objective value
 *  - each line contains a vertex number and its subset (1 for S, 0 for V-S) */
function output() {
    if (solFileName == nil) return;
    println("Write solution into file '" + solFileName + "'");
    local solFile = io.openWrite(solFileName);
    solFile.println(cutWeight.value);
    for [i in 1..n]
        solFile.println(i, " ", x[i].value);
}
Execution (Windows)
set PYTHONPATH=%HX_HOME%\bin\python
python maxcut.py instances\g05_60.0
Execution (Linux)
export PYTHONPATH=/opt/hexaly_13_0/bin/python
python maxcut.py instances/g05_60.0
import hexaly.optimizer
import sys

def read_integers(filename):
    with open(filename) as f:
        return [int(elem) for elem in f.read().split()]

#
# Read instance data
#
def read_instance(filename):
    file_it = iter(read_integers(filename))
    # Number of vertices
    n = next(file_it)
    # Number of edges
    m = next(file_it)

    # Origin of each edge
    origin = [None] * m
    # Destination of each edge
    dest = [None] * m
    # Weight of each edge
    w = [None] * m

    for e in range(m):
        origin[e] = next(file_it)
        dest[e] = next(file_it)
        w[e] = next(file_it)
    
    return n, m, origin, dest, w

def main(instance_file, output_file, time_limit):
    n, m, origin, dest, w = read_instance(instance_file)

    with hexaly.optimizer.HexalyOptimizer() as optimizer:
        #
        # Declare the optimization model
        #
        model = optimizer.model

        # Decision variables x[i]
        # True if vertex x[i] is on the right side of the cut
        # and false if it is on the left side of the cut
        x = [model.bool() for i in range(n)]

        # An edge is in the cut-set if it has an extremity in each class of the bipartition
        incut = [None] * m
        for e in range(m):
            incut[e] = model.neq(x[origin[e] - 1], x[dest[e] - 1])

        # Size of the cut
        cut_weight = model.sum(w[e] * incut[e] for e in range(m))
        model.maximize(cut_weight)

        model.close()

        # Parameterize the optimizer
        optimizer.param.time_limit = time_limit

        optimizer.solve()

        #
        # Write the solution in a file with the following format:
        #  - objective value
        #  - each line contains a vertex number and its subset (1 for S, 0 for V-S)
        #
        if output_file != None:
            with open(output_file, 'w') as f:
                f.write("%d\n" % cut_weight.value)
                # Note: in the instances the indices start at 1
                for i in range(n):
                    f.write("%d %d\n" % (i + 1, x[i].value))

if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Usage: python maxcut.py inputFile [outputFile] [timeLimit]")
        sys.exit(1)

    instance_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 10
    main(instance_file, output_file, time_limit)
Compilation / Execution (Windows)
cl /EHsc maxcut.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly130.lib
maxcut instances\g05_60.0
Compilation / Execution (Linux)
g++ maxcut.cpp -I/opt/hexaly_13_0/include -lhexaly130 -lpthread -o maxcut
./maxcut instances/g05_60.0
#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace hexaly;
using namespace std;

class Maxcut {
public:
    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Number of vertices
    int n;

    // Number of edges
    int m;

    // Origin of each edge
    vector<int> origin;

    // Destination of each edge
    vector<int> dest;

    // Weight of each edge
    vector<int> w;

    // True if vertex x[i] is on the right side of the cut
    // and false if it is on the left side of the cut
    vector<HxExpression> x;

    // Objective
    HxExpression cutWeight;

    /* Read instance data */
    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> n;
        infile >> m;

        origin.resize(m);
        dest.resize(m);
        w.resize(m);

        for (int e = 0; e < m; ++e) {
            infile >> origin[e];
            infile >> dest[e];
            infile >> w[e];
        }
    }

    void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // Decision variables x[i]
        x.resize(n);
        for (int i = 0; i < n; ++i) {
            x[i] = model.boolVar();
        }

        // An edge is in the cut-set if it has an extremity in each class of the bipartition
        // Note: the indices start at 1 in the instances
        vector<HxExpression> incut(m);
        for (int e = 0; e < m; ++e) {
            incut[e] = model.neq(x[origin[e] - 1], x[dest[e] - 1]);
        }

        // Size of the cut
        cutWeight = model.sum();
        for (int e = 0; e < m; ++e) {
            cutWeight.addOperand(w[e] * incut[e]);
        }

        model.maximize(cutWeight);
        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(limit);
        optimizer.solve();
    }

    /* Write the solution in a file with the following format:
     *  - objective value
     *  - each line contains a vertex number and its subset (1 for S, 0 for V-S) */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());

        outfile << cutWeight.getValue() << endl;
        for (unsigned int i = 0; i < n; ++i)
            outfile << i + 1 << " " << x[i].getValue() << endl;
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: maxcut inputFile [outputFile] [timeLimit] " << endl;
        return 1;
    }

    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "10";

    try {
        Maxcut model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const exception& e) {
        cerr << "An error occurred: " << e.what() << endl;
        return 1;
    }
}
Compilation / Execution (Windows)
copy %HX_HOME%\bin\Hexaly.NET.dll .
csc Maxcut.cs /reference:Hexaly.NET.dll
Maxcut instances\g05_60.0
using System;
using System.IO;
using Hexaly.Optimizer;

public class Maxcut : IDisposable
{
    // Number of vertices
    int n;

    // Number of edges
    int m;

    // Origin of each edge
    int[] origin;

    // Destination of each edge
    int[] dest;

    // Weight of each edge
    int[] w;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // True if vertex x[i] is on the right side of the cut
    // and false if it is on the left side of the cut
    HxExpression[] x;

    // Objective
    HxExpression cutWeight;

    public Maxcut()
    {
        optimizer = new HexalyOptimizer();
    }

    /* Read instance data */
    public void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            var tokens = input.ReadLine().Split(' ');
            n = int.Parse(tokens[0]);
            m = int.Parse(tokens[1]);

            origin = new int[m];
            dest = new int[m];
            w = new int[m];

            for (int e = 0; e < m; ++e)
            {
                tokens = input.ReadLine().Split(' ');
                origin[e] = int.Parse(tokens[0]);
                dest[e] = int.Parse(tokens[1]);
                w[e] = int.Parse(tokens[2]);
            }
        }
    }

    public void Dispose()
    {
        if (optimizer != null)
            optimizer.Dispose();
    }

    public void Solve(int limit)
    {
        // Declare the optimization model
        HxModel model = optimizer.GetModel();

        // Decision variables x[i]
        x = new HxExpression[n];
        for (int i = 0; i < n; ++i)
            x[i] = model.Bool();

        // An edge is in the cut-set if it has an extremity in each class of the bipartition
        // Note: the indices start at 1 in the instances
        HxExpression[] incut = new HxExpression[m];
        for (int e = 0; e < m; ++e)
            incut[e] = model.Neq(x[origin[e] - 1], x[dest[e] - 1]);

        // Size of the cut
        cutWeight = model.Sum();
        for (int e = 0; e < m; ++e)
            cutWeight.AddOperand(w[e] * incut[e]);
        model.Maximize(cutWeight);

        model.Close();

        // Parametrize the optimizer
        optimizer.GetParam().SetTimeLimit(limit);
        optimizer.Solve();
    }

    /* Write the solution in a file with the following format:
     *  - objective value
     *  - each line contains a vertex number and its subset (1 for S, 0 for V-S) */
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(cutWeight.GetValue());
            for (int i = 0; i < n; ++i)
                output.WriteLine((i + 1) + " " + x[i].GetValue());
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: Maxcut inputFile [solFile] [timeLimit]");
            Environment.Exit(1);
        }
        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "10";

        using (Maxcut model = new Maxcut())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac Maxcut.java -cp %HX_HOME%\bin\hexaly.jar
java -cp %HX_HOME%\bin\hexaly.jar;. Maxcut instances\g05_60.0
Compilation / Execution (Linux)
javac Maxcut.java -cp /opt/hexaly_13_0/bin/hexaly.jar
java -cp /opt/hexaly_13_0/bin/hexaly.jar:. Maxcut instances/g05_60.0
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class Maxcut {
    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Number of vertices
    private int n;

    // Number of edges
    private int m;

    // Origin of each edge
    private int[] origin;

    // Destination of each edge
    private int[] dest;

    // Weight of each edge
    private int[] w;

    // True if vertex x[i] is on the right side of the cut
    // and false if it is on the left side of the cut
    private HxExpression[] x;

    // Objective
    private HxExpression cutWeight;

    private Maxcut(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            n = input.nextInt();
            m = input.nextInt();

            origin = new int[m];
            dest = new int[m];
            w = new int[m];
            for (int e = 0; e < m; ++e) {
                origin[e] = input.nextInt();
                dest[e] = input.nextInt();
                w[e] = input.nextInt();
            }
        }
    }

    private void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // Decision variables x[i]
        x = new HxExpression[n];
        for (int i = 0; i < n; ++i) {
            x[i] = model.boolVar();
        }

        // An edge is in the cut-set if it has an extremity in each class of the bipartition
        // Note: the indices start at 1 in the instances
        HxExpression[] incut = new HxExpression[m];
        for (int e = 0; e < m; ++e) {
            incut[e] = model.neq(x[origin[e] - 1], x[dest[e] - 1]);
        }

        // Size of the cut
        cutWeight = model.sum();
        for (int e = 0; e < m; ++e) {
            cutWeight.addOperand(model.prod(w[e], incut[e]));
        }
        model.maximize(cutWeight);

        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(limit);
        optimizer.solve();
    }

    /* Write the solution in a file with the following format:
     * - objective value
     * - each line contains a vertex number and its subset (1 for S, 0 for V-S) */
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            output.println(cutWeight.getValue());
            for (int i = 0; i < n; ++i) {
                output.println((i + 1) + " " + x[i].getValue());
            }
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java Maxcut inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "10";

        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            Maxcut model = new Maxcut(optimizer);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}