# Qelly Bench v0

Exactly solved liquidity decisions, for any optimizer.

This is a small suite of synthetic instances of one constrained scheduling
problem from small-business finance. Every instance ships with its exact
optimum, the exact number of feasible plans, exports for other solvers, and an
independent checker that replays any answer and issues a certificate.

**No quantum advantage is claimed.** A MILP solver (HiGHS) finds the optimum
of every instance here in milliseconds. The exact contraction that also counts
the feasible plans takes from milliseconds to several minutes on a laptop. The
point is that every instance ships with ground truth, so any solver's answer can
be scored exactly. All figures are synthetic and fictional.

## The problem

A business holds one or more cash accounts over a horizon of weekly periods.
Each account has an opening balance, a reserve it must never go below, and
committed weekly cash flows. On top of that there is a list of decisions
(*items*). Every item has mutually exclusive *options*; every option has an
integer cost and a schedule of integer cash flows. Examples: pay a supplier
when due or a week later for a fee, take an early-payment discount, stage an
investment, draw on a credit line and repay it with interest, move cash between
entities of a group. A fee, discount or interest charge is paid in cash with the
payment it belongs to, in the same week, so it appears in the option's cash
flows as well as in its cost. The one cost that moves no cash is the estimated
margin lost by deferring an investment beyond the horizon (a non-cash
opportunity cost).

A *plan* picks exactly one option per item. A plan is *feasible* when every
account's closing cash is at or above its reserve in every week (flows within a
week are netted first). The objective is the minimum total option cost over
feasible plans. All amounts are whole currency units, so feasibility and cost
are exact.

Two families are included:

* `chain` — one company, one account. The constraint structure is a chain in
  time. That alone does not keep exact contraction cheap: because fees are paid
  in cash, the number of distinct cash states grows quickly as payables are
  added (`chain-n18` carries about 1.2 million).
* `group` — several entities with their own cash and reserves, coupled by
  intercompany transfers and one shared credit facility. Each extra entity
  multiplies the states our exact contraction carries between weeks
  (`max_bond_dimension` below). That number sets this method's cost; it is not
  a lower bound for other exact solvers, and a MILP solver is fast on all of
  these instances.

`demo` is the illustration shown on qelly.ai; it also defines two alternative
scenarios (`late_1`, `late_2`) in which one customer receipt arrives later.

## Instances

| instance | family | accounts | items | binary variables | plan space | feasible plans | optimum | optimal plans | max bond dimension | slack-QUBO variables |
|---|---|---:|---:|---:|---:|---:|---:|---:|---:|---:|
| `demo` | illustration | 1 | 8 | 24 | 5,184 | 1,333 | 2,850 | 1 | 1,132 | 119 |
| `chain-n6` | chain | 1 | 8 | 20 | 864 | 18 | 13,400 | 1 | 76 | 119 |
| `chain-n10` | chain | 1 | 12 | 33 | 82,944 | 1,212 | 15,365 | 1 | 3,958 | 129 |
| `chain-n14` | chain | 1 | 16 | 45 | 8,503,056 | 103,256 | 16,046 | 1 | 110,382 | 149 |
| `chain-n18` | chain | 1 | 20 | 57 | 544,195,584 | 5,876,472 | 14,373 | 1 | 1,190,981 | 160 |
| `group-e2` | group | 2 | 9 | 32 | 40,320 | 584 | 12,400 | 1 | 1,434 | 242 |
| `group-e3` | group | 3 | 13 | 46 | 889,056 | 9,990 | 12,748 | 1 | 6,732 | 365 |
| `group-e4` | group | 4 | 17 | 63 | 256,048,128 | 2,588,016 | 13,005 | 3 | 263,424 | 489 (not shipped) |

`binary variables` counts one variable per (item, option). `plan space` is the
number of one-option-per-item combinations. `max bond dimension` is the largest
number of distinct (cash, open-decision) states the exact contraction carried
between two weeks. `slack-QUBO variables` counts decision and slack bits; a
slack QUBO with more than 400 variables is not shipped (marked `not shipped`
above and noted under `notes` in `manifest.json`). The same numbers, with
SHA-256 hashes and byte sizes of every file, are in `manifest.json`.

