Combinatorial Auction WDP Solver

Experiments on engineering faster exact solvers for the Winner Determination Problem (WDP) in combinatorial auctions. Investigates how preprocessing and heuristic branching guidance affect Gurobi's branch-and-bound performance across random and CATS-inspired instance families.

Results

Bundle-size branching guidance against Gurobi's default, median of 10 seeds per configuration:

Items	Best speedup	Default	Guided	Configuration
20	1.01x	0.019s	0.019s	20 bidders, 10 bids
30	1.21x	0.133s	0.110s	10 bidders, 20 bids
40	5.02x	1.216s	0.242s	20 bidders, 20 bids
50	11.32x	6.296s	0.556s	40 bidders, 20 bids
60	6.92x	3.617s	0.523s	40 bidders, 10 bids

The guidance is inert on small instances, where solve times are already milliseconds. It pays off in a middle band of hard-but-tractable instances, peaking at 11x on 50 items. On the largest, densest instance tested (60 items, 40 bidders, 20 bids) it is slower than the default -- 16.5s against 14.8s -- so the effect is not monotone in problem size.

Full per-configuration numbers are in results/figures/table1_density_summary.csv.

Repository layout

src/
  data_types.py          # Bid and AuctionInstance dataclasses
  generate.py            # Random XOR auction generator
  generate_cats.py       # CATS Arbitrary / Paths / Regions generators
  model.py               # Gurobi MIP model builder (XOR-WDP formulation)
  preprocess.py          # Bid deduplication, dominance removal, decomposition
  solve.py               # solve_instance, solve_lp_relaxation, solve_by_decomposition
  heuristics.py          # bundle_size and conflict_degree priority scorers
  mip_start.py           # Greedy warm-start builder
  features.py            # Conflict graph construction and statistics
  experiment.py          # run_heuristic_comparison (dispatches to all generators)
  analysis.py            # Figure and table generation (importable library)

run_density_sweep.py     # Main branching heuristic sweep (20–60 items, 3 methods)
run_preprocessing_sweep.py  # Preprocessing / MIP-start / decomposition comparison
run_cats_sweep.py        # CATS Arbitrary sweep (40–100 items, 3 methods)
run_analysis.py          # Regenerate all figures and summary tables

results/
  density_sweep_raw.csv
  preprocessing_experiment_raw.csv
  cats_raw.csv
  figures/               # Generated figures (PDFs) and summary tables (CSVs)

report.tex / report.pdf  # Final report
refs.bib                 # BibTeX references

Requirements

• Python 3.10+
• Gurobi 13.x with a valid licence (gurobipy)
• pandas, matplotlib, numpy

pip install pandas matplotlib numpy gurobipy

Reproducing experiments

Run scripts from the repository root. Each script saves results to results/.

# Main branching heuristic sweep (~5 min)
python run_density_sweep.py

# Preprocessing / MIP-start / decomposition comparison (~2 min)
python run_preprocessing_sweep.py

# CATS Arbitrary sweep (~10 min)
python run_cats_sweep.py

# Regenerate all figures and summary tables
python run_analysis.py

Figures are written to results/figures/. Pre-computed CSVs are included so run_analysis.py can be run without re-solving.

Methods

Method	Description
default	Gurobi defaults, no preprocessing
bundle_size	Branch priorities proportional to bundle size
conflict_degree	Branch priorities proportional to conflict-graph degree
default_mip_start_bundle	Default + greedy warm start (sorted by bundle size)
decomposition_default	Solve each conflict-graph component independently

Key results

• Bundle-size priority achieves up to 11× speedup on medium-difficulty random XOR instances (50 items, 40 bidders, 20 bids each)
• At the hardest tested configuration (60 items, 40 bidders, 20 bids), heuristics regress slightly — static priority orderings are insufficient when all bids are maximally conflicted
• CATS Arbitrary instances show consistent but modest gains (1.1–1.3×); CATS Paths and Regions have near-integral LP relaxations and are solved trivially at the root node regardless of method