Algorithms and solvers for combinatorial problems.
What Campion is
Section titled “What Campion is”Campion is a project for the long-term development of algorithms and solvers. Its scope is combinatorial optimisation, graphs and inference, and later proofs. Each part should be specified clearly, tested thoroughly and measured on problems where it is meant to help.
The core is written in Rust. Python and C++ bindings expose the same algorithms, so a solver can be called from a modelling script or embedded in an existing C++ system without being rewritten.
The first solver: PBQP
Section titled “The first solver: PBQP”The first solver is for partitioned Boolean quadratic programming (PBQP). A PBQP instance is a graph. Each node is a variable that chooses exactly one of a few alternatives, and each alternative has a cost. Each edge has a cost matrix with one entry for every combination of choices at its two ends. A solution picks one alternative per node, and the aim is the lowest total cost over all nodes and edges.
The small example shows why the problem is hard. The cheapest choice for one node depends on the choices of its neighbours, and in a large graph those dependencies interact. PBQP is best known from compilers, where it models register allocation and instruction selection for processors with irregular register sets.
The name comes from the Boolean formulation. Each node’s alternatives become a group of Boolean variables, exactly one of which is true, so the variables are partitioned into one group per node.
The name
Section titled “The name”A campion is a meadow flower of the genus Silene. Red campion, Silene dioica, grows in meadows and along woodland edges across northern Europe. Its five petals are each deeply notched, which the logo draws as two facets per petal: one partition with two choices. The name also sounds like champion.
It is also a backronym:
Combinatorial Algorithms, Models, Proofs, Inference, Optimisation and Networks
The flower links Campion to Gecode Iris and to vallmo, a planned constraint programming system in Rust. Vallmo is Swedish for poppy.
Status
Section titled “Status”Campion has just started. Nothing has been released: there are no Rust crates, Python packages or C++ libraries to install, and every interface may change. The source is in the zayenz/campion repository on GitHub, which is private for now. This page will link to documentation and releases when they exist.