Max-Cut Problem

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)

#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;
    }
}

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);
        }
    }
}

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);
        }
    }
}