For `demo`, the 1,333 feasible plans include those that defer the equipment order. The homepage counts the 85 of them that place the order (any `investment` option except `defer`); the optimum, 2,850, is the same either way. Deferring moves no cash: its 12,000 cost is an estimated, non-cash opportunity cost (margin lost after the six-week window). Every other fee, discount and interest charge is paid in cash with the payment it belongs to.

In `chain-n6`, `chain-n10`, `chain-n14`, `chain-n18`, `group-e2`, `group-e3` and `group-e4`, no feasible plan places the investment: every feasible plan defers it, so each of these optima includes the 12,000 estimated, non-cash deferral cost (75% to 97% of the optimum). The generators set opening cash as tight as they can while keeping at least 1% of all plans feasible, and in these instances none of those plans leaves room for the investment. Read them as scheduling problems around a deferred investment. `demo` is the only instance with feasible plans that place it. `investment.placing_plans` in `manifest.json` gives the exact count for every instance.

## Files per instance

| file | content |
|---|---|
| `instance.json` | the instance, schema `qelly.liquidity.v1` |
| `solution.json` | exact optimum, one optimal plan, number of optimal plans, exact count of feasible plans, per-week bond dimensions, an independent MILP (HiGHS) cross-check, the checker's certificate, and option marginals for plan spaces up to one million |
| `qubo_slack.json` | QUBO with binary slack variables for every reserve constraint; exact integer coefficients. Not shipped when it has more than 400 variables |
| `qubo_unbalanced.json` | QUBO with unbalanced penalization, no slack variables |
| `ising_unbalanced.json` | the same model in Ising form (`s = 2x - 1`) for gate-model and annealing workflows |
| `cqm.lp` | the constrained binary model in standard LP format (objective, one-hot equalities, reserve inequalities, `Binary` section), written by `dimod`. MILP solvers such as HiGHS, SCIP, Gurobi or CPLEX read it directly; `dimod.lp.load` reads it as a CQM |
| `cqm_labels.json` | maps the LP-safe labels in `cqm.lp` back to the export variable names |

Exports describe the base scenario. `solution.json` of `demo` also lists the
exact results of its other scenarios under `scenarios`.

### `instance.json`

```
accounts[]   id, opening_cash, reserve, fixed_flows[week]      (committed net flow per week)
items[]      id, kind, label, options[]
options[]    id, label, cost, flows[] = {week, account, amount}  (amount < 0 is an outflow)
scenarios{}  name -> {account id -> fixed_flows[week]}           (replaces the committed flows)
```

Weeks are numbered from 1. Closing cash of an account in week `t` is its
opening cash, plus committed flows through `t`, plus the flows through `t` of
every selected option.

### `qubo_*.json`

```
minimize  offset + sum_i linear[variables[i]] * x_i + sum_(i<j) bias_ij * x_i * x_j,   x binary
```

`quadratic` entries are `[i, j, bias]` with `i < j`, both indexing `variables`.
Variable `x[item|option] = 1` selects that option; every item needs exactly one
selected option. Variables `s[account|week|bit]` are slack bits and carry no
decision. With `g = meta.granularity` and `h = (closing cash - reserve) / g`
for each (account, week):

* **slack** — `P * (sum_o x[k,o] - 1)^2` per item and `P * (h - s)^2` per
  reserve constraint, `s` a bounded binary-encoded integer (Lucas 2014).
  `P = meta.penalty`. In exact arithmetic a feasible plan with the right slack
  bits has energy equal to its cost, and any violated constraint costs at least
  `P`. The default
  `P = 1 + sum_k max_o cost[k,o] - sum_(k,o) min(0, cost[k,o])` makes every
  invalid assignment cost more than every feasible plan, so the ground states
  are the optimal plans.
* **unbalanced** — the same one-hot term and `P * (-l1 * h + l2 * h^2)` per
  reserve constraint with `(l1, l2) = meta.unbalanced_lambda`
  (Montañez-Barrera et al. 2024). This encoding is approximate by design and
  the weights were not tuned: a lower energy does not imply a feasible plan.

