mixingcut 0.1.3

A program to solve the MAXCUT SDP Relaxation.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

# MixingCut Solver and Library 


MixingCut is a solver and library for the MaxCut SDP relaxation via mixing cut algorithm proposed by Po-Wei Wang et al [1]. This 
can solve general large scale instances of the MaxCut SDP relaxation problem.

$$
\begin{align*}
\min_{X} &\text{tr}(QX) \\
s.t. &X_{ii} = 1\\
&X \succeq 0
\end{align*}
$$

In addition to the solver, this repository provides a library that can be used to integrate the components of the MixingCut algorithm into other applications. The library is designed to be modular and easy to use, allowing developers to leverage the power of the MixingCut algorithm in their own projects.


# Binary Usage


## Mixing Cut Solver


The MixingCut solver can be used via the command line with the following interface:

```bash
./mixingcut \
    --input-path <input_file> \
    --output-path <output_file> \
    --rank <rank> \
    --tolerance <tolerance> \
    --max-iters <max_iter> \
    --index-correction <index-correction> \
    --step-rule <step_rule> \
    --dual-bound <dual_bound> \
    --verbose <verbose> \
    --rounding-iters <rounding_iters>
```

Where:
- `<input_file>` is the path to the file containing the input data for the matrix ``Q``. 
- `<output_file>` is the path to the file where the output will be written. Default is ``output.txt``.
- `<rank>` is the rank of the low rank approximation, and ``rank = 0`` selects ``2log2(n)``, and ``rank = 1`` 
  selects ``sqrt(2n)`` as the rank. Default is ``0`` 
- `<tolerance>` is the tolerance for the stopping criterion between iterations. If the objective improvement is less 
  than this number, solver termination occures. Default is ``1e-2``. 
- `<max_iter>` is the maximum number of iterations. Default is ``1000``.
- `<step_rule>` is the update rule for the mixing cut algorithm. Default is ``coord_no_step``. Options are ``grad``, 
  ``grad_adv``, ``coord`` and ``coord_no_step``. 
- `<index_correction>` is for reading the input graph file, if the vertices are 0-indexed or 1-indexed. Default is 
  ``1``. 
- `<dual_bound>` is the flag for computing the dual bound for the SDP relaxation. Default is ``0``. A value of ``1`` 
  will compute the dual bound (this is an expensive(non computable) operation for large(huge) instances).  
- `<verbose>` is the flag for printing the output to the console. Default is ``1``. To disable output set to ``0``.
- `<rounding_iters>` is the number of iterations for the rounding algorithm. Default is ``1000``.

However, only the input file is required. The solver will use the default values for the other parameters if not 
specified in the command line with the following command: 

```bash
./mixingcut --input-path <input_file>
```

### Expected File Format

The solver reads the input from a file in the following format: Where `n` is the number of vertices, `i` and `j` are 
the vertices of the edge and `q_ij` is the weight of the edge. In the case where ``q_ij`` is not specified, the 
default value is 1.

```
n
i_1 j_1 q_{i_1,j_1}
i_2 j_2 q_{i_2,j_2}
...
i_m j_m q_{i_m,j_m}
```

### Output File Format

The solver writes a rounded solution to a file in the following format: Where ``obj_sdp`` is the value of the 
SDP relaxation, ``obj_rounded_sol`` is the value of the rounded solution and `x_i` is the value of the vertex `i`. 

```
obj_sdp
obj_rounded_sol
x_0
x_1
...
x_{n-1}
```

## Perturb


```bash
./perturb \
    --input-path <input_file> \
    --output-path <output_file> \
    --rank <rank> \
    --tolerance <tolerance> \
    --max-iters <max_iter> \
    --index-correction <index-correction> \
    --step-rule <step_rule> \
    --verbose <verbose>
```

Where:
- `<input_file>` is the path to the file containing the input data for the matrix ``Q``.
- `<output_file>` is the path to the file where the output will be written. Default is ``output.txt``.
- `<rank>` is the rank of the low rank approximation, and ``rank = 0`` selects ``2log2(n)``, and ``rank = 1``
  selects ``sqrt(2n)`` as the rank. Default is ``0``
- `<tolerance>` is the tolerance for the stopping criterion. If the stationarity condition error is less
  than this number, solver termination occurs. Default is ``1e-2``.
- `<max_iter>` is the maximum number of iterations. Default is ``1000``.
- `<step_rule>` is the update rule for the mixing cut algorithm. Default is ``coord_no_step``. Options are ``grad``,
  ``grad_adv``, ``coord`` and ``coord_no_step``.
- `<index_correction>` is for reading the input graph file, if the vertices are 0-indexed or 1-indexed. Default is
  ``1``.
- `<dual_bound>` is the flag for computing the dual bound for the SDP relaxation. Default is ``0``. A value of ``1``
  will compute the dual bound (this is an expensive(non computable) operation for large(huge) instances).
- `<verbose>` is the flag for printing the output to the console. Default is ``1``. To disable output set to ``0``.

# More Info 


MixingCut is based on the ideas proposed by the following paper:

```bibtex
@article{wang2017mixing,
	title = {The Mixing method: coordinate descent for low-rank semidefinite programming},
	author = {Po-Wei Wang and Wei-Cheng Chang and J. Zico Kolter},
	journal = {arXiv preprint arXiv:1706.00476},
	year = {2017}
}
```