XQCP -- X-Quadratic Constraint Programmer

A constraint-programming DSL that compiles a problem description into three XQVM assembly programs: an encoder, a verifier, and a decoder. See Three Programs for what those three are and why there are three.

Install

pip install xqcp

A complete example

Max-Cut for three nodes -- the same graph Quadratic Models derives by hand -- built with Problem and compiled to .xqasm:

from xqcp import Domain, Problem, Types

problem = Problem("Triangle")
n = problem.input("n", type=Types.Int)
edges = problem.input("edges", type=Types.Vec)
problem.define_model(size=n, domain=Domain.BINARY)

edge_count = problem.stow("edge_count", edges.veclen() // 3)
with problem.range(0, edge_count) as e:
    offset = e * 3
    i = problem.stow("i", edges.get(offset))
    j = problem.stow("j", edges.get(offset + 1))
    w = problem.stow("w", edges.get(offset + 2))
    problem.model.linear[i].add(-w)
    problem.model.linear[j].add(-w)
    problem.model.quadratic[i, j].add(w * 2)

partition = problem.output("partition", type=Types.Vec)
with problem.range(0, n) as node:
    partition.append(problem.sample.getline(node))

programs = problem.compile()
print(programs.encoder.count("\n"), "lines in the compiled encoder")
# 57 lines in the compiled encoder

programs.encoder builds the model; programs.verifier checks a sample against it and computes its energy; programs.decoder reads a sample back into a partition. Each is a standalone .xqasm string, runnable through any XQVM interpreter.

Domain also covers integer variables (INTEGER with k=, or with lo=/hi= for a range XQCP shifts into the model and back out through sample.value()) and unordered cases (CATEGORICAL with k= and penalty=, recorded as a one-hot binary grid read with sample.case()). The Modelling chapter covers each form and what constraints are available on it.

How it works

Problem records every DSL call (input, define_model, range, stow, model.linear[i].add(w), and the rest) as an Action. Nothing is assembled until compile() runs: it walks the recorded actions once per program and emits assembly with automatic register allocation and loop nesting.

DSL reference

The full DSL -- inputs, expressions, objectives, constraints, control flow, outputs, and what compile() produces -- is Modelling, eight chapters built around this exact package. The normative reference is spec/xqcp/SPEC.md; this package follows it, and any divergence here is a bug.

Examples

Fifteen complete problems built with this DSL, from Max-Cut to Travelling Salesman, are listed in the example gallery.

Also see

• xqvm_py -- pure-Python reference VM that runs the compiled programs.
• xqffi -- pyo3 FFI bindings to the Rust runtime.
• xqsa -- solver adapters for the models this package builds.
• xquad -- umbrella meta-package.

License

AGPL-3.0-or-later.