# Gap-gradient methods for solving generalized mixed integer inverse optimization: an application to political gerrymandering

arXiv: https://arxiv.org/abs/2406.09457 · HTML: https://mlsanity.com/paper/2406.09457/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jun 2024.

## Built on by (most cited first, 1 of 1)

- [Uncovering expert objectives in production planning via inverse optimization: An industrial case study](https://mlsanity.com/paper/2608.07398/) (2026)

## Abstract (arXiv)

Inverse optimization has received much attention in recent years, but little literature exists for solving generalized mixed integer inverse optimization. We propose a new approach for solving generalized mixed-integer inverse optimization problems based on sub-gradient methods. We characterize when a generalized inverse optimization problem can be solved using sub-gradient methods and we prove that modifications to classic sub-gradient algorithms can return exact solutions in finite time. Our best implementation improves solution time by up to 90% compared to the best performing method from the literature. We then develop custom heuristic methods for graph-based inverse problems using a combination of graph coarsening and ensemble methods. Our heuristics are able to further reduce solution time by up to 52%, while still producing near-optimal solutions. Finally, we propose a new application domain - quantitatively identifying gerrymandering - for generalized inverse integer optimization. We apply our overall solution approach to analyze the congressional districts of the State of Iowa using real-world data. We find that the accepted districting marginally improves population imbalance at the cost of a significant increase in partisan efficiency gap. We argue that our approach can produce a more nuanced data-driven argument that a proposed districting should be considered gerrymandered.