Index:

Preliminaries - containing preliminaries to Iterative Rounding and our interpretation of it.
Iterative Rounding interface - containing C++ interfaces of Iterative Rounding classes.
Example - example usage of the Iterative Rounding framework.
Custom components

Preliminaries

In the iterative rounding method we consider a linear programming relaxation of the given problem.
After solving the linear programming relaxation the fractional solution is being rounded (some variables are fixed to integer values) and/or relaxed (some constraints are removed from the problem) according to some rounding and relaxing rules (specfic to the problem).
The obtained simplified linear program is then resolved and the process is iterated until we obtain a solution to the original problem.

Let us write the pseudo code for this operation:

 iterative_rounding()
 {
     init(LP)
     solve(LP)
     while (not solution_found(LP))
     {
         round(LP)
         relax(LP)
         resolve(LP)
     }
     return solution(LP)
 }

The relax step proceeds as follows:

 relax(LP)
 {
     for_each (Row r in LP)
     {
         if (relax_condition(r))
         {
             delete_row(r, LP)
         }
     }
 }

Note that in most algorithms we can relax an arbitrary number of relaxable constraints (as long as we relax at least one, in order to make progress). The framework allows to set a limit on the number of constraints relaxed in each iteration.

There are two possible versions of the round step. The most common one is similar to the above relax step:

 round(LP)
 {
     for_each (Column c in LP)
     {
         if (round_condition(c))
         {
             val -> round_value(c)
             fix_column(c, val, LP)
         }
     }
 }

That is, we decide independetly whether each column should be rounded.

In another version, called dependent rounding, we do the rounding based on the values of all columns (not independently, hence the name: dependent rounding).

Iterative Rounding interface

In order to present the iterative rounding interface we need to introduce several concepts.
Note that Problem is the problem type: a class containing problem input data and any additional data structures necessary to solve the problem (e.g., mapping between problem elements and LP rows or columns).
LP is the linear programming instance type, paal::lp::col_id and paal::lp::row_id are the LP column and row identifier types (see Linear Programming).

The Iterative Rounding framework uses eight component classes (described below):

Those components are grouped together into one class: paal::ir::IRcomponents, using the Components class.

Out of the listed components only the first one (Init) does not have a default value and has to be provided by the user.
Also, at least one of the next 3 components (RoundCondition, RelaxCondition, SetSolution) should be provided by the user in order to construct the solution to the problem. Depending on the problem, the solution can be most easily constructed either during the execution of the algorithm (during the round/relax steps: RoundCondition, RelaxCondition) or in the end (in the SetSolution step).

Components:

Init is a concept class responsible for initializing the LP form the given problem and initializing additional problem data structures.
```
    InitArchetype {
        void operator()(Problem & problem, LP & lp);
    }
    
```
RoundCondition is a concept class responsible for checking if a given column can be rounded according to the used rounding rules.
If the answer is positive, it returns the value to which the column is rounded.
```
    RoundConditionArchetype {
        boost::optional<double> operator()(Problem & problem, const LP & lp, paal::lp::col_id column);
    }
    
```
Alternatively, if the problem uses dependent rounding then instead of the RoundCondition concept class we use DependentRound concept class.
DependentRound is a concept class responsible for performing dependent rounding based on all of the column values.
```
    DependentRoundArchetype {
        void operator()(Problem & problem, LP & lp);
    }
    
```
Default component: paal::ir::default_round_condition (rounds each column, which value is integral).
RelaxCondition is a concept class responsible for checking if the given row can be relaxed according to the used relaxing rules.
```
    RelaxConditionArchetype {
        bool operator()(Problem & problem, const LP & lp, paal::lp::row_id row);
    }
    
```
Default component: paal::utils::always_false (no relaxations).
SetSolution is a concept class responsible for constructing the solution of the original problem, based on the values of the final LP solution and the values of columns fixed (rounded) in previous iterations. The solution is passed as a function from column identifier to column value.
```
    template <typename GetSolution>
    SetSolutionArchetype {
        void operator()(Problem & problem, const GetSolution & solution);
    }
    
```
GetSolution is the type of a function from paal::lp::col_id to double (function returning the value of the given column in the final LP solution).
Default component: paal::utils::skip_functor (skips solution setting).
SolveLP is a concept class responsible for solving the LP for the first time.
```
    SolveLPArchetype {
        paal::lp::problem_type operator()(Problem & problem, LP & lp);
    }
    
```
Default component: paal::ir::default_solve_lp_to_extreme_point (finds an extreme point solution to the LP).
ResolveLP is a concept class responsible for re-solving a previously solved and modified LP.
```
    ResolveLPArchetype {
        paal::lp::problem_type operator()(Problem & problem, LP & lp);
    }
    
```
Default component: paal::ir::default_resolve_lp_to_extreme_point (finds an extreme point solution to the LP).
StopCondition is a concept class responsible for checking if the current LP solution is a valid solution to the original problem. In such case we should finish the algorithm.
```
    StopConditionArchetype {
        bool operator()(const Problem & problem, const LP & lp);
    }
    
```
Default component: paal::ir::default_stop_condition (stops if all colums have got integer values).
RelaxationsLimit is a concept class responsible for checking if the limit of relaxations number per IR iteration was reached.
```
    RelaxationsLimitArchetype {
        bool operator()(int number_of_relaxed_constraints);
    }
    
```
Default component: paal::utils::always_false (no limit on relaxations number).

