# Solving 0-1 Integer Programs with Unknown Knapsack Constraints Using Membership Oracles

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 64 references that are in the map.
- First posted on arXiv 23 May 2024.

## Builds on (most cited first, 12 of 12)

- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Complexity Theoretic Limitations on Learning Halfspaces](https://mlsanity.com/paper/1505.05800/) (2015)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Inverse Optimization: Theory and Applications](https://mlsanity.com/paper/2109.03920/) (2021)
- [Efficient Learning of Linear Separators under Bounded Noise](https://mlsanity.com/paper/1503.03594/) (2015)
- [Optimization with Constraint Learning: A Framework and Survey](https://mlsanity.com/paper/2110.02121/) (2021)
- [Efficient Convex Optimization with Membership Oracles](https://mlsanity.com/paper/1706.07357/) (2017)
- [Active Learning: Problem Settings and Recent Developments](https://mlsanity.com/paper/2012.04225/) (2020)
- [A PTAS for Agnostically Learning Halfspaces](https://mlsanity.com/paper/1410.7050/) (2014)
- [Boosting Combinatorial Problem Modeling with Machine Learning](https://mlsanity.com/paper/1807.05517/) (2018)
- [Active Information Acquisition for Linear Optimization](https://mlsanity.com/paper/1709.10061/) (2017)
- [A Simple Method for Convex Optimization in the Oracle Model](https://mlsanity.com/paper/2011.08557/) (2020)

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

- [Mathematical Programming Algorithms for Convex Hull Approximation with a Hyperplane Budget](https://mlsanity.com/paper/2407.17341/) (2024)

## Abstract (arXiv)

We consider solving a combinatorial optimization problem with unknown knapsack constraints using a membership oracle for each unknown constraint such that, given a solution, the oracle determines whether the constraint is satisfied or not with absolute certainty. The goal of the decision maker is to find the best possible solution subject to a budget on the number of oracle calls. Inspired by active learning for binary classification based on Support Vector Machines (SVMs), we devise a framework to solve the problem by learning and exploiting surrogate linear constraints. The framework includes training linear separators on the labeled points and selecting new points to be labeled, which is achieved by applying a sampling strategy and solving a 0-1 integer linear program. Following the active learning literature, a natural choice would be SVM as a linear classifier and the information-based sampling strategy known as simple margin, for each unknown constraint. We improve on both sides: we propose an alternative sampling strategy based on mixed-integer quadratic programming and a linear separation method inspired by an algorithm for convex optimization in the oracle model. We conduct experiments on classical problems and variants inspired by realistic applications to show how different linear separation methods and sampling strategies influence the quality of the results in terms of several metrics including objective value, dual bound and running time.