Functions
On our webpage, we provide solvers for different kinds of problems. The functions, that are currently implemented, are described below.
BiqBin
Description
Computes the solution of a binary quadratic problem subject to linear constraints.
min x'Fx + c'x s.t. Ax = b, x in {0,1}^n
Input
The parameters A,b,c, and F defining problem (refer to above) in a sparse format, where F is symmetric, thus we report only the upper (or lower) triangular part.
Example of an input:
3 2
A
1 1 1
1 2 1
1 3 1
b
1 1
F
1 1 1
1 3 2
2 2 2
3 3 3
c
2 1
3 2
The first line contains the number of variables n and the number of constraints m.
The next lines define the parameters.
There is line A, and the following lines denote the elements of A in a sparse format (row, column, value).
There is line b, and the following lines denote the elements of b in a sparse format (row, value).
There is line F, and the following lines denote the elements of the upper triangular part of the symmetric matrix F in sparse format (row, column, value).
There is line c, and the following lines denote the elements of c in a sparse format (row, value).
Output
A file with the result and info about process' execution on HPC.
Source code
Max-Cut
Description
Computes max-cut in a given graph.
Input
A graph in the edge list file. Example of format:
7 9
1 2 46
2 3 -22
3 4 76
4 5 -180
5 6 22
6 7 -50
7 1 14
1 5 61
3 7 3
The first line contains the number of vertices n and the number of edges m. The next m lines contain three integers denoting edges and their weights.
Output
A file with the result and info about running on HPC.
Source code
Stable set
Description
Computes the maximum stable set in a given unweighted graph.
Input
A graph in the edge list file. Example of format:
7 9
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 1 1
1 5 1
3 7 1
The first line contains the number of vertices n and the number of edges m. The next m lines contain three integers denoting edges and their weights.
Output
A file with the result and info about running on HPC.