Now we can introduce the paal::ir::solve_iterative_rounding interface:

template <typename Problem,
          typename IRComponents,
          typename Visitor = paal::ir::trivial_visitor,
          typename LP = paal::lp::glp>
paal::ir::IRResult solve_iterative_rounding(Problem & problem, IRComponents components, Visitor visitor = Visitor());

In the case when our algorithm uses dependent rounding, we should apply the paal::ir::solve_dependent_iterative_rounding interface:

template <typename Problem,
          typename IRComponents,
          typename Visitor = paal::ir::trivial_visitor,
          typename LP = paal::lp::glp>
paal::ir::IRResult solve_dependent_iterative_rounding(Problem & problem, IRComponents components, Visitor visitor = Visitor());

Example

Complete example: iterative_rounding_example.cpp

In this example we are going to solve the minimum cost vertex cover problem (minimum cost set of vertices in a graph \(G=(V,E)\), which are incident with every edge).
The algorithm follows the iterative rounding framework: we have a variable \(x_v\) for every vertex \(v\) (of cost \(c_v\)) and solve the following LP:

\begin{eqnarray*} \mbox{minimize:} & \sum_{v\in V} \ c_v x_v & \\ \mbox{subject to:} & & \\ & x_v + x_u \geq 1 & \mbox{ for every } (u,v)=e \in E\\ & 0\leq x_v\leq 1 & \mbox{ for every } v\in V\\ \end{eqnarray*}

