NB1P_swaps

ILP formulation (Gurobi) of NB1P: find a column permutation of a matrix M (entries 0/1, or 0/1/2 with 2 as a joker) that minimizes z(π), the number of internal zero blocks — maximal runs of 0s flanked by 1s on both sides. All optimal permutations are pulled out of Gurobi's solution pool.

This matches the definition and model used in report/report_fr.tex (equivalence between NB1P and reversal/swap distance, bounds, and a section describing the ILP variables directly).

A note on the name: despite NB1P_swaps, this code doesn't actually build a step-by-step sequence of swaps the way NB1P_reversals builds a sequence of reversals (there's no time-indexed variable here). It solves the relaxed version directly — find the best π, full stop — which the report calls "Problem (A)". The connection to composed swaps/reversals ("Problem (B)") is proven equivalent in the report, but isn't a separate ILP in this repo.

Install

pip install -e .

Needs numpy and gurobipy (Gurobi license required).

Quick example

from NB1P_swaps import solve_NB1P_swaps
 
M = [
    [1, 0, 1, 1, 1],
    [0, 0, 1, 1, 1],
    [0, 1, 1, 0, 0],
    [1, 1, 0, 0, 0],
]
 
success, perms, z_star = solve_NB1P_swaps(M, verbose=False)
print(f"z* = {z_star}, {len(perms)} optimal permutations")

Gives z* = 1, 20 distinct optimal permutations. On the joker matrix from NB1P_reversals's example (5 genes, 4 loss events) this returns z* = 0, consistent with the global bound computed there.

API

solve_NB1P_swaps(matrix, verbose=False, pool_solutions=2_000_000_000, use_indicators=False) is the only entry point, returns (success, permutations, z_star).

Layout

NB1P_swaps/
  variables.py     permutation variables (xi, pos)
  gaps.py          z(pi) counted as internal zero BLOCKS, joker-aware
  constraints.py   old per-position counting (Big-M / indicator) — no longer
                   called by solve_NB1P_swaps, kept around for reference
  extraction.py    dedups solutions coming out of the Gurobi pool
  display.py       readable printout of one solution
  solver.py        solve_NB1P_swaps, wires everything together
examples/
  run_example.py
report/
  report_fr.tex / .pdf   theory + section 2 on the ILP variables