Boolean Optimisation

[SSoelvsten]

Donald Knuth solved the NP-complete combinatorial coloring problem (and many others) to optimality in a graph of 50 nodes in one of his lectures and also in The Art of Programming Volume 4A on page 208 - 214. Given that Adiar already is competitive with other BDD packages for combinatorial problems, this seems like an interesting way to go.

The resulting algorithm should run in O(sort(N)) time and I/Os and use O(N) space.

<adiar/functional.h>:

////////////////////////////////////////////////////////////////////////////////
/// \brief Provider of the cost of assigning variable *x* the value `true`. That
///        is, this provides the coefficients for a linear programming problem.
///
/// \tparam label_t The integral type of the *x* value(s).
////////////////////////////////////////////////////////////////////////////////
template<typename label_t>
using cost_function = function<double(label_t)>;

<adiar/bdd.h>:

Here, we would at a minimum want the bdd_optmin function that computes finds the minimal path in a BDD. The output should be the cost of the path and the path itself. The path may be provided in two ways:

1. A callback function cb (i.e. a consumer function) is called bottom-up with the assignment.
2. A cubical BDD is constructed, i.e. a BDD with a single node on each level and each node reflects the assignment in the shortest path.

////////////////////////////////////////////////////////////////////////////////
/// \brief obtain the satisfying assignment that is minimal for the given linear
///        cost function over the global domain.
///
/// \param f  The BDD of feasible solutions
///
/// \param c  A (pure) function that provides the cost function's coefficient.
///
/// \param cb  A callback function that is called in \em descending order.
///
/// \returns The cost of the satisfying cost.
///
/// \see     domain_set domain_isset
////////////////////////////////////////////////////////////////////////////////
double
bdd_optmin(const bdd &f,
           const cost_function<bdd::label_t> &c,
           const consumer<bdd::label_t, bool> &cb);

////////////////////////////////////////////////////////////////////////////////
/// \brief obtain the satisfying assignment that is minimal for the given linear
///        cost function over the global domain.
////////////////////////////////////////////////////////////////////////////////
double
bdd_optmin(const exec_policy &ep,
           const bdd &f,
           const cost_function<bdd::label_t> &c,
           const consumer<bdd::label_t, bool> &cb);

////////////////////////////////////////////////////////////////////////////////
/// \brief obtain the satisfying assignment that is minimal for the given linear
///        cost function over the global domain.
///
/// \param f The BDD of feasible solutions
///
/// \param c A (pure) function that provides the cost function's coefficient.
///
/// \returns A pair of a BDD with the assignment and its cost.
///
/// \see     domain_set domain_isset
///
/// \pre     The global \ref module__domain is set to a set of variables
///          that is equals to or a superset of the variables in `A`.
////////////////////////////////////////////////////////////////////////////////
std::pair<bdd, double>
bdd_optmin(const bdd &f, const cost_function<bdd::label_t> &c);

////////////////////////////////////////////////////////////////////////////////
/// \brief obtain the satisfying assignment that is minimal for the given linear
///        cost function over the global domain.
////////////////////////////////////////////////////////////////////////////////
std::pair<bdd, double>
bdd_optmin(const exec_policy &ep,
           const bdd &f,
           const cost_function<bdd::label_t> &c);

As @halvko noticed, these functions implicitly work over a global domain. If a domain is not set, then the BDD's levels should be used instead. Yet, this makes things much more complicated: each suppressed node in the BDD may either choose to set their value to 0 or to 1 to further improve the solution.

The best solution seems to restrict our focus to bdd_optmin with c only providing non-negative values, i.e. 0 <= c(x) for all x.

<adiar/zdd.h>:

Since ZDDs are in many cases better than BDDs for combinatorial (optimisation) problems, we would also want to have the equivalent function zdd_optmin. To implement this, we need to parameterise the algorithm on a template parameter DdPolicy (instantiated as bdd_policy or zdd_policy). In this case we only need these to obtain the input and output types.

The beautiful thing about ZDDs is, that their semantics force the value of each suppressed variable in the DAG to be 0. That is, each suppressed variable by definition cannot contribute to the minimal nor to the maximal path. That is:

1. We do not need to put any requirements on the cost function c.
2. We can also provide the zdd_optmax function. To do so, we need to parameterise the algorithm's comparator, i.e. replace < with std::less<>/std::greater<> provided as the template parameter Comp.

[SSoelvsten]

Closed by the good work of Erik Funder Carstensen ( @halvko ) last semester.