Max cut

Principles learned

  • Create a generic model that uses data
  • Use of comparison operators outside a constraint

Problem

../_images/maxcut.png

Given a graph G=(V,E), a cut is a partition of V into two subset 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 weight

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:
localsolver maxcut.lsp inFileName=instancesg05_60.0 [lsTimeLimit=] [solFileName=]
/********** maxcut.lsp **********/

use io;

/* Reads instance data. */
function input() {
    local usage = "Usage: localsolver maxcut.lsp "
        + "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=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();
    }
}

/* Declares the optimization model. */
function model() {
    // x[i] is 1 if vertex i is in the subset S, 0 if it is in V-S
    x[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]];
    cutWeight <- sum[e in 1..m] (w[e]* incut[e]);
    maximize cutWeight;
}

/* Parameterizes the solver. */
function param() {
    if(lsTimeLimit == nil) lsTimeLimit = 10;
}

/* Writes the solution in a file following 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=%LS_HOME%\bin\python27\
python maxcut.py instancesg05_60.0
Execution (Linux)
export PYTHONPATH=/opt/localsolver_XXX/bin/python27/
python maxcut.py instancesg05_60.0
########## maxcut.py ##########

import localsolver
import sys

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


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


with localsolver.LocalSolver() as ls:

    #
    # Reads instance data
    #

    file_it = iter(read_integers(sys.argv[1]))
    # Number of vertices
    n = file_it.next()
    # Number of edges
    m = file_it.next()

    # 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] = file_it.next()
        dest[e] = file_it.next()
        w[e] = file_it.next()

    #
    # Declares the optimization model
    #
    model = ls.model

    # Decision variables x[i]
    # Is 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)]

    # incut[e] is true if its endpoints are in different class of the partition
    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()

    #
    # Param
    #
    ls.param.nb_threads = 2
    if len(sys.argv) >= 4: ls.create_phase().time_limit = int(sys.argv[3])
    else: ls.create_phase().time_limit = 10

    ls.solve()

    #
    # Writes the solution in a file following the following format: 
    #  - objective value
    #  - each line contains a vertex number and its subset (1 for S, 0 for V-S)
    #
    if len(sys.argv) >= 3:
        with open(sys.argv[2], '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))
Compilation / Execution (Windows)
cl /EHsc maxcut.cpp -I%LS_HOME%\include /link %LS_HOME%\bin\localsolver.dll.lib
maxcut instancesg05_60.0
Compilation / Execution (Linux)
g++ maxcut.cpp -I/opt/localsolver_XXX/include -llocalsolver -lpthread -o maxcut
./maxcut instancesg05_60.0
//********* maxcut.cpp *********

#include <iostream>
#include <fstream>
#include <vector>
#include "localsolver.h"

using namespace localsolver;
using namespace std;

class Maxcut {
public:
    // LocalSolver 
    LocalSolver localsolver;

    // 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<lsint> w;

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

    // Objective 
    LSExpression cutWeight;

    // Reads 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){
        // Declares the optimization model. 
        LSModel model = localsolver.getModel();

        // Decision variables x[i]
        x.resize(n);
        for(int i = 0; i < n; i++) {
            x[i] = model.boolVar();
        }
        
        // incut[e] is true if its endpoints are in different class of the partition
        vector<LSExpression> 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 += w[e]*incut[e];
        }

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

        // Parameterizes the solver. 
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(limit);
        localsolver.solve();
    }

    // Writes the solution in a file following 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;
        // Note: in the instances the indices start at 1
        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 << "Error occurred: " << e.what() << endl;
        return 1;
    }
}
Compilation/Execution (Windows)
copy %LS_HOME%\bin\*net.dll .
csc Maxcut.cs /reference:localsolvernet.dll
Maxcut instancesg05_60.0
/********** Maxcut.cs **********/

using System;
using System.IO;
using localsolver;

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;

    // Solver
    LocalSolver localsolver;

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

    // Objective
    LSExpression cutWeight;

    public Maxcut()
    {
        localsolver = new LocalSolver();
    }


    // Reads 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 (localsolver != null)
            localsolver.Dispose();
    }

    public void Solve(int limit)
    {
        // Declares the optimization model.
        LSModel model = localsolver.GetModel();

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

        // incut[e] is true if its endpoints are in different class of the partition
        // Note: the indices start at 1 in the instances
        LSExpression[] incut = new LSExpression[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();

        // Parameterizes the solver.
        LSPhase phase = localsolver.CreatePhase();
        phase.SetTimeLimit(limit);
        localsolver.Solve();

    }

    // Writes the solution in a file following 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";

        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 %LS_HOME%\bin\localsolver.jar
java -cp %LS_HOME%\bin\localsolver.jar;. Maxcut instancesg05_60.0
Compilation/Execution (Linux)
javac Maxcut.java -cp /opt/localsolver_XXX/bin/localsolver.jar
java -cp /opt/localsolver_XXX/bin/localsolver.jar:. Maxcut instancesg05_60.0
/********** Maxcut.java **********/

import java.util.*;
import java.io.*;
import localsolver.*;

public class Maxcut {
    // LocalSolver
    private LocalSolver localsolver;

    // 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, false if it is on the left side of the cut
    private LSExpression[] x;

    // Objective
    private LSExpression cutWeight;

    // Reads 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();
            }
        }
    }

    // Declares the optimization model.
    private void solve(int limit) {
        localsolver = new LocalSolver();
        LSModel model = localsolver.getModel();

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

        // incut[e] is true if its endpoints are in different class of the partition
        // Note: the indices start at 1 in the instances
        LSExpression[] incut = new LSExpression[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();

        // Parameterizes the solver.
        LSPhase phase = localsolver.createPhase();
        phase.setTimeLimit(limit);
        localsolver.solve();
    }

    // Writes the solution in a file following 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());
            // In the instances the indices start at 1
            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 {
            Maxcut model = new Maxcut();
            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);
        }
    }
}