Selecting an effective cutting plane to minimize the branch-and-cut tree size is a critical challenge in the branch-and-cut algorithm. Recent advancements have employed a data-driven approach to select optimal cutting planes from a parameterized family, aimed at reducing the branch-and-bound tree size for a given distribution of integer programming instances. We extend this idea to the selection of the best cut generating function (CGF) from a parameterized family of facet-defining valid functions for the infinite group relaxation problem, with Gomory's mixed-integer (GMI) cuts as a particular instance. We provide rigorous sample complexity bounds for the selection of an effective CGF from these families for any specified distribution under some mild assumptions. Our empirical results show that the selected CGF can outperform the best GMI cut for certain synthetic distributions. Additionally, we explore the sample complexity of using neural networks for instance-dependent CGF selection.

The p-median problem is a classical discrete location problem and is equivalent to the well-known k-medoids problem in the unsupervised clustering literature. The aim is to select p centers while minimizing the sum of distances from each customer to its nearest center. Recent advancements in solving the p-median and related problems have successfully leveraged Benders decomposition methods. In order to reduce the number of variables and possibly the number of Benders cuts in these models, it is possible to aggregate distance variables corresponding to customers. We propose to partially aggregate the distance variables based on an initial solution: aggregation occurs only when the corresponding customers are assigned to the same center in the initial solution. In addition, we propose a set of tailored valid inequalities for these aggregated variables. Initial experiments indicate that our model, post-initialization, provides a stronger lower bound, thereby accelerating the resolution of the root node. Furthermore, this approach seems to positively impact the branching procedure, leading to an overall faster Benders decomposition method.

We consider a variant of the knapsack problem in which the knapsack constraint is unknown and the decision maker only has access to a membership oracle that, given a solution, determines whether the solution is feasible or infeasible with absolute certainty. The goal of the decision maker is to find a nearly-optimal feasible solution and a knapsack constraint that, used in place of the unknown one in the knapsack model, yields such a solution. We assume that the oracle can be queried no more than a pre-defined number of times.

The problem is of interest both in the context of pure linear constraint interactive learning and for its applications in business and educational settings in which respecting a limit on the query budget and ensuring interpretability of the solution are critical concerns.

In our work we tackle the problem relying on an algorithmic structure inspired by SVM-based active learning. In particular, we show how to adapt from literature an algorithm that iteratevely applies SVM for linear separation and Simple Margin as a query strategy. We propose two alternative approaches for linear separation, the first one based on finding the Chebyshev center of the version space relative to the candidate separating hyperplanes and the other adapted from an algorithm for interactive convex optimization based on separation oracle. In addition, we introduce an alternative query strategy also based on the notion of version space.

We show how different separation methods and query strategies influence the quality of the result, in terms of objective value and constraint approximation. As a variant of the pure knapsack problem, we consider the composition of a college study plan in which the unknown constraint models time budgeting and the objective is to maximize the number of acquired credits. The student acts as the oracle and interacts with a system that proposes combinations of courses to attend that respect known dependencies, e.g. prerequisites. We conduct additional experiments to show how the proposed algorithms perform in this setting.