We round to 1 every variable with value greater or equal to \(\frac{1}{2}\) (such variable can always be found, see [22] chapter 14.3). The vertex cover is the set of vertices with value 1 in the final solution.
The algorithm gives a 2-approximation (it's not the most effective implementation of the 2-approximation, but it gives a simple example of the IR framework).

First we define the vertex_cover class, which contains the problem input data and a mapping between the LP columns and graph vertices.

#include "paal/iterative_rounding/iterative_rounding.hpp"
#include "paal/utils/floating.hpp"
#include "paal/utils/functors.hpp"
#include <boost/graph/adjacency_list.hpp>
#include <boost/range/iterator_range.hpp>
#include <iostream>
#include <unordered_map>
namespace ir = paal::ir;
template <typename Graph, typename CostMap, typename OutputIter>
class vertex_cover {
public:
    vertex_cover(const Graph & g, CostMap cost_map, OutputIter cover) :
        m_g(g), m_cost_map(cost_map), m_cover(cover) {}
    using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;
    using VertexMap = std::unordered_map<Vertex, paal::lp::col_id>;
    const Graph &get_graph() const { return m_g; }
    auto get_cost(Vertex v)->decltype(std::declval<CostMap>()(v)) {
        return m_cost_map(v);
    }
    void bind_col_to_vertex(paal::lp::col_id col, Vertex v) {
        m_vertex_map.insert(typename VertexMap::value_type(v, col));
    }
    paal::lp::col_id vertex_to_column(Vertex v) { return m_vertex_map[v]; }
    void add_to_cover(Vertex v) {
        *m_cover = v;
        ++m_cover;
    }
  private:
    const Graph &m_g;
    CostMap m_cost_map;
    OutputIter m_cover;
    VertexMap m_vertex_map;
};

Next we define the vertex_cover_init and vertex_cover_set_solution functors, and the vertex_cover_ir_components components class.

struct vertex_cover_init {
    template <typename Problem, typename LP>
    void operator()(Problem &problem, LP &lp) {
        lp.set_optimization_type(paal::lp::MINIMIZE);
        // variables for vertices
        for (auto v :
             boost::make_iterator_range(vertices(problem.get_graph()))) {
            problem.bind_col_to_vertex(lp.add_column(problem.get_cost(v)), v);
        }
        // x_u + x_v >= 1 for each edge e=(u,v)
        for (auto e : boost::make_iterator_range(edges(problem.get_graph()))) {
            auto x_u = problem.vertex_to_column(source(e, problem.get_graph()));
            auto x_v = problem.vertex_to_column(target(e, problem.get_graph()));
            lp.add_row(x_u + x_v >= 1);
        }
    }
};
struct vertex_cover_set_solution {
    template <typename Problem, typename GetSolution>
    void operator()(Problem &problem, const GetSolution &solution) {
        // add vertices with column value equal 1 to cover
        for (auto v :
             boost::make_iterator_range(vertices(problem.get_graph()))) {
            if (m_compare.e(solution(problem.vertex_to_column(v)), 1)) {
                problem.add_to_cover(v);
            }
        }
    }
private:
    const paal::utils::compare<double> m_compare;
};
using vertex_cover_ir_components =
    ir::IRcomponents<vertex_cover_init, ir::round_condition_greater_than_half,
                     paal::utils::always_false, vertex_cover_set_solution>;

Finally, we can use the defined classes to solve an instance of the problem.

int main() {
    using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
        boost::no_property, boost::no_property>;
    using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
    // sample problem
    std::vector<std::pair<int, int>> edges{ { 0, 1 }, { 0, 2 }, { 1, 2 },
                                            { 1, 3 }, { 1, 4 }, { 1, 5 },
                                            { 5, 0 }, { 3, 4 } };
    std::vector<int> costs{ 1, 2, 1, 2, 1, 5 };
    Graph g(edges.begin(), edges.end(), 6);
    auto vertex_costs = paal::utils::make_array_to_functor(costs);
    std::vector<Vertex> result_cover;
    auto insert_iter = std::back_inserter(result_cover);
    vertex_cover<Graph, decltype(vertex_costs), decltype(insert_iter)> problem(
        g, vertex_costs, insert_iter);
    // solve it
    auto result =
        ir::solve_iterative_rounding(problem, vertex_cover_ir_components());
    // print result
    if (result.first == paal::lp::OPTIMAL) {
        std::cout << "Vertices in the cover:" << std::endl;
        for (auto v : result_cover) {
            std::cout << "Vertex " << v << std::endl;
        }
        std::cout << "Cost of the solution: " << *(result.second) << std::endl;
    } else {
        std::cout << "The instance is infeasible" << std::endl;
    }
    paal::lp::glp::free_env();
    return 0;
}

Custom components

The library provides a number of custom components which might be very helpful.

paal::ir::default_round_condition
paal::ir::round_condition_equals
paal::ir::round_condition_to_fun
paal::ir::cond_bigger_equal_than
paal::ir::round_condition_greater_than_half
paal::ir::default_solve_lp_to_extreme_point
paal::ir::default_resolve_lp_to_extreme_point
paal::lp::row_generation_solve_lp (more: Row generation)
paal::lp::row_generation_resolve_lp (more: Row generation)
paal::ir::default_stop_condition
paal::ir::relaxations_limit_condition