Metadata-Version: 2.5
Name: pymdls
Version: 0.2.0
Summary: Multi-directional local search with user-supplied moves
Project-URL: Homepage, https://github.com/nsushant/ORBITAL/tree/MDLS
Project-URL: Repository, https://github.com/nsushant/ORBITAL/tree/MDLS
Project-URL: Documentation, https://github.com/nsushant/ORBITAL/blob/MDLS/user_guide.md
Project-URL: Issues, https://github.com/nsushant/ORBITAL/issues
Project-URL: Changelog, https://github.com/nsushant/ORBITAL/blob/MDLS/CHANGELOG.md
Author: Sushanta Nigudkar
License: MIT
License-File: LICENSE
Keywords: local search,mdls,metaheuristics,multi-objective optimisation,multi-objective optimization,pareto
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Requires-Dist: numba>=0.57
Requires-Dist: numpy>=1.23
Provides-Extra: dev
Requires-Dist: build>=1.0; extra == 'dev'
Requires-Dist: pytest>=7.0; extra == 'dev'
Requires-Dist: twine>=5.0; extra == 'dev'
Provides-Extra: examples
Requires-Dist: matplotlib>=3.6; extra == 'examples'
Description-Content-Type: text/markdown

# mdls

`mdls` is a small, decorator-based implementation of **multi-directional local
search** (MDLS) for multi-objective optimisation. You supply an `evaluate`
function and one move per objective; the library owns the non-dominated
archive, selection, budgets and statistics.

The method follows Tricoire (2012). This package is a
generalised, reusable version of the MDLS engine used in
[ORBITAL](https://github.com/nsushant/ORBITAL/tree/MDLS).

## Install

```bash
pip install pymdls
```

The distribution is named `pymdls`; the import package is `mdls`, so the code
below always uses `from mdls import ...`.

Python 3.10 or newer is required. NumPy and Numba are installed automatically.

For the example's plotting command, install the extra:

```bash
pip install "pymdls[examples]"
```

## Quick start

```python
import numpy as np

from mdls import MDLS, move


def evaluate(x, inst):
    """MDLS minimises; g <= 0 means feasible."""
    return -(inst["obj"] @ x), [inst["weight"] @ x - inst["cap"]]


def _toggle(x, inst, rng, k, n_toggle):
    """One attempt: flip items, keep the copy if objective k improves."""
    y = x.copy()
    flip = rng.choice(x.size, size=n_toggle, replace=False)
    y[flip] = ~y[flip]
    if inst["weight"] @ y > inst["cap"]:
        return None
    return y if inst["obj"][k] @ y > inst["obj"][k] @ x else None


@move(improves=0, attempts=8)
def toggle_0(x, inst, rng, n_toggle=2):
    return _toggle(x, inst, rng, 0, n_toggle)


@move(improves=1, attempts=8)
def toggle_1(x, inst, rng, n_toggle=2):
    return _toggle(x, inst, rng, 1, n_toggle)


rng = np.random.default_rng(0)
n = 20
inst = {"obj": rng.random((2, n)), "weight": rng.random(n), "cap": 0.3 * n}
moves = [toggle_0(n_toggle=2), toggle_1(n_toggle=2)]
search = MDLS(evaluate, moves=moves, instance=inst)

res = search.run([np.zeros(n, dtype=bool)], max_eval=500, seed=0)
print(res.summary())
print(res.objectives)
```

## What the library provides

- **Archive** of feasible, non-dominated solutions with a relative tolerance,
  duplicate rejection and dominated-point eviction.
- **Move contract**: a move is one improving attempt, optionally retried up to
  `attempts` times by the `@move` decorator.
- **Balanced search**: every iteration applies one sampled move per objective
  from the same archived base solution.
- **Budgets**: stop on iterations (`max_iter`), evaluations (`max_eval`,
  including initial solutions) or wall-clock time (`time_limit`).
- **Statistics**: per-move counts of calls, no-moves, non-descents, infeasible
  results, dominated results, accepted results and time.
- **Large-archive index**: past 8192 archived points the archive switches
  automatically to an exact Numba dominance index, so fronts with many
  objectives keep growing without a quadratic scan. Results are identical to
  the scan.
- **Extension points**: `is_feasible`, `selection`, `copy_solution`, and the
  `select`, `offer`, `copy` and `on_iteration` hooks.

Moves are ordinary functions and stay readable; Numba is optional but is used
inside the library's dominance scan and large-archive index, and can be used
inside your own moves.

## Examples

The repository includes a bi-objective 0/1 knapsack:

```bash
python examples/knapsack.py run      # one search, writes front.csv
python examples/knapsack.py plot     # fronts for up to four seeds, writes front.png
```

The full tutorial, including the move contract and every option, is in
[`user_guide.md`](https://github.com/nsushant/ORBITAL/blob/MDLS/user_guide.md).

## Testing

The test suite lives in the repository, so clone it first (the `MDLS` branch):

```bash
git clone https://github.com/nsushant/ORBITAL.git
cd ORBITAL
git switch MDLS
pip install -e ".[dev,examples]"
python -m pytest
```

`.[dev]` alone is enough to run the tests; the `examples` extra is only needed
for `python examples/knapsack.py plot`.

## License

MIT. See [LICENSE](LICENSE).

## Citation

If you use this package in academic work, cite the MDLS paper and optionally
the software itself (see `CITATION.cff`):

> Tricoire, F. (2012). Multi-directional local search. *Computers &
> Operations Research*, 39(12), 3089–3101.
> https://doi.org/10.1016/j.cor.2012.03.010
