Mixed Integer Programming

Defined in algorithms/mixed_integer_program.hpp

namespace sarma::mixed_integer_program

To the best of our knowledge, this is the first work that tackles the symmetric rectilinear partitioning problem. Symmetric rectilinear partitioning is a restricted problem, therefore comparing our algorithms with more relaxed partitioning algorithms (such as jagged, rectilinear etc.) doesn’t provide enough information about the quality of the found partition vectors. Hence, we implemented a mathematical model that finds the optimal solution using Gurobi. This namespace contains required functions.

Note

This mixed integer program implementation can also handle non-symmetric partitioning.

Functions

template<bool symmetric, typename Int, typename Value>
auto partition(const Matrix<Int, Value> &A, const Int P, const Int Q_ = 0)

Implements the mixed integer program solver for rectilinear partitioning.

Return

a cut vector if symmetric and returns a pair of vectors if symmetric is false

Parameters

  • A: the input matrix

  • P: number of parts

  • Q_: number of parts in the other dimension for when template parameter symmetric is false