**Numbers and precision.** Slack-QUBO coefficients and offsets are exact
integers, written as JSON integers. With amounts in whole dollars they are
large: `meta.max_abs_coefficient` and `meta.abs_offset` give the magnitudes,
and `meta.float64_exact` is `false` when a coefficient, the offset or an energy
sum can exceed 2^53 = 9,007,199,254,740,992, beyond which a double does not
hold every integer. That is the case for every slack QUBO here except `demo`'s.
Plan costs can differ by one dollar, so rounding the coefficients by a few units
can change which assignment has the lowest energy. Read these files with an
integer-preserving JSON parser (Python's `json` module is one; JavaScript's
`JSON.parse` is not) and add energies in integer arithmetic; a solver that
works in double precision solves a slightly perturbed model. The unbalanced
QUBO and the Ising file have rational coefficients, each rounded once to the
nearest double.

`meta.bias_dynamic_range` is the ratio of the largest to the smallest non-zero
coefficient, which matters for analog hardware. In every case the energy a
solver reports is not evidence of feasibility. Only the checker decides.

## Checking an answer

`qelly_check.py` is a single file with no dependencies (Python 3.8 or newer)
and shares no code with any solver.

```sh
python3 qelly_check.py instances/demo/instance.json my_plan.json \
    --solution instances/demo/solution.json --solver "my-solver v1"
```

`my_plan.json` is either a plan, `{"item_id": "option_id", ...}`, or a binary
sample straight from a QUBO, Ising or CQM solver,
`{"x[item_id|option_id]": 0 or 1, ...}` (slack variables are ignored; for
`cqm.lp` map labels back with `cqm_labels.json` first). Use
`--scenario late_1` to replay under a named scenario.

The checker replays the plan week by week with integer arithmetic and prints a
certificate: instance digest, scenario, solver name, the plan, `valid`,
`feasible`, `cost`, any reserve `breaches`, and, when `--solution` is given,
`reference_optimum`, `gap` and `matches_reference_optimum`. The certificate
carries a SHA-256 digest of its own content. It replays feasibility and cost;
optimality is only relative to the supplied reference optimum, which the
checker does not prove. The published optimum in `solution.json` comes from an
exact contraction over every plan and is cross-checked by HiGHS
(`optimum_basis`). Neither establishes that the fictional inputs are true.
Exit status is 0 for a feasible plan, 1 for an infeasible or invalid answer, 2
for a usage or input error.

## What to report

We would like to see how annealing, gate-model, quantum-inspired and classical
solvers do on this suite. If you run it, please send the certificates to
luis@qelly.ai together with the solver and hardware, the encoding and penalty
settings, wall-clock time, the number of reads or shots, and the share of
samples that were feasible. Negative results are useful. A fair comparison
matches wall-clock budgets and includes a classical exact baseline; an MILP
solver finds the optimum of every instance here in well under a second.

## Reproducibility

The bundle is generated by `python3 -m qelly_dtn.bench` from fixed seeds and is
byte-reproducible; `manifest.json` lists the SHA-256 of every file. The exact
results come from a tensor-network contraction (dynamic programming over the
weekly chain with swappable arithmetic: counting for the number of feasible
plans, min-plus for the optimum), are cross-checked against HiGHS, and are
replayed by the independent checker.

## Background

* A. Lucas, "Ising formulations of many NP problems", Front. Phys. 2:5 (2014), arXiv:1302.5843.
* A. Montañez-Barrera et al., "Unbalanced penalization: a new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms", Quantum Sci. Technol. 9 (2024), arXiv:2211.13914.
* J.-G. Liu, L. Wang, P. Zhang, "Tropical tensor network for ground states of spin glasses", Phys. Rev. Lett. 126, 090506 (2021), arXiv:2008.06888.
* J.-G. Liu, X. Gao, M. Cain, M. D. Lukin, S.-T. Wang, "Computing solution space properties of combinatorial optimization problems via generic tensor networks", SIAM J. Sci. Comput. 45, A1239 (2023), arXiv:2205.03718.
* A. Abbas et al., "Challenges and opportunities in quantum optimization", Nat. Rev. Phys. (2024), arXiv:2312.02279.