SIGIR Permutations — Rank Optimization

Code and experiments for rank optimization via permutations: maximize a weighted objective (e.g. revenue) over rankings while satisfying lower-bound constraints on other metrics. Supports multiple solvers: ILP (HiGHS, MOSEK), PermR (swap-based heuristic), and GA (genetic algorithm with pymoo).

Project structure

├── data/
│   └── example.csv          # Input: per-query metrics (f0–f6) as list columns
├── rank_optimizer/          # Core solver library
│   ├── abstract_solver.py   # Base Solver, lower bounds, visibility weighting
│   ├── perm_r_solver.py    # PermR (PermRSolver)
│   ├── solver_config.py    # BaseSolverConfig, PermRSolverConfig
│   └── lower_bound.py      # LowerBound dataclass
├── run_HiGHS.ipynb         # Run ILP with HiGHS (SciPy)
├── run_MOSEK.ipynb         # Run ILP with MOSEK (requires license)
├── run_GA.ipynb            # Run genetic algorithm (pymoo)
├── run_PermR.ipynb         # Run PermR — iterations / time variants
├── analysis.ipynb          # Aggregate results, tables, plots
├── results/
│   ├── GA/                 # GA results (time_0.01.csv … time_1.0.csv)
│   ├── ILPs/               # HiGHS.csv, MOSEK/threads_*.csv
│   └── PermR/              # iterations_*.csv (e.g. iterations_750.csv)
├── requirements.txt
└── README.md

Setup

1. Clone and create a virtual environment

   python -m venv venv
   source venv/bin/activate   # or `venv\Scripts\activate` on Windows

2. Install dependencies

   pip install -r requirements.txt

   For GA runs you also need:

   pip install pymoo tqdm

3. MOSEK (optional)
   To use run_MOSEK.ipynb, install MOSEK and set a license. The notebook looks for mosek.lic in the project root. Set MOSEKLM_LICENSE_FILE to the path of your license file if needed.

Data format

• data/example.csv
  • query_id, serp.logcat, and metric columns f0, f1, f2, f3, f4, f5, f6.
  • Each metric column holds a string representation of a list of floats (one value per rank position).
  • f0 is the goal (e.g. revenue); the solvers maximize position-discounted f0 (visibility 0.97^position) subject to lower bounds on the other metrics.

Running experiments

• HiGHS (ILP): Open run_HiGHS.ipynb, set MAX_TIME, run all. Output: results/ILPs/HiGHS.csv.
• MOSEK (ILP): Open run_MOSEK.ipynb, ensure MOSEK license is set, set thread count NUM_THREADS and time limit MAX_TIME, run. Output: results/ILPs/MOSEK/threads_*.csv.
• GA: Open run_GA.ipynb, set MAX_TIME (seconds per query), POP_SIZE, N_JOBS, run. Output: results/GA/time_<MAX_TIME>.csv.
• PermR: Open run_PermR.ipynb, set NUM_ITERATIONS, run. Output: results/PermR/iterations_*.csv.

Results CSVs contain columns such as prod_f0, prod_norm_f0, solver-specific columns (e.g. GA_0.5_f0, GA_0.5_norm_f0, GA_0.5_time, or PermR_750_f0, PermR_750_time), and metric columns (e.g. PermR_750_f1, …).

Analysis

• analysis.ipynb loads result CSVs from results/, computes improvement vs. production (e.g. revenue uplift %) and timing (mean, std, max), and builds tables/plots for the paper (e.g. PermR iteration sweep, GA time limits, ILP solvers).

Solver overview

Method	Notebook	Description
HiGHS	run_HiGHS.ipynb	MILP via cvxpy + SciPy (HiGHS); no license.
MOSEK	run_MOSEK.ipynb	MILP via cvxpy + MOSEK; multi-thread, time limit; needs license.
GA	run_GA.ipynb	Genetic algorithm (pymoo): permutation sampling, order crossover, inversion mutation; time-limited per query.
PermR	run_PermR.ipynb	Swap-based heuristic (rank_optimizer.PermRSolver): adjacent swaps, constraint repair; configurable iterations.

License

See repository and paper for license and citation details. MOSEK is subject to its own license terms.