Metadata-Version: 2.4
Name: polyblocks
Version: 0.1.0
Summary: Solvers for global monotonic optimisation problems
Author: Ahmed Rashwan
Author-email: Ahmed Rashwan <ar3009@bath.ac.uk>
License-Expression: MIT
Requires-Dist: numba>=0.65.1
Requires-Dist: numpy>=2.2.6
Requires-Python: >=3.10
Project-URL: Homepage, https://github.com/RashwanA/polyblocks
Description-Content-Type: text/markdown

Polyblocks
=============

This package provides a set of solvers for monotonic optimisation problems, which take the general form:

$$
\begin{aligned}
\max_{x \in \mathbb{R}^n} \quad & f(x) \\
\text{s.t.} \ \quad & x_l \le x \le x_u \\
& g(x) \le 0 \\
& h(x) \ge 0
\end{aligned}
$$

where $f$, $g$, and $h$ are non-decreasing in each coordinate.
This covers a broad class of non-convex problems, including polynomial programming along with many radio resource allocation problems in communications.

Solvers are built around the **Polyblock Outer-approximation (POA)** algorithm: a branch-and-bound algorithm which iteratively refines a rectangular outer-approximation of the solution space.
Full details are available in the accompanying paper: **LINK**

## Installation

```bash
pip install polyblocks
```

or, for local development:

```bash
git clone https://github.com/RashwanA/polyblocks.git
cd polyblocks
pip install .
```

## Solvers

The package includes three built-in solvers: `BasePOA`, `BalancedPOA`, and `TreePOA`.
Of these `TreePOA` typically has the best empirical performance as it uses an efficient tree-based representation of the solution space.
All solvers implement the common `ABPolyblock` interface, which exposes a set of subroutines used by the POA algorithm.
Users may also define custom solvers by implementing this interface.

## Usage

Each solver is called via its `solve` classmethod, which takes the objective, the bounding box, and oracles for querying feasibility.

Ball optimisation example:

```python
from polyblocks import TreePOA

# maximise 3x + 4y
# subject to x^2 + y^2 <= 1

def obj(x):
    return x @ [3, 4]

def ub_oracle(x):
    return (x ** 2).sum(-1) <= 1

sol = TreePOA.solve(
    obj=obj,
    ub_oracle=ub_oracle,
    x_l=(0., 0.),
    x_u=(1., 1.),
)

print(f"status={sol.status}, obj={sol.obj:.2f}, x={sol.x.round(2)}")
```

Geometric programming example:

```python
from polyblocks import TreePOA

# maximise x y z
# subject to x (y + z) <= 4,
#            y z <= 4,
#            x, y, z ∈ [0, 4]

def obj(x):
    return x.prod(1)

def ub_oracle(x):
    cons1 = x[:,0] * (x[:,1:].sum(1)) <= 4.
    cons2 = x[:,1:].prod(1) <= 4.
    return cons1 * cons2

sol = TreePOA.solve(
    obj=obj,
    ub_oracle=ub_oracle,
    x_l=(0., 0., 0.),
    x_u=4.,             # bounds are broadcast
    verbose_gap=10,     # print progress every 10 iterations
)
print(f"status={sol.status}, obj={sol.obj:.2f}, x={sol.x.round(2)}")
```

Objectives and oracles are expected to accept batched inputs of shape `(num_points, dim)`.
