Actively Learning Combinatorial Optimization Using a Membership Oracle
<|reference_start|>Actively Learning Combinatorial Optimization Using a Membership Oracle: 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.<|reference_end|>
@article{messana2024actively,
    title={Actively Learning Combinatorial Optimization Using a Membership Oracle},
    author={Rosario Messana, Rui Chen, Andrea Lodi},
    journal={arXiv preprint arXiv:2405.14090},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.14090},
    primaryClass={cs.LG math.OC}
}