# Max Cut¶

## Principles learned¶

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

## Problem¶ 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.

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

use io;

function input() {
local usage = "Usage: localsolver maxcut.lsp "
+ "inFileName=inputFile [solFileName=outputFile] [lsTimeLimit=timeLimit]";

if (inFileName == nil) throw usage;

for [e in 1..m] {
}
}

/* 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\python
python maxcut.py instances\g05_60.0
Execution (Linux)
export PYTHONPATH=/opt/localsolver_10_5/bin/python
python maxcut.py instances/g05_60.0
########## maxcut.py ##########

import localsolver
import sys

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

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

with localsolver.LocalSolver() as ls:

#
#

# 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)

#
# 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
#
if len(sys.argv) >= 4: ls.param.time_limit = int(sys.argv)
else: ls.param.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, '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\localsolver105.lib
maxcut instances\g05_60.0
Compilation / Execution (Linux)
g++ maxcut.cpp -I/opt/localsolver_10_5/include -llocalsolver105 -lpthread -o maxcut
./maxcut instances/g05_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;

ifstream infile;
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++) {
}

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

// Parameterizes the solver.
localsolver.getParam().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.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;
const char* solFile = argc > 2 ? argv : NULL;
const char* strTimeLimit = argc > 3 ? argv : "10";

try {
Maxcut model;
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 %LS_HOME%\bin\localsolvernet.dll .
csc Maxcut.cs /reference:localsolvernet.dll
Maxcut instances\g05_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();
}

{
{
n = int.Parse(tokens);
m = int.Parse(tokens);

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

for (int e = 0; e < m; e++)
{
origin[e] = int.Parse(tokens);
dest[e] = int.Parse(tokens);
w[e] = int.Parse(tokens);
}
}
}

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++)
{
}
model.Maximize(cutWeight);

model.Close();

// Parameterizes the solver.
localsolver.GetParam().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;
string outputFile = args.Length > 1 ? args : null;
string strTimeLimit = args.Length > 2 ? args : "10";

using (Maxcut model = new Maxcut())
{
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 instances\g05_60.0
Compilation / Execution (Linux)
javac Maxcut.java -cp /opt/localsolver_10_5/bin/localsolver.jar
java -cp /opt/localsolver_10_5/bin/localsolver.jar:. Maxcut instances/g05_60.0
/********** Maxcut.java **********/

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

public class Maxcut {
// LocalSolver
private final 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;

private Maxcut(LocalSolver localsolver) {
this.localsolver = localsolver;
}

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) {
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++) {
}
model.maximize(cutWeight);

model.close();

// Parameterizes the solver.
localsolver.getParam().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;
String outputFile = args.length > 1 ? args : null;
String strTimeLimit = args.length > 2 ? args : "10";

try (LocalSolver localsolver = new LocalSolver()) {
Maxcut model = new Maxcut(localsolver);