mixingcut 0.1.2

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

#![allow(non_snake_case)] // reasoning: The code is based on linear algebra notation (X is a matrix, x is a vector)

use clap::Parser;
use mixingcut::io_operations;
use mixingcut::io_operations::write_dual_variables;
use mixingcut::maxcut_oracle::get_Q_norm;
use mixingcut::sdp_solver::compute_approx_perturbation;
use mixingcut::step_rules::generate_step_rule;
use std::time::{SystemTime, UNIX_EPOCH};

#[derive(Parser, Debug)]
#[command(version, about, long_about = None)]
struct Args {
    // Name of the input file
    #[clap(short, long)]
    input_path: String,

    // Name of the output file
    #[clap(short, long, default_value = "output.txt")]
    output_path: String,

    #[clap(short, long, default_value = "0")]
    rank: usize,

    // The stopping tolerance
    #[clap(short, long, default_value = "1e-2")]
    tolerance: f64,

    // Number of iterations
    #[clap(short, long, default_value = "1000")]
    max_iters: usize,

    // Step Rule
    #[clap(short, long, default_value = "coord_no_step")]
    step_rule: String,

    // index correction
    #[clap(long, default_value = "1")]
    index_correction: usize,

    // compute dual bound
    #[clap(short, long, default_value = "0")]
    dual_bound: usize,

    // verbosity
    #[clap(short, long, default_value = "1")]
    verbose: usize,

    // rounding iters
    #[clap(long, default_value = "100")]
    rounding_iters: usize,

    // beam search width
    #[clap(long, default_value = "128")]
    beam_width: usize,
}

fn current_time() -> f64 {
    SystemTime::now()
        .duration_since(UNIX_EPOCH)
        .unwrap()
        .as_secs_f64()
}

fn main() {
    let args: Args = Args::parse();

    let index_correction = args.index_correction;

    // read in the graph
    let Q = io_operations::read_graph_matrix(&args.input_path, index_correction);

    let alpha_safe = get_Q_norm(&Q);

    let step_rule = generate_step_rule(&args.step_rule, alpha_safe);

    let n = Q.shape().0;

    let max_iters = args.max_iters;

    let verbose = args.verbose;

    let start = current_time();

    let tolerance = args.tolerance;

    // set up the rank size of the problem
    let k = match args.rank {
        0 => 2 * (n as f64).log2() as usize,
        1 => (2.0 * n as f64).sqrt() as usize,
        _ => args.rank,
    };

    let is_verbose = verbose > 0;

    let y_sol = compute_approx_perturbation(
        &Q,
        Some(k),
        None,
        Some(max_iters),
        Some(tolerance),
        Some(step_rule),
        is_verbose,
    );

    let end = current_time();

    // print the perturbation solution
    if verbose > 0 {
        println!("Perturbation solution: {:?}", y_sol);
        println!("Perturbation solution norm: {}", y_sol.sum());
        println!("Solved in {:.5} seconds", end - start);
    }

    write_dual_variables(&args.output_path, y_sol);
}