We consider solving a combinatorial optimization problem with an unknown
linear constraint using a membership oracle that, given a solution, determines
whether it is feasible or infeasible 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 based on Support Vector
Machines (SVMs), we adapt a classical framework in order to solve the problem
by learning and exploiting a surrogate linear constraint. The resulting new
framework includes training a linear separator 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, one can consider using SVM as a linear classifier and the
information-based sampling strategy known as Simple margin. 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 the pure
knapsack problem and on a college study plan problem from the literature to
show how different linear separation methods and sampling strategies influence
the quality of the results in terms of objective value.

使用成员预测器解决未知线性约束的组合优化问题，以学习和利用替代线性约束的新框架，并通过采样策略和解决 0-1 整数线性规划来选择需要标记的新点，以提高结果的质量。