Learning Cuts via Enumeration Oracles
Authors: Daniel Thuerck
Boro Sofranac
Marc Pfetsch
Sebastian Pokutta
Venue: NeurIPS 2023 poster (2023)
Keywords: Integer Programming
Cutting Planes
Optimization

Abstract: Cutting-planes are one of the most important building blocks for solving large-scale integer programming (IP) problems to (near) optimality. The majority of cutting plane approaches rely on explicit rules to derive valid inequalities that can separate the target point from the feasible set. Local cuts, on the other hand, seek to directly derive the facets of the underlying polyhedron and use them as cutting planes. However, current approaches rely on solving Linear Programming (LP) problems in order to derive such a hyperplane. In this paper, we present a novel generic approach for learning the facets of the underlying polyhedron by accessing it implicitly via an enumeration oracle in a reduced dimension. This is achieved by embedding the oracle in a variant of the Frank-Wolfe algorithm which is capable of generating strong cutting planes, effectively turning the enumeration oracle into a separation oracle. We demonstrate the effectiveness of our approach with a case study targeting the multidimensional knapsack problem (MKP).

Learning Cuts via Enumeration Oracles
Daniel Thuerck
Boro Sofranac
Quantagonia
Quantagonia
Bad Homburg. Germany
Bad Homburg. Germany boro sof www.rr@uannttagnniaaccm
daniel. thwercck@quattaggmie..oo
Marc E. Pfetsch
Sebastian Pokutta
Department of Mathematics, TU Darmstadt
Zuse Institute Berlin and TU Berlin Berlin, Germnany
Darmstadt, Germany
pfetschhmatthematik wtwp:eatttatttttttteeeeeeeeeeeee tu-darmstadt.de
pokuttaćzib.de
Abstract
Cutting-planes of the most important building blocks for solving large- scale integer programming (IP) problems to (near) optimality. The majority of cutting plane approaches rely explicit rules to derive valid inequalities that separate the target point from the feasible set. Local cuts, on the other hand, seek directly derive the facets of the underlying polyhedron and use them cutting planes. However, current approaches rely on solving Linear Programming (LP) problems in order derive such hyperplane. In this paper, we present a novel generic approach for learning the facets of the underlying polyhedron by accessing it implicitly via an enumeration oraele reduced dimension. This is achieved by embedding the oracle in a variant of the Frank-Wau algorithm which is capable of generating strong cutting planes, effectively turning the enumeration oracle into a separation oracle. We demonstrate the effectiveness of our approach with case study targeting the multidimensional knapsack problem (MKP).
Introduction
In this paper, we deal with integer programs (IP)
max {(e, x)) As b, xEZ")
(IP)
where A Qmxn b QTh and Q" Let E R" Ar < b} be the underlying polyhedron and its integer hull P, = conv(Pnz)) We restrict attention to the case in which all variables are required be integral, as the methods we will propose are more readily applicable this case, but the general idea works for mixed-integer programs (MIP) as well.
Solving IPs is -ar-hard in general, however, surprisingly fast algorithms exist in practice [1, 50]. The most successful approach to solving IPs is based on the branch- ancehhh-nd-aa and-bound algorithm and its extensions. This algorithm involves breaking down the original problem into smaller subproblems that are easier to solve through a process known as branching. By repeatedly branching on subproblems, search tree is obtained. The bounding step involves computing upper bounds for subproblems and pruning suboptimal nodes the tree in order to avoid enumerating exponentially many subproblems. Upper bounds are generally computed with the help of Linear Programming (LP) relaxations
max ((,, E P}.
(LP)
Because the integrality constraints are relaxed, optimal solutions of (LP) provide an upper bound for the original problem (IP).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Alternativll, cutting plane procedures iteratively solve LP-relaxations as long as the solution x" is not integral (and thus x² &f Pt). To remove these solutions x² from the relaxation's 's polyhedron, one adds cutting planes (or cuis) (n, S B with cutring planes or to determine that none exists is called the separation problem. The strongest cuts are those that define facer, i.e., the face Py n {a (a, x) = } has co-dimension 1 with respect to Pt. When the cutting plane method is combined with suuuch-and-bound the resulting algorithm is often called branch-and-con
Q", 3 E Q and x²) > B. The search for such
Gomory conducted foundational work in this field, demonstrating that pure cutting plane approaches can solve integer programs with rational data in finite number of steps without the need for branching [32, 33, 34].
Gomory's 's initial approach to cutting planes suffered from numerical difficulties at that time, prevent- ing pure cutting plane methods from being effective in practical applications. However, his proposed (Gomory) mixed integer (GMI) cuts are very efficient if combined with rranch-and-ooum (see the computational study in [11]) and still are one of the most important types of cutting planes used by contemporary solvers. As more GMI cuts are added to a problem, their incremental value tends to diminish. To address this issue, modern MIP and IP solvers use range of techniques to generate cuts, e.g., mixed-integer-rounding (MIR) inequalities [55], knapsack covers [26, 38], flow covers [39], fit-aadd-rroeed cuts [5]. {0, 3 ) J-Chvátal-Gomory cuts [22], and others.
Most cutting plane separation algorithms rely on fixed formulas to derive valid inequalities that separate the target point x" from the polyhedron Pt. An alternative approach is to directly seek to derive the facets of Py that separate the point x². Notice that while the facets of the polyhedron P are explicitly known from the problem definition, the facets of its integer hull P7 are unknown in general. While the facet-definin inequalities are intuitively the strongest cuts, they can be relatively expensive to explicitly compute, limiting their applicability in practice, Local cuts, a type of cutting planes that try to derive facets of Pr. approach this problem by deriving facets of Pi in a reduced dimension, and then lifting those cuts to obtain facets in the original dimension. In this paper, we will propose a new variant of the Frank- Wolfe algorithm with the goal of learning the (unknown) facets of P1 (or at least valid inequalities) in reduced dimension, which can then be lifted to the original dimension and be used as strong cutting planes. In our learning approach, the underlying polyhedron will only be accessed via algorithmically simple linear optimization oracle, in contrast to existing approaches, which also need to solve LPs.
1.1 Related Work
Local cuts have first been introduced as "Fenchel cuts" in Boyd [13, 14], who developed an algorithm to exactly separate inequalities for the knapsack polytope via the equivalence of separation and optimization. They were subsequently investigated extensively by Applegate et al. [3] for solving the traveling salesman problem (TSP). Buchheim et al. [20, 21] and Althaus et al. [2] adopted local cuts into their approaches for solving constrained quadratic 0-1 1 optimization problems and Steiner-tree problems, respectively. In [25], Chvátal et al. generalize the local cuts method to general MIP problems.
In the context of knapsack problems, after the aforementioned work of Boyd [13, 14], Boccia [12] introduced an approach based on local cuts, as stated by Kaparis and Letchford [47]', who further refined the algorithm. Vasilyev presented an alternative approach with application to the generalized assignment problem in [63], see also the comprehensive computational study conducted by Avella et al. in [4]. In [64], Vasilyev et al. propose new implementation of this approach, with the goal of making it more efficient. In [37], Gu presents an extension of the algorithm of Vasilyev et al. [64].
Existing works on the application of learning methods in solving IP (and more generally MIP) problems can in general be divided into two categories: learning decision strategies within the solvers, and learning heurisites to obtain feasible (primal) solutions. Examples of the former would be learning to select branching variables [6. 31, 48), learning to select branching nodes [41], learning to select cutting planes [61], learning to optimize the usage of primal heuristies [23, 42, 49]. A typical example of the latter case would be learning methods develop large neighborhood search (LNS) heuristics [28, 60, 59]. Additionally, a number of works in the literature have focused on learning
algorithms for solving specific IP problems [8, 44, 27, 51, 54, 56]. For a more detailed overview of using learning methods in IP, we refer the interested reader to [9].
We could not independently verify the claim as could not access Boccia's paper online.

---

1.2 Contribution
The contributions of this paper can be summarized as follows:
1. We present an efficient, LP-free separation framework that aims to learn local cuts for IPs through the solution of subproblems. We propose to use variant of the Frank- Woolfe [29] algorithm to solve the associated separation problem. The resulting framework is general and given the availability of suitable lifting method applicable any IP.
2. We propose a new, dynamic stopping criterion for the application of Frank-Wolfe to the separation problem at hand. This new criterion, derived by exploiting duality information, directly evaluates the strength of the resulting cut and thus dramatically decreases the number of iterations.
3. We illustrate the benefit of our approach in a case study for the multidimensional knapsack (MKP) problem, demonstrating its effectiveness. Our computational results show that embedding our method in the academic solver SCIP leads to 11% faster solving times on the instances solved to optimality, on average.
The rest of this paper is organized as follows: In Section 2, the fundamental framework of local cuts and required notation are introduced. Section 3 presents our approach for the LP-less generation procedure for local cuts. Section 4 demonstrates how the aforementioned framework can be applied to solve the multidimensional knapsack problem. Computational expr experiments are presented in Section 5. Finally, Section 6 summarizes conclusions and future work.
2 Local Cuts
To describe the idea of local cuts, assume that P R",, > O, is a polytope, i.e., bounded, and full-dimensional. Then one considers a small subproblem with underlying polytope P, which is usually an orthogonal projection of P onto lower-dimensional space. The polytope P is restricted to being non-empty and its dimension 0 < k S. ri is chosen small enough such that integer optimization problems over P can be solved efficiently in practice, for example, by enumeration. Consider a projection ã of the point to be separated x on R² The procedure tries to generate a valid cut (ā, < 3 with E Q 3 E Q such that (ā, .) > 3, i.e., it cuts off from P. This cut can be "lifted" to the original space, which yields a cut (a, x) S B that hopefully cuts off x²?²
The approach to generate (á, S 33, in the literature mentioned above, relies on the equivalence between optimization and separation [36] and can be very briefly explained follows. By the Minkowski- Weyl Theorem, we can express P as the convex hull of its vertex set V. Let 50 E P be an interior point. Then consider the LP
min by: Eer (f- - A
11
VEV
"E
The dual problem (D) is
max (ū, 3: (v, (300))330 SBVEEV (i (i- -", 11).
Let a, 33 be an optimal solution of (D). Then (ā.x) 3 is valid inequality for P, since by construction (v, ā) < 3 holds for all v e V and thus by convexity for all points in P. The objective enforces that this cut is maximally violated by I if the optimal value is positive.
Since P may have an exponential number of vertices, problem (D) can be solved by a column generation algorithm (or cutting plane algorithm in the primal). In each iteration, one needs to solve the following pricing problem for the current point (á, 8): Decide whether there exists V with (u, > 3. This can be done by maximizing á over the subproblem P. i.e., one can use linear optimization oracle for the subproblem. This subproblem can contain integrality constraints. thereby requiring. again, IP techniques. Note that the most interesting case where we operate on integer
"The idea local cuts often confused with inft-and-p -ff-jee-rrojeet cuts, as the two methods share some high-level ideas, such as exploring solutions in a different space and using projection. However, they are quite different. and- project methods first lift, then generate cut and project back, while local cuts first project and then lift the cut. Moreover, the subproblems generate cuts are signficiantly different.
3

---

hulls, i.e. P= Pı to generate cuts for P Pl. .. In this way, local cuts can help solving an integer optimization problem over P. Hence, in the following sections, any reference to P. P holds for the integer case as well and our case study illustrates exactly that.
As mentioned above, the strongest cutting planes are those that define facets. The tilting method by Applegate et al. [3] produces such facet. Buchheim al. [20] introduced different formulation that automatically produces a facet. Chvátal et al. [25] developed a formulation for general MIPs using linear optimization oracles. All three approaches use sequence LPs their heart; either for tilting a plane or through a column-generation procedure.
3 Learning Strong Cuts from Enumeration
The local cuts framework, applicable to general IPs, relies on a sequence of three operators: SEP, FACET and LIFT. SEP refers to a separation oracle separating the projected point è from P that returns a separating cut (ā, x² S 3 (or certifies that P). FACET further refines the cut until represents a facet of P and lastly, LIFT transforms the resulting facet into the space of P such that it separates x² from P with high probability. In some variants of local cuts, SEP and FACET may be combined into one step similar to [20], whereas [25], the tilting process is a separate, concrete embodiment of FACET. Note that that facets of the subproblem, when lifted, result in the strongest cuts. In practice, it is often sufficient to find good valid inequalities of P. As mentioned before, the method
original approach for local cuts through duality requires an expensive polumm-generaan which is based on LPs. In this section, we derive alternative and LP-Iess approach.
The general idea of our new approach is sketched in Figure 1: Given a point ă E R² that we intend to separate from P. we solve the following optimization problem:
y argmin f(y),
(Separation)
yEP
with (w) = : =||2. Observe that this effectively the projection of onto P under the e--nrrm and that V5((y) = (y - ū)..
We solve (Separation) with a suitable variant of the Wolfe algorithm. The Frank- Wolfe algorithm [29] (also called: Conditional Gradients [53]) is a method to minimize a smooth convex function f over compact convex domain P by only relying on a First-order Oracle (FO) for i.i... given a point æ the oracle returns ff(x) (and potentially f(x)) as well as a Linear Minimization Oracle (LMO) ("oracle" for the remainder of this paper), i.e., given objective vector c, the oracle returns V E argmin zg e (c, x²). The original Frank- Wolfe algorithm, provided with step sizes " > O, iteratively calls the LMO to determine U/- + argmin (V fy()), v) and updates the iterate to Yt+1 Yt + (1/2 v1). There are various step-size strategies for Yt, but the actual choice is 2
irrelevant for the discussion here; a common choice is 7 = 842'
The main advantages of using Frank- are (1) if there is LP-less oracle, valid inequalities can be generated without solving LPs, (2) the computational overhead of the Frank-Wolfe steps compared to calls to the LMO are very light and, finally, (3) as we will show, for the case of (Separation), we can derive a new dynamic stopping criterion that can dramatically reduce the number of iterations. Note that we are not guaranteed to end up with facets, especially when the method is stopped early, however, valid inequalities that are "close" to being a facet can still serve as strong cutting planes.
For our problem minimizing f. the Frank-Wold algorithm iteratively calls the oracle and updates its current iterate through a convex combination of the previous iterate and oracle's solution vertex. Step by step, the solution is thus expressed through a convex combination of vertices in P as shown in Figures la- Ic. At convergence, the hyperplane fV)(()), 2 (Vf()") (("))""))))))))))) forms the desired cut.
3.1 Separation via Conditional Gradients
Let y² E P be an optimal solution to (Separation) and let x E S be arbitrary. By convexity, follows that 0 < referred to as Frunk- Wolfe gap (at æ). Moreover, the following lemma holds, which direct consequence of the first-order optimality condition.
< (Vf()), x y²) < (ax - v) and the last quantity

---

11
f1
21
f(3)
V. [iffe+)))
1/k
P
P
(a)
(b)
(c)
Figure 1: We propose the following approach to separate a fractional point from a full-dimensional
polytope P: We solve min, yeP f(y) := blly i||2 i.e., the L2 projection of I onto P. through variant of the Frank- Wolfe algorithm. Starting from a random vertex (a), the algorithm iteratively computes the gradient of f at the current iterate yı and uses oracle to solve a linear integer optimization problem over P. building up active set of vertices that form iterates through a convex combination (b). At convergence (c) optimal solution y yk++i together with its gradient forms a cut that induces facet of P: ()(()++)) T x 2 f()++s) yk+t (except for degenerate cases).
Lemma (First-order Optimality Condition). Let y¹' E P. Then y² is an optimal solu- tion to min yep f(y) if and only if (VI(y"). w) S 0 for all v E (and in particular max (V) - -) -
Note that in the constrained case, does not necessarily hold that Vf( = 0, if y an optimal solution. In fact, if the å that we want to separate is not contained in P, then f(v") > 0 and Vf((") o 0 since y" will lie on the boundary of P.
turns out that we can naturally use an optimal solution y" E P to (Separation) to derive a separating hyperplane. By Lemma 1:
(VF())
(Cut)
which holds for all v E P. Moreover, ā $ P. then (Cut) is violated by I. i.e., (Vf(""). > (Vf(v"), ž). since (Vf(""), 2) f(y") f()) = f(y") O.
Usually, however, we do not solve Problem (Separation) exactly, but rather up to some accuracy. In fact, the Frank Wolfe algorithm often the Frank-Wolfe gap stopping criterion, minimizing the function until for some iterate y, it holds max, (V (3x), Dt - v) S & for some target accuracy e; note that the Frank-Wolfe gap converges with the primal gap (see e.g.. [46]). Given an accuracy ε >> O, we obtain the valid inequality
rate (up small constant factors) as the
(Vi())), v1) < (V fy()... v),
(approxCut)
for all v E P. which also separates t from P if far from P, i.e. 111 al| VE:
(v.)) V: 2 f(,) f() 2 f(y") - 0. The accuracy chosen depending on the application; see also [17] for sensitivity analysis for conditional gradients.
3.1.1 A dynamic stopping criterion
turns out, however, that in our case of interest, the above can be significantly improved by exploiting duality information. This allows us not only to stop the algorithm much earlier, but we also obtain separating inequality directly from the associated stopping criterion and duality information.
The stopping criterion is derived from a few simple observations, which provide a new characterization of a point ã that can be separated from P. Our starting point is the following standard expansion. Let v E be arbitrary and let y/ be an iterate from above. Then,
| 21 = | 11 + 1lye o1l2
2(v, 5. V: v),
5

---

which is equivalent to
(ye 5. yt v) 2|1 yell2 l1 u||2 | r1
Observe that the left hand-side is the Frank- Wolfe gap expression at iterate yr (except for the maximization over v E P) since (f())) - yr Z.
Necessary Condition. Let us first assume Ue - e|| < | - iteration t. Then (1) yields
v|l for all vertices & e P in some
(y 2, yr v) 111 vell?.
(altTest)
0 is the Frank- Wolfe vertex in iteration t, we obtain:
1ive म||² 21le"* 2||2 (wv) f(v))
I max (Vf(y)) v) (V (We) Vs uz) (y: x. yt v2) 2 ye VEP
Subtracting 1 - 1 on both sides and re- e-raranggng yields: 0 < 2 - $|? which proves that á & P. Moreover, (1) also immediately provides separating hyperplane: observe that (altTest) is actually a linear incquality in and it holds for all v E P since the maximum is achieved at vertex. However, for the choice v = I the inequality is violated.
Sufficient Condition. Suppose that in each iteration there exists a vertex U2 P (not to be confused with the Frank-Wolfe vertex), so that 1/v. Te 2 || Tell. In this case (1) ensures:
(yt v. y vi) = - yell + all - 5y 1| 1 Jell? 2
bll yell?.
Thus, the Frank- Wolfe gap satisfies in each iteration /. that
max
f(v)) yr- u) 2 (y: 2, n.) 1 1el1 VEP
ie., the Frank- Wolfe gap upper bounds the distance between the current iterate y, and point each iteration. Now, the Frank-Wolfe gap converges to as the algorithm progresses, with iterates yt E P, so that with the usual arguments (compactness and limits etc.) follows that è E P. In total, we obtain the following result.
Characterization 2. The following are equivalent:
1. (Non-Membership)) ī & P.
2. (Distance) There exists an iteration I, so that ||y. - w|| < | - v|| for all vertices v E P.
3. (FW Gap) For some iteration t, max,ee (y: Σ, yo v)
--ž-v7 111
In particular, Characterization 2.3 can be easily tested within the algorithm, since the Frank-Wolfe gap computed anyways. Using this criterion significantly improves the performance of the algorithm. Moreover, the characterization above can also be combined with standard convergence guarantees to estimate the number of iterations required to either certify non-membership or membership (up to an e-error): If we use the vanilla Frank- algorithm, then by standard guarantees (see e.g., [16)) it
known that the Frank- Wolfe gap Gt max,g P (w: ã, 1/t v) satisfies minogr 9r
4LD2 for
r+3
appropriate positive constants I. and D. Suppose that max ve p. (v: 3. yt v) 2 || - yell holds for all iterations 0 < t T. We want estimate how long this can hold. If ã & P. then using the convergence guarantee yields:
4LD²
dist(T P)3 min 1
2-11
1+3
Using I, = as f(v) | ä 2 and rearranging we obtain
8D2
5 T == dist(E, P)z
3,
i.e., after at most T iterations we have certified that 7 is not in P. Guarantees for more advanced Frank- Wolfe variants can be obtained similarly.

---

Algorithm Lazy Away-Step Frank- [18, 19] with explicit active set and early termination
Input: Point yo P. function f'()) 2 flly =|l?. step-sizes "t > O, tolerance 6 > 0, oracle Q Output: Valid cut (ū,x) S B for P with (ā,, .i > 3 or false if E E P.
1: ng +- (V(V(()))
2: S <- {(70, )o) - 70. vo)) (V) (v)) yo vo)
3: for 0 to max do
4: if [l)
then
5: return false
6: end if
7:
(Az, VL) +- (.) u). (AA, UA) + (VF(())
8:
if (V fye), y/ UL) 2 max ( (V ((e),, UA -yt), 5) then
9:
U++1 f UL Ymna f
(lazy step)
10:
else if (V)(y),, U^ - yn) I max (Vf())), x- vn). }} then
11:
U++1 - VA. 7max I-AA
(aaay step]
12: else
13:
U++11 <- CVVVVVVVV (w:)), 7max +-1
14:
(V/ (ye), 1/ Ut+1) < $ then
15:
< min (V)()),) 3t 11+1), 2 Ymax +- 0
[dual step]
16:
end if
17:
end if
18:
if (Wt
5. Vt - 1+1) < 2 $- 111 then
19:
return cut (- V fl (1t), $ (v))) v441)
{see Charac. 2.3)
20:
end if
21:
min Tmax
22:
S+ (A(1-a),0) (A, ES u (41)
23:
1++1 EnNoees Au
end for
3.2 Computational Aspects
common trait of the local cuts framework is that P is accessed implicitly via an oracle returning vertices. By far the simplest black-box -box oracle for any bounded IP is enumeration, which simply evaluates all possible solutions and picks the best one. If the IP is unbounded. then pure enumeration does not suffice any more and the oracle needs to take the unboundedness into account. For some problems, we can find problem-speciff algorithms that only enumerate over feasible solutions or otherwise exploit the structure of the problem at hand to reduce the complexity of enumeration. Examples are the dynamic programming approach for knapsack problems, see Section 4. 1, or directly enumerating n! possible permutations of items for the linear ordering problem (LOP).
Similarly the enumeration oracle, the lifting routine can also avail of problem-specific structure in some cases. In the case of LOPs, the so-called trivial lifting lemma holds, that is, facet-defining inequalities of the LOP polytope in dimension also define facets in dimension n [35], meaning that no lifting is needed at all in this case. For knapsack problems. we can again use dynamic programming approach, see Section 4.2.
In general, to apply our method to a given class of IP probems, one needs three components: i) a projection + P. ii) An oracle solving linear optimization problems over to optimality; in order to be practical, the selected should be such that the oracle runs reasonably fast. iii) A lifting method to lift cuts from P up to P.
In our implementation, we use the Lazy Away-Step Frank- Frank-Wolfe algorithm of [18, 19], which converges linearly for (Separation). We integrate the novel termination criterion from Characteriza- tion 2.3, leading to Algorithm 1. This algorithm should be thought of as more advanced version of the vanilla Trank-Wolfs algorithm. This variant motivated by the fact that Frank- Wolfe trends towards sparse solutions and hence the oracle will often return previously-sed vertices. Hence, instead of querying the expensive oracle, one stores previous vertices active sei whose size controlled through so-called away steps. It provides superior convergence speed both in iterations and
7

---

wall-clock time, exploiting the strong convexity of our objective function of the separation problem; we refer the interested reader to [46, 52, 16] for an overview. Lazification, to be thought of as an advanced caching technique, further reduces the per-iteration cost by reusing previously computed LMO solutions. Lastly, we note that our setting and case study presented Section 4, the L.O always returns vertex. Even though this is not theoretical requirement for the results presented in this paper, we do not consider the alternative case for brevity.
4 Case Study: The Multidimensional Knapsack Problem
The multidimenssonal knapsack problem (MKP) is well-known problem in combinatorial opti- mization and is strongly N'P-hard. has been used to address various practical resource allocation problems [30]. The problem involves maximizing the total profits of selected items, taking into account m resource capacity (knapsack) constraints. There are n items that contribute profits given by E Z". The resource consumption of item j for the ith knapsack is given by aij E Z+; this defines matrix A (a.y) Zm The capacities of the knapsacks are given by b E Z We define binary variables x E {0, 1 such that 2, is equal to if item j is selected and 0 otherwise. Then MKP can be expressed an IP:
max ((e, Ar S b, E {0, 1).
(MKP)
There exists abundant literature on the knapsack problems; we refer the interested reader to the recent survey by Hojny et al. [43].
We will also test our approach on the instances of the generalized assignment problem (GAP), see Section 5. GAP is variant of MKP with applications in scheduling [43]. In addition to the constraints from the MKP problem, it is required that each of the items be assigned to exactly one knapsack. The interested reader can find a survey, more details, and a comprehensive reference list in [4, 58].
In order for our approach to work, we need to provide two things: the oracle, presented in Section 4.1, and the lifting routine, presented in Section 4.2, ef. Section 2 and Section 3.
We consider each knapsack problem in turn and try to generate inequalities that are valid for each individual knapsack. This has the advantage that there are practically efficient oracles and more importantly efficient lifting processes. The disadvantage is that the cuts might be weaker, since they are valid for all integer solutions for all knapsack constraint instead of their intersection. An alternative would be to consider optimization oracles for the complete set of knapsack constraints as done by Gu [37]. However, then either lifting becomes more computationally demanding one cannot use lifting.
4.1 The Linear Minimization Oracle
The process begins with solution x² of the LP relaxation of the MKP. We create reduced knapsack problem of dimension & E Z4, k I n by removing variables of each knapsack that have integral values (0/1) the LP relaxation. The oracles now solve the knapsack problems (KP) for each constraint of the form max {(c, xt) (w,z) 4)) S C, x E {0, 1)"), with e R E Z C E Z_... In practice, the dimension is rather small (in our test sets, see Section 5, we observe an average & value of 9.6 with a maximal size of 26), allowing for efficient solution approaches. In our implementation. we use a LMO based on dynamic programming. We note that we also apply the preprocessing improvements described by Vasilyev et al. [64], before run the oracle on the reduced problem.
Dynamic programming, as presented by Bellman in 1957 [7], was one of the earliest exact algorithms for solving KPs. Toth [62] presents additional improvements to the algorithm. More recently, Boyer et al. present mussively-paralll implementations running on GPUs [15]. The space and time complexity of the dynamic programming algorithm for KP is (KC)) [15], where k is the number of items and C the knapsack capacity. For this work, we reuse the single-threaded, CPU-based implementation of dynamic programming available in the sper-source solver SCIP [10]. As we rely on existing implementations, we refer the interested reader to the above references for more details on this algorithm.
8

---

Table I: Statistics for branch-and-cue run with separation of local cuts for 45 generalized assignment problem instances (left) and 21 instances that were solved to optimization by all variants (right).
variant
I solved
time
sep. time
Ncuts
variant
A solved
nodes
time
default
98.2
default
21
lo0-ac-dowalift
21
411.7
$4.0
10858.6
leO-ne-dowalift
21
1522
33.7
lc0-ac-liiting
113.7
9.8
4933.6
leU-ne-Hittngg
21
657
5,3
lcl nc lifting
86.8
31.8
160244.4
1cl me lifting
21
185
4.2
4.2 The Lifting Routine
Lifting knapsack constraints has been extensively studied in literature, see [43] for short survey with comprehensive references. Therefore, we only briefly summarize the implemented methods here and refer the interested reader to [43] and references therein for more details.
Let fa E (0,1)" E== aj2; I au3 be one of the original knapsack constraints (corresponding to a single row Ar < in (MKP)). Define [n] == (I,...,n) m), Fo = (i E [n] =3 = 0). and Fi = [j [m] zj = 1}. Then == [m] \ (Po U Fi) are the variable indices the reduced knapsack. The lifting procedure then lifts a given inequality Ejes ajæ, S 0g valid for the reduced knapsack polytope fz E 1) EjEs Ozz; I Ag - DIER az} to a valid inequality for the original knapsack by computing new coefficients Bz. E Fo Pi:
Σa
Σ JEFI
B,
B,a, S ag Σ 3,.
JES
JEP
JEP
We implemented algorithms known as sequential up-lifting and sequential down-lifting, respectively. The implementation is based on dynamic programming as described by Vasilyev et al. [64].
Computational Experiments
We implemented the described methods in C/C++, using developer version of SCIP 8.0.4 (githash 3dbcb38) and CPLEX 12.10 as LP-solver. All tests were performed on a Linux cluster with 3.5 GHz Intel Xeon E5- Quad-Core CPUs, having 32 GB main memory and 10 MB cache. All computations were run single-threaded and with a time limit of one hour. To concentrate on the improvement of local cuts on the dual bound, we initialize all runs with the optimal value. We used = 1 x 10 in Algorithm 1.
To demonstrate the advantage of using local cuts with the Frank- approach, implementation on the generalized assignment instances from the OR-Library available at http:// people. brunel. ac fte//mmatjjaa jaapj///jeebbriire wawoor/b////oee httgaiinfo.....//oo/.opoopooooot cttmnfo.html. These instances have also been used by Avella et al. [4].
The results are presented in Table 1. Here, "default" are the default, factory settings of SCIP. The other settings are 1cX-nc-Y, where X means that we only separate local cuts in the root node and X = 1 means that we separate local cuts in the whole tree; Y refers to whether we perform down lifting (Y = downlift) or up- and down lifting (Y = lifting). Note that for these settings, where local cuts enabled, we turn the generation of all other cuts off, because this (somewhat surprisingly) showed better performance. The CPU time in seconds ("time") and separation time ("sep. time") ") as well as number of nodes ("#nodes")) are given shifted geometric means?. The numbers of generated cuts ("#cuts") are arithmetic means. Note that the iteration limit for the Frank- Wolfe algorithm is 10 000 in the root node and 1000 in the subtree. We also reduce the effect of cut filtering allowing for more cuts to enter the main LP. Moreover, we initialize the runs with the best know solution values as in [4].
The results show that the best version is 1c1 acc-nc-lifting i.e., helps to separate local cuts every node and perform up- and down lifting. This version is roughly 31% faster than the default settings on the instances solved to optimality. Using only down lifting performs badly. In any case, on these
'The shifted geometric mean of values ....., tr is defined as (II(4, + +)) with shift = 1 for time and s 100 for nodes in order decrease the influence of easy instances in the mean values.

---

instances, using our local cuts method is big advantage. Additional results are given in the appendix. In addition, we also ran an experiment in which we applied complemented mixed-intee -ntteger rounding (CMIR) on the produced cut, which turned out to not be helpful and is therefore not reported in detail.
Some additional observations over all 45 instances in the test set icl-nc-lifting called local cuts separation 16 17870.6 times on average. The total time for Frank- Wolfe separation is about one third of the total time. The time spent in the oracle is 17.3 seconds on average compared to a total of 87.9 seconds for the complete Trank-Wolf algorithm. On average 69 968.8 calls ended running into the iteration limit, 81.2 detected optimality with a zero gradient, 8652.9 stopped because the primal gap is small enough, and 143 155.9 stopped because of the termination criterion of Section 3.1.1. This demonstrates the effect of this criterion.
follows: Variant
6 Conclusion and Future Work
In this paper, we presented novel method to learn local cuts without relying on solutions of LPs in the process. To show the effectiveness of our approach. we selected the multidimensional knapsack problem as case study and presented computational results to support our claims.
Solving LPs has proved to be notoriously hard to parallelize, with only minor performance im- provements reported in literature to date [40, 45). Thus, existing methods for deriving local cuts, which rely on solving LPs, typically run single-threaded, on CPUs. Our approach is quite fast, as demonstrated in the computational experiments for our target problem class, but also paves the way for exploring highly parallel implementations on heterogeneous hardware and compute accelerators. This is made possible by eliminating the dependence on LPs and instead relying on the Frank-Wolfe algorithm. One such option we would like explore the future is derive a vectorized version of our Frank-Wore algorithm that could work on multiple separation problems at the same time, increasing the computational density of the operations performed and availing of massively parallel compute accelerators like GPUs in the process.
The presented method is generic and can be applied to any (M)IP. We have chosen important problem class in this paper to demonstrate the method. A natural extension of this work would be consider other important problem classes and evaluate the benefits of using our method on those problems- especially those with beneficial properties as outlined in Section 3.2.
References
[1] T. Achterberg and R. Wunderling. Mixed integer programming: Analyzing 12 years of progress. In M. Jünger and G. Reinelt, editors, Facets of Commiinttoiill Optimization: Festschrift for Martin Grötschel, pages 449-481, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013.
[2] E. Althaus, Т. Polzin, and S. V. Daneshmand. Improving linear programming approaches for the Steiner tree problem. In K. Jansen, M. Margraf, M. Mastrolilli, and J. D. P. Rolim, editors, Experimental and Efficient Algorithms, pages 1-14, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg.
[3] D. Applegate, R. Bixby, V. Chvátal, and W. Cook. TSP Cuts Which Do Not Conform to the Template Paradigm. In M. Jünger and D. Naddef, editors, Computational Combinatorial Optimization, volume 2241 of Lecture Notes in Computer Science, pages 26! 1033. Springer Berlin Heidelberg, 2001.
[4] P. Avella, M. Boccia, and Vasilyev. A computational study of exact knapsack separation for the generalized assignment problem. Computational Optimization and Applications, 45(3):543-555 2010.
[5] E. Balas, S. Ceria, and G. Cormuéjoss A lift-and-project cutting plane algorithm for mixed 0-1 programs. Mathematical Programming, 58(1):295-33) 1993.
[6] M.-F Balcan, T. Dick, T. Sandholm, and E. Vitercik. Learning branch. In Dy and A. Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 344-353, PMLR, 10-15 Jul 2018.
[7] R. Bellman. Dynamic CacaumccProoraaeet Programming. Princeton University Press, Princeton, NJ, USA, 1957.
10

---

[8] I. Bello, H. Pham, Q. V. Le, M. Norouzi. and S. Bengio. Neural combinatorial optimization with reinforcement learning, 2017.
[9] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: A methodological tour d'horizon. European Journal of Operational Research, 290(2):405-422 421, Apr. 2021.
[10] K. Bestuzheva, M. Besançon, W.-K Chen, A. Chmiela, T. Donkiewicz, J. van Doornmalen, L. Eifler, O. Gaul, G. Gamrath, A. Gleixner, L. Gottwald, C. Graczyk, K. Halbig, A. Hoen, C. Hojny, R. van der Hulst, T. Koch, M. Lübbecke, S. Maher, F. Matter, E. Mühmer, B. Müller, M. E. Pfetsch, D. Rehfeldt, S. Schlein, Schlösser,
Serrano, Y. Shinano, B. Sofranac, M. Turner, S. Vigerske, F. Wegscheider, P. Wellner, D. Weninger, and J. Witzig. Enabling research through the SCIP Optimization Suite 8.0. ACM Transactions on Mathematical Software, 2023. accepted for publication.
[11] R. Bixby and E. Rothberg. Progress in computational mixed integer programmiing a look back from the other side of the tipping point. Annals of Operations Research, 149(1):37-41, 2007.
[12] M. Boccia. Using exact knapsack separation for the single-source capacitated facility location problem. tech. rep.. Department of Engineering. University of Sannio, 2006.
[13] A. E. Boyd, A pseudopolynomial network flow formulation for exact knapsack separation. Networks, 22(5):503-514, 1992.
[14] E. A. Boyd. Generating Fenchel cutting planes for knapsack polyhedra. SIAM Journal Optimization, (44):734-500, 1993.
[15] V. Boyer, D. EI Baz, and M. Elkihel. Solving knapsack problems on GPU. Computers & Operations Research, 39(1):22-47, 2012.
[16] G. Braun, A. Carderera, C. W. Combettes, H. Hassani, A. Karbasi, A. Mokthari, and Pokutta. Conditional gradient methods. Preprint, arXiv, 2022. attps://arxiv.or org/ haargg/bb/221111 14103.
[17] G. Braun and S. Pokutta. Dual Prices for Frank-Wolfe Algorithms. Preprint, arXiv, 2021. https://arxiv.otm org// ab10 020877.
[18] G. Braun, S. Pokutta, and D. Zink. Lazifying conditional gradient algorithms. In Proceedings of the 34th International Conference on Machine Learning, pages 566-575, 2017.
[19] G. Braun, S. Pokutta, and D. Zink. Lazifying conditional gradient algorithms. Journal of Machine Learning Research (JMLR), 20(71):1-42, 2019.
[20] C. Buchheim, F. Liers, and M. Oswald. Local cuts revisited. Operations Research Letters, 36(4):430-433, 2008.
[21] C. Buchheim, F. Liers, and M. Oswald. Speeding up IP-based algorithms for constrained quadratic 0-1 optimization. Mathematical Programming, 124(1):513-535, 2010.
[22] A. Caprara and M. Fischetti. {0, WV2--Chvátal-Gomory cuts. Mathematical Programming, 74(3):221-235, 1996.
[23] A. Chmiela, E. B. Khalil, A. Gleixner, A. Lodi, and S. Pokutta. Learning to schedule heuristics in branch and bound. In A. Beygelzimer, Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[24] P. Chu and J. E. Beasley. A genetic algorithm for the multidimensional knapsack problem. Journal of Heuristics, 4:63-86, 86, 1998.
[25] V. Chvátal, W. Cook, and D. Espinoza. Local cuts for mixed-integer programming, Mathemati- cal Programming Computation, 5(2):171-200 2013.
[26] H. Crowder, F. Johnson, and M. W. Padberg. Solving large-scale zero-one linear program- ming problems. Oper. Res., 31:803-834 834, 1983.

---

[27] H. Dai, E. B. Khalil, Y. Zhang. B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. Proceedings of the 31st International Conference on Neural Infor- mation Processing Systems, NIPS' 17, page 6351-6361 Red Hook, NY, USA, 2017. Curran Associates Inc.
[28] J. Ding, C. Zhang. L. Shen, S. Li, B. Wang, Y. Xu, and L. Song. Accelerating primal solution findings for mixed integer programs based on solution prediction. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02):1452-1455) Apr. 2020.
[29] M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Research Logisties Quarterly, 3(1-2)995-110,, 1956.
[30] A. Fréville. The multidimensional 0-1 knapsack problem: An overview. European Journal of Operational Research, 155(1):1-21, 2004.
[31] M. Gasse, D. Chételat, N. Ferroni, L. Charlin, and A. Lodi. Exact Combinatorial Oplimization with Graph Convolutional Neural Networks. Curran Associates Inc., Red Hook, NY, USA, 2019.
[32] R. Gomory. Outline of an algorithm for integer solutions linear programs. Bulletin of the American Society, 64:275-278, 1958.
[33] R. Gomory. An algorithm for the mixed integer problem. Technical Report RM-2597, The RAND Cooperation, 1960.
[34] R. Gomory. Solving linear programming problems in integers. Combinatorial Analysis, R. Bellman and J. M. Hall, eds., Symposia in Applied Mathematics X, Providence, RI, 1960, American Mathematical Society, 10:211-215, 1960.
[35] M. Grötschel, M. Jünger, and G. Reinelt. Facets of the linear ordering polytope. Mathematical Programming, 33:43 60. 1985.
[36] M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimiza- lion. Springer, 1988.
[37] H. Gu. Local cuts for 0-1 multidimensional knapsack problems. In R. Sarker, H. A. Abbass, S. Dunstall, P. Kilby, R. Davis, and L. Young, editors, Data and Decision Sciences in Action, pages 81-89, Cham, 2018. Springer.
[38] Z. Gu, G. L. Nemhauser, and M. W. Savelsbergh. Sequence Independent Lifting in Mixed Integer Programming. Journal of Combinatorial Optimization, 4(1):109-129, 2000.
[39] Z. Gu, G. L. Nemhauser, and M. W. Savelsbergh. Lifted flow cover inequalities for mixed 0-1 integer programs. Mathematical Programming, 35(3):439-46) 1999.
[40] A. J. Hall Towards a practical parallelisation of the simplex method. Computational Management Science, 1(2):139-170, 2010.
[41] H. He, H. Daume III, and J. M. Eisner. Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[42] G. Hendel. Adaptive large neighborhood search for mixed integer programming. Mathematical Programming Computation, 14(2):185 221, Nov. 2021.
[43] C. Hojny, T. Gally, O. Habeck, H. Lüthen, F. Matter, M. F. Pfetsch, and A. Schmitt. Knapsack polytopes: survey. Annals of Operations Research, 292(1):469-517, 2020.
[44] A. Hottung and K. Tierney. Neural large neighborhood search for routing problems. Artificial Intelligence, 313: 103760,, 2022.
[45] Q. Huangfu and A. Hall. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119-422, 2018.
12

---

[46] M. Jaggi. Revisiting Frank-Wolfe: projection free sparse convex optimization. In Proceedings of the 30th International Conference on Machine Learning, pages 427-435, 2013.
[47] K. Kaparis and A. N. Letchford. Separation algorithms for 0-1 knapsack polytopes. Mathemati- cal Programming, 124(1):69-99) 2010.
[48] E. Khalil, P. L. Bodic, L. Song, G. Nemhauser, and B. Dilkina. Learning to branch in mixed integer programming. Proceedings of the AAAI Conference Artificial Intelligence, 30(1), Feb. 2016.
[49] E. B. Khalil, B. Dilkina, G. L. Nemhauser, S. Ahmed, and Y. Shao. Learning to run heuristics in tree search. In Proceedings of the Twenty-Sine Eienty-Sixtth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, Aug. 2017.
[50] T. Koch, A. Martin, and M. E. Pfetsch. Progress in academic computational integer programming. In M. Jünger and G. Reinelt, editors, Facets of Combinatorial Optimization: Festschrift for Martin Grötschel, pages 483-506 Springer Berlin Heidelberg, Berlin, Heidelberg, 2013.
[51] W. Kool, H. van Hoof, and M. Welling. Attention, learn to solve routing problems! In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.ne, 2019.
[52] S. Lacoste-Julien and M. Jaggi. On the global linear convergence of Frank-Wolfe optimization variants. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 496-504, Curran Associates, 2015.
[53] E. S. Levitin and B. T. Polyak. Constrained minimization methods. USSR Computational Mathematics and Mathematical Physics, 655):1-50, 1966.
[54] D. Liu, A. Lodi, and M. Tanneau. Learning chordal extensions. Journal of Global Optimization, 81 (1(1)33-2, Jan. 2021.
[55] H. Marchand and L. A. Wolsey. Aggregation and Mixed Integer Rounding to Solve MIPs. Operations Research, 49(3):363-371, June 2001.
[56] M. Nazari, A. Oroojlooy. L. Snyder, and M. Takac. Reinforcement learning for solving the vehicle routing problem. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[57] M. E. Pfctsch, G. Rinaldi, and P. Ventura. Optimal patchings for consecutive ones matrices. Mathematical Programming Computation, 14(1):43-84, 84, 2022.
[58] M. Posta, J. A. Ferland, and P. Michelon. An exact method with variable fixing for solving the generalized assignment problem. Computational Optimization and Applications, 644, 2012.
[59] J. Song, r. lanka, Y. Yue, and B. Dilkina. A general large neighborhood search framework for solving integer linear programs. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 20012-20023. Curran Associates, Inc., 2020.
[60] N. Sonnerat, P. Wang, I. Ktena, S. Bartunov, and V. Nair. Learning large neighborhood search algorithm for mixed integer programs, 2021.
[61] Y. Tang, S. Agrawal, and Y. Faenza. Reinforcement learning for integer programming: Learning to cut. In H. D. III and A. Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 9367-9376. PMLR, 13-18 Jul 2020.
[62] Toth. Dynamic programming algorithms for the zero-one knapsack problem. Computing, 25(1):29 1980.
13

---

[63] I. L. Vasil'es ev. A cutting plane method for knapsack polytope. Journal of Computer and Systems Sciences International, 48(1):70-77, 2009.
[64] I. Vasilyev, M. Boccia, and S. Hanafi. An implementation of exact knapsack separation. Journal of Global Optimization, 66(1): 2016.
14

---

Appendix A
We ram two additional experiments. the first, we try to repeat the experiments about the strength of local cuts in the root node from [47]. As comparison, we use the implementation of the local cuts with the LP-based approach of [57] (see the beginning of Section 3 for an overview the method). In the second experiment, demonstrate what happens if we use local cuts in branch-and-cut framework to solve multi-dimensional knapsack problems to optimality.
start with a comparison the gap-closed, which is defined as 100 100 p-d=, where p the p-d;y optimal primal value, d, is the dual bound at the end of the root node, and dip is the dual bound of the first LP the node. Table shows the results. We use the same multi multi-dimensiona. knapsack instances as Kaparis and Letchford: they were originally generated randomly by Chu and Beasley [24] and are available at http: http://people, brunel. ac ww..a..............
mknapinfo... html. The instances are organized in blocks of 10, using variables, m knapsack constraints, and parameter a. Column "KI." shows the gap-closed from [47]. Then the results of using the implementation of the L.-haaed approach (which is also used in [47]) and our Frank-Won Wolfe approach are presented. For each approach, we show the average of gap-closed, total running time in seconds, as well as separation time, number of calls, and generated violated cuts by the local cut separation over each instance block (of 10 instances). For both approaches, we turn off all other cuts and strong branching. Moreover, iterations of the Frank- Wolfe algorithm in the root node, and reduce the effect of cut filtering, i.e., more cuts added the LP. In each round separate local cuts for all knapsack constraints that are available. We also initialize the runs with the optimal value to remove the effects of primal heuristics.
settings that allow 1000 rounds of local cuts, 10000
The results show that the LP-based approach achieves similar gap-closed values as Kaparis and Letchford. One explanation for the differences is that the final gap depends on the particular points to be separated (but note that we do not generate rank-2 cuts). In comparison, the Foolfe approach is much faster, but also produces smaller gap-closed. There are again several reasons for differences: We limit the number of Frank- Wolfe iterations to 10000 in the root node, which will leave
separation problems be undecided and the Frank- Wolfe algorithm might fail to converge (for instance, for n 500, m = 5, a = 75, on average 34.8 Frank- Wolfe runs terminated in the iteration limit and 75.4 with the termination criterion explained in Section 2). Moreover, the Frank- Wolfe approach does not necessarily produce a facet, which can weaken the bounds.
Table 3 shows results for running a complete branch-and-cut with variants Lc0-nc-11n lifting and hel-ne-lifting As comparison, we use the default settings of SCIP, but reduce cut filtering (this produces slightly better results for these instances). The results show that for smaller instances,
Table 2: Gap closed and running times after the rool node for the multi-dimennional knapsack instances; each line represents the average 10 instances.
LP
gap closed
sepa time
gAP closed
sepa time
KL
#calls
#calls
100
17.96
18.88
1.60
1.60
26.1
113.0
12.54
0.77
0.76
21.3
78.4
100
21.65
22.36
2.13
2.12
29.3
124.5
15.55
0.88
0.87
20.8
77.7
100
5
22.88
23.19
2.18
2.17
28.8
122.9
16.91
0.96
0.95
21.3
85.8
100
5.75
2.68
14.5
105.7
2.73
43.0
100
10
SO
7.33
7,63
3.62
3.62
16.5
120.1
4.30
1.50
1.49
11.4
59.2
2.71
4.37
100
30
25
16
0.14
2.80
2.87
2.4
12.0
0.00
1.05
1.05
0.2
0.1
100
50
0.49
0.47
4.45
4.44
4.9
38.2
0.02
0.84
0.83
0.6
0.7
100
0.52
0.53
4.30
4.29
35.9
0.07
1.01
250
5
25
14.56
15.44
4.03
4.00
3G.3
161.0
8.03
1.08
1.06
20.4
77.6
250
7.87
250
5
75
17.48
16,98
7.42
7.39
36.6
165.3
10.45
2.58
2.56
22.5
87.5
3.98
17.5
128.7
49.7
250
10
50
4.48
4.11
6.52
6.48
17.4
130.8
1,60
1.49
1.48
8.4
46.2
250
4.73
8.54
8.51
18.5
141.3
2.10
2.12
2.11
9.5
51.
500
13.80
11.75
10.37
10.31
42.0
182.9
5.06
2.84
2.81
20.9
78.4
500
50
11.91
11.17
17.41
17.35
45.2
199.2
5.02
5.21
5.19
21.5
$1.0
15

---

Table 3: Detailed statistics for branch-and-cut run with three different algorithm variants for the multi celti-dimensional knapsack instances; each line represents shifted geometric means over 10 instances.
default
lo0-nc-litting
le lel-nc-uplift
Y
#solved
time
sep time
#solved
time
time
#solved
time
time
100
25
10
11.76
5.11
10
5.89
1.45
24.41
18.95
100
50
10
7.61
3.32
10
5.27
1.57
19.62
16.00
7.74
100
10
25
10
47.49
10.83
10
32.67
2.27
10
347.27
308.99
100
10
50
10
44.48
11.49
30.04
2.77
300.69
325.67
100
10
75
10
16.44
3.20
11.33
2,80
10
112 23
102.36
100
30
25
10
558.98 98
18.90
458
2.07
3
3288. 89
3095.03
100
30
50
10
497.33
20.35
413.70
3057.
2870.52
100
30
75
10
118.77
12.38
10
92.87
1.91
7
1986.30
1892.20
250
25
12.55
63.59
195.77
250
50
10
125.84 84
10.07
10
104.14
3.54
10
636. 2/5
493.87
250
75
10
53
7.89
42.53
4.08
231.
188. 66
250
10
25
3600.01
906.72
3419.56
4.13
3600.01
2992.22 23
250
10
50
3528.
1033.57
3483.90
4.03
3600.00 0
3326.01
250
10
75
2062.86
346.76
1645.50
5.10
3482.48
3138.87
300
25
1883 73
218.06
10
1539.91
5.07
3
3056. 45
1962.73
2963.75
2068.72
300
75
676.14
70.40
10
648.03
9.43
2039 17
1368.61
there no clear advantage of the Frank-Wolfe approach, but for larger sizes, it solves more instances and is faster.
16


Reviews:
[{"review_id": "MyaBTVXMbP", "reviewer": "Reviewer_cm37", "summary": "This paper studies integer programming (IP) by proposing an alternative cutting-plane approach that makes use of the Frank-Wolfe (FW) algorithm for the separation sub-routine (i.e., separation of the target from the feasible set). The main idea is to use “local cuts” which aims at deriving the facets of $P_I$, i.e., the integer hull of the feasible set, $P$, of the relaxed linear program (LP). \n\nFacets of $P_I$ are the strongest cuts but they are unknown and finding the facets could be computationally expensive. The authors propose a separation procedure which does not need to solve an LP, and instead uses away-step FW variant to (approximately) solve the separation problem. \n\nTo demonstrate the performance of their approach, the authors compare their FW-based approach with the default SCIP solver, an optimization framework for solving mixed-integer programs, against solving the multi-dimensional knapsack problem. They also describe the implementation of the linear minimization oracle (LMO) of the FW algorithm using dynamic programming for the application at hand.", "questions": "-\tHow do you set $\\epsilon$ in your algorithm?\n-\tHave you compared your algorithm numerically with other proposed methods for solving MKP or other popular IP problem (other than the results in the appendices)?\n-\tHave you run experiments for other problem instances?\n-\tI am curious about the possible shortcomings of the FW approach. The linear minimization oracle for the FW method uses dynamic programming, which introduces an overhead for the computation of $v_t$. Is there any regime where the FW approach with the proposed LMO oracle becomes computationally expensive such that the run times are comparable to LP-based approaches?", "limitations": "-\tThe authors might need to consider more problems like MKP to validate the performance of their approach.\n-\tI would prefer to see several other methods to be included in the numerical tests.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "-\tAuthors provide an alternative to the cutting-plane approaches by simplified local cuts. Instead of exactly solving an LP, the authors make use of FW algorithm and dynamic programming to find facets of the underlying polyhedron in lower dimensions. They use known lifting techniques to obtain the full-dimensional cut.\n\n\n-\tThe stopping criterion for the algorithm is derived via fundamental properties of the FW algorithm and LMOs. Using a fundamental, technical intuition, they improve the performance of the separation routine by an additional stopping criterion.\n\n\n-\tThey compare their approach with SCIP with default settings as a benchmark and provide improved run times.", "weaknesses": "-\tThe fundamental differences and improvements with respect to existing cutting-plane methods to solve IP problem (specifically MKP as the authors provide it as an example) are not clarified. Computational/complexity improvements with respect to LP-based methods are not studied in technical details.\n\n\n-\tThe method is not comprehensively compared against (in practice) to existing methods for solving IPs, specifically MKPs. The authors provide a comparison between LP-based separation as implemented by [42] and the FW approach in the appendix. The FW approach is faster in run time but the gap closed is less than the LP-based approach. I am not sure whether it is enough to claim a clear advantage for the proposed algorithm. However, we should note that Table 3 shows promising results for the FW algorithm.\n\n\n-\tSince this paper does not propose a new theory and analysis, I don’t find the experimental evaluation comprehensive enough. The authors should have considered other problems, such as TSP, while including existing algorithms in their runs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n1. How do you set $\\epsilon$ in your algorithm?\n\nOur algorithm sets $\\epsilon$ to 1e-9, following the SCIP default. We will include this into the revised version of the paper.\n  \n2. Have you compared your algorithm numerically with other proposed methods for solving MKP or other popular IP problems (other than the results in the appendices)?\n\nRegarding the comparison of our algorithm with other methods, we have chosen to focus on a generic method capable of operating on any IP given a suitable lifting routine. We deemed it most relevant to test this within a general-purpose solver, rather than specialized heuristic methods. Our choice of SCIP is motivated by its status as the most widely used academic solver of this kind. The comparisons presented in the appendices involve the most recent state-of-the-art competing methods, as per our knowledge.\n\n3. Have you run experiments for other problem instances?\n\nConcerning the testing of different problem instances, we used the MKP to introduce and illustrate our methodology, given its relevance and popularity in IP problems, thereby providing a robust benchmark. However, we plan to explore other problem classes in future work, with a particular interest in problems with trivial lifting, which we believe align well with our approach.\n\n4. I am curious about the possible shortcomings of the FW approach. The linear minimization oracle for the FW method uses dynamic programming, which introduces an overhead for the computation of $v_t$. Is there any regime where the FW approach with the proposed linear optimization oracle becomes computationally expensive such that the run times are comparable to LP-based approaches?\n\nPlease note that the oracle _used in the MKP_ uses dynamic programming. The structure of the oracle is very much problem-dependent, e.g., in the case of a TSP, the oracle could be enumerating a set of round tours on a subset of cities. Hence, one has to find a balance between the overhead introduced by calling the oracle and the advantages of the FW procedure in general.\n\nAs for potential limitations of the FW approach, while it is technically possible to craft cases where FW runtimes exceed those of the LP-based approach, the overall effect on the solving process is more intricate. It depends on the quality of the cuts produced and their interplay with the various components of a modern MIP solver. This interaction encompasses aspects such as the cut filtering implementation, the strength of other obtained cuts, the solver's emphasis on generating cutting planes compared to other techniques, and more. Consequently, the method's true potential can only be gauged empirically over a relevant test set, as demonstrated in our computational studies by comparing out-of-the-box SCIP with SCIP enhanced by our method, as well as comparisons against SCIP enhanced with competing methods."}, {"review_id": "bq2Ipg77g0", "reviewer": "Reviewer_bBeY", "summary": "The paper studies cut generation from operations research. While this is potentially a promising approach, I believe the paper falls out of scope of the conference. Optimization can be seen as part of machine learning machiery, but normally NeurIPS papers are expected to have some connection to machine learning, e.g., at the very least, the experiments could have been done on some machine learning problem. It is not common to reject a paper based on out of scope, however in this case the paper is purely operations research. I believe submiting to an operations research venue would be more appropriate, and it is likely that the impact of the work would be greater in such a community.", "questions": "What is the motivation for submiting this paper to NeurIPS?", "limitations": "Did not look in detail.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Did not look in detail.", "weaknesses": "Did not look in detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n1. What is the motivation for submiting this paper to NeurIPS?\n\nWe recognize that our paper primarily falls under Operations Research, but it's crucial to note a significant distinction. Unlike many conventional cutting plane techniques in this field that hinge on fixed equations and formulas for separating hyperplane derivation, our method aims to learn unknown facets of a polytope from a lower-dimensional version, subsequently generalizing them into cutting planes for the high-dimensional polytope. This learning approach, while not new to Operations Research as high-level meta-paradigm, is made tangible and practical by our novel use of the Frank-Wolfe algorithm. This innovation paves the way for *general-purpose* cutting planes, learned directly from the problem rather than from pre-established rule sets.\n\nWe understand that this may not be the most typical application of learning algorithms, yet we respectfully differ with the view that it lacks interest for the community. We believe it could instead stimulate knowledge exchange across fields and potentially inspire machine learning researchers to apply new or improved methods derived from machine learning advancements to optimization problems.\n\nFurthermore, several NeurIPS papers from previous years have explored the application of learning methods in solving integer programming problems. A few notable ones are:\n\n- Wu, Y., Song, W., Cao, Z., Zhang, J., Gupta, A., & Lin, M. S. (2022). Graph Learning Assisted Multi-Objective Integer Programming. In NeurIPS.\n- Chmiela, A., Khalil, E., Gleixner, A., Lodi, A., & Pokutta, S. (2021). Learning to Schedule Heuristics in Branch-and-Bound. In NeurIPS.\n- Wu, Y., Song, W., Cao, Z., & Zhang, J. (2021). Learning large neighborhood search policy for integer programming. In NeurIPS.\n- Chen, X., & Tian, Y. (2019). Learning to perform local rewriting for combinatorial optimization. In NeurIPS.\n- He, H., Daume III, H., & Eisner, J. M. (2014). Learning to search in branch and bound algorithms. In NeurIPS.\n\nThis point is also reinforced by the review of reviewer kHh3 (see \"Strengths\")."}, {"review_id": "vdP7YKrcUZ", "reviewer": "Reviewer_5Xhs", "summary": "* Context:\nThis paper deals with the subject of generating cuts for solving Integer Programs (MIP).\nRather than using a cut generating algorithm based on a formula (like Gomory cuts) to create hyperplanes separating the solution of the relaxed problem from the (integer) feasible domain, the papers attempts to generate \"Local cuts\".\nLocal cuts are cuts that are obtained by generating a cut in a subproblem with reduced dimension (so that any optimization problem required to generate the cut are easier to solve), and then, taking the cut for the subproblem and transforming it into a cut for the actual problem to solve.\n\n* Contribution:\nThis paper presents a local cuts generating algorithm, based on the Frank-Wolfe / conditional gradient algorithm.\nFrank-Wolfe is used to find the point in the subproblem polyhedron $\\tilde{P}$ that is the closest to the point to be separated $\\tilde{x}$, as this point will be likely to be on a facet.\nThe Frank-Wolfe algorithm has the advantage that it only require linear optimization oracle access over the subproblem to arrive at a solution, which can often be implemented efficiently.\nThe paper also demonstrates that using duality information, the Frank-Wolfe algorithm does not need to be run all the way to convergence and that the strength of the cut generated by intermediate iterates can be evaluated, leading to a speed-up.\n\nThe impact of using these cuts is evaluated on the multi-dimensional knapsack problem, by including the local cut generating algorithm into the open source SCIP solver.", "questions": "* [Section 2] Could you clarify the relation between the polytope $P \\subseteq \\mathbb{R}^n$ and the polyhedron $\\tilde{P} \\subseteq \\mathbb{R}^k$ ? Is it always a restriction (a subset of the variables in P, such that an element is in $\\tilde{P}$ if there exists an element in $P$ with those values?) or could it be something more general ( like an affine transformation of $\\tilde{P}$ ?) and have as only requirement \"if we have a cut in $\\tilde{P}$, we can find a cut in $P$? . As it is, it sounds quite abstract.\n\n* [Section 5] Downlifting vs up- and down lifting is not explained anywhere. Given that downlifting performs significantly worse on all benchmarks, it seems that it might not be worth it to include it in the main version of the paper to avoid confusion.\nSimilarly, CMIR seems to have very little impact so unless it can be explained, it might make sense to move it to the appendix.\n* Would it be possible to include some more information on what the default settings of SCIP looks like? Is it a reasonable baseline? Is there an indication on how many cuts (whether local or not local) it corresponds to?\n\nTypos / small comments:\n- Line 30, I don't understand what the notion of the first $p$ indices is. Is that a reference to some Mixed Integer Programming case, where only the first $p$ variables need to be integral?\n- Figure 1 legend, is it supposed to be the L_2 projection (rather than L_t) ?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper presents a algorithmic improvement for solving an important problem, and does it in a clear fashion.\nIt is clearly delineated what exists in the current literature and what constitutes an actual contribution of the work.\nExplanations and motivations are straightforward to follow.", "weaknesses": "* From reading the paper, what is not obvious is how to take the contribution of this paper, and apply it to a different problem. After reading the paper, I understand how to apply this to a knapsack problem, but it's not obvious to me how I would do it if I had a more arbitrary MIP (for example one for verifying neural networks), or even a different type of problem solvable by integer programs (let's say a TSP). What would be beneficial would be to have somewhere clearly \"These are the requirements that you need for your problem to be solvable using this method\"\n\n* I think that what is missing is some appropriate baseline from the evaluation. As it is, the contribution of the paper seems to me to be \"here is an efficient way to do local cuts\", while the only baseline that is compared to is default SCIP. Is the performance difference that is seen due to using local cuts or using the local cuts presented in this paper? (I think that Table 3 in the appendix might have some results that are relevant to this, but this would benefit from being moved to the main part of the paper.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Comments on weaknesses:  \n\n1. [..] What would be beneficial would be to have somewhere clearly \"These are the requirements that you need for your problem to be solvable using this method\" [..]\n\nAs we restrict the scope to IPs for this paper, we will only list the requirements for applying the method for IPs. To be able to apply the method in general, you'll need the following components:\na) A projection P -> \\tilde{P}. Note that we restrict \\tilde{P} to always be a subset of P, which restricts the degrees of freedom. In order to be practical, the selected \\tilde{P} should be such that the oracle (see 2.) solves linear optimization problems over \\tilde{P} efficiently.\nb) An oracle solving problems over \\tilde{P} to optimality (returning a vertex). Note that while there may exist practically efficient specialized methods (such as dynamic programming for MKP), enumeration constitutes a general go-to option, especially in the presence of parallel hardware.\nc) A lifting method to lift cuts from \\tilde{P} up to P.\n\nNevertheless, we think making this list explicit is a great idea. While all components are there, we will make sure that in the revised version, we modify the language accordingly to clarify these conditions.\n\n2. [...] while the only baseline that is compared to is default SCIP. Is the performance difference that is seen due to using local cuts or using the local cuts presented in this paper? [..]\n\nIn Table 1, we compare the performance of baseline SCIP (aka \"default\") to variants of SCIP where the only cuts enabled are our FW-Local-Cuts (lc0 if separation only occurs in the root node; lc1 if this is done in the whole tree). As the reviewer correctly notes, the desired computation is indeed shown in the appendix, but here in Table 2: There, we compare _our_ local cuts (FW) with the LP-based local cuts from [42]. \n\nNote that both methods result in different cuts, hence one always has to take both the runtime as well as the gap closed measure into account when comparing them. The third paragraph in Appendix 2 discusses the results.\n\nAnswers to questions:\n  \n1. [Section 2] Could you clarify the relation between the polytope P and the polyhedron P_tilde? Is it always a restriction (a subset of the variables in P, such that an element is in if there exists an element in with those values?) or could it be something more general (like an affine transformation of?) and have as only requirement \"if we have a cut in, we can find a cut in? As it is, it sounds quite abstract.\n  \nIn the paper, we consistently assume that \\(P_{tilde}\\) is a subset of P, with no transformations of any kind. This will be clarified in the revised version. We have not delved into the potential application of affine transformations. While they might be theoretically possible, they would greatly complicate the process of efficiently lifting cuts to the original space. Moreover, we did not discern a distinct advantage in applying such transformations.\nThe restriction to using subsets of variables only has, in our opinion, already enough degrees of freedom (think, e.g., projecting out continuous variables in a MIP) yet enables us to find amenable subproblems quite effectively, as shown, e.g., in the case study for MKP.\n\n2. [Section 5] Downlifting vs up- and down lifting is not explained anywhere. Given that downlifting performs significantly worse on all benchmarks, it might not be worth it to include it in the main version of the paper to avoid confusion. Similarly, CMIR seems to have very little impact so unless it can be explained, it might make sense to move it to the appendix.\n\nLifting procedures are inherently problem-specific. The lack of detailed explanations for individual lifting procedures for MKP in the paper stems from our reliance on established methods from existing literature, for which we provide references. We initially included all variants in the primary experiments to align with the customary practices in MKP literature. However, acknowledging your point, we are inclined to relocate the less effective variants to the appendices in the revised version to enhance clarity.\n\n3. Would it be possible to include some more information on what the default settings of SCIP look like? Is it a reasonable baseline? Is there an indication on how many cuts (whether local or not local) it corresponds to?\n\nIn general, we understand the desire to include a thorough discussion here; nevertheless, we also see the degree of complexity that would be required to correctly reflect this in the paper. For example, the default settings in SCIP enable the use of all implemented types of cuts, but the actual application is subject to an internal cut selection procedure. While SCIP is very informative in this regard, e.g. writing out how many separators were called and how many cuts were effectively applied, a discussion here would quickly evolve out of the scope of the paper. SCIP is considered best-in-class for the academic solvers, hence the default settings usually reflect a decent baseline.\nFinally, we could offer a compromise here: Together with the revised version of the paper, we publish the SCIP log files of all the experiments contained in the paper which contain the data.\n\n4. Line 30, I don't understand what the notion of the first indices is. Is that a reference to some Mixed Integer Programming case, where only the first variables need to be integral?\n\nYour observation is accurate. In the context of MIP, the terminology would be applicable, but our focus on the IP case, where every variable is integral, requires a different explanation. In the IP scenario, LP-relaxations are undertaken as long as the solution \\(x^*\\) has fractional values across one of the n indices. We will rectify this in the revised paper.\n\n5. Figure 1 legend, is it supposed to be the L_2 projection (rather than L_t) ?\n\nYou're right; it should indeed be L_2. This oversight will be addressed in our paper's next version.\n"}, {"review_id": "ZOihpDgwib", "reviewer": "Reviewer_kHh3", "summary": "This paper presents a method for generating separating cutting planes for integer programming problems that is based on the Frank-Wolfe method for optimizing over polyhedron. It falls roughly within the existing local/Fenchel cut framework: given a point, it identifies the closest point within the feasible region by repeatedly calling a (hopefully fast) optimization oracle, and then ", "questions": "* L19: \"However, the by far most interesting case is the one we consider here\" (IP vs. MIP). This is a subjective statement that I imagine many researchers in the MIP community would (strongly!) disagree with. I'd suggest softening or removing, as this is not really necessary to justify the restriction to IP for the purposes of the paper.\n* L30: \"first p indices\" seems like it is left over from an earlier draft that considered MIP.\n* The first paragraph of Section 2 is fairly confusing, largely because you introduce two polyhedron (P and tilde{P}), but really only work with the second. As such, statements about \"valid cut\"s and \"original space\" are unclear without further qualification. I'd suggest rewriting it, and maybe adding some discussion about how P and tilde{P} should or do relate to each other: \"subproblem\" suggests some relationship (maybe containment in a projected space?), but is vague.\n* L101: You do not assume that tilde{P} is full-dimensional (just P, but see comment above), so there may not exist an interior point. \n* Figure 1: The figure and caption are a bit confusing: it's not clear what the tilde{P}_I label refers to; indices t and k are used variously in the caption and figure; there is no explicit reference to (c) in the caption, etc.\n* L151: Is the oracle required to return a solution vertex? If so, you should state that above. If not, does this affect any of the statements to follow?\n* L317: It is a bit confusing to the reader that you state a percentage solve time improvement in an unqualified manner, when it only applies to a subset of the instances in your test bed (the solved ones). Please be more explicit about this in the test (here, and also earlier in the contributions section).\n* Section: To bolster the takeaways from the computational study, it would be interesting to have more information about the relative performance on the unsolved instances. For instance: How many instances does each method solve to optimality within the time budget? What do the dual and primal/dual integrals look like for the various methods? How long does \"default\" SCIP spend in cut separation? A separate suggestion to isolate the dual effect of the new method would be to seed each method with the best known primal solution as a warm start.", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall I quite like the paper and how it stitches together some disparate, existing ideas from the optimization literature.\n\nThe paper is generally very well-written. The paper is in an area of clear interest to the Operations Research and Mathematical Optimization community, and the subject matter is consistent with a number of other papers accepted to NeurIPS in the past. The application of Frank-Wolfe in this manner is interesting and non-trivial, as the authors apply some extensions to improve its practical performance (the \"FW Gap\" characterization being chief among them). ", "weaknesses": "The results in the computational study are slightly underwhelming. A 31% improvement in solving times is nice, but this only considers \"solved\" instances and the geo-mean solve times here are quite small to begin with (6s for \"default\"). The provided solve times on all instances (including ones that terminate without proving optimality) show a significantly smaller (though still positive) speedup. Given that MIP solvers such as SCIP tend to be engineered more for hard instances than easy ones, it is difficult to know how much to read into these results without additional detail.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "\n1. L19: \"However, the by far most interesting case is the one we consider here\" (IP vs. MIP). This is a subjective statement that I imagine many researchers in the MIP community would (strongly!) disagree with. I'd suggest softening or removing, as this is not really necessary to justify the restriction to IP for the purposes of the paper.\n  \nWe understand the concern and agree that the phrasing needs refinement. Our objective wasn't to compare IP vs. MIP directly, but rather to highlight that the methods proposed in our paper are more readily applicable to the IP case. We will amend this in the revised manuscript.\n  \n2. L30: \"first p indices\" seems like it is left over from an earlier draft that considered MIP.\n\nIndeed, that is an oversight on our part, a remnant from considering the MIP case. We will revise this in the updated manuscript. Thanks!\n\n3. The first paragraph of Section 2 is fairly confusing, largely because you introduce two polyhedron (P and tilde{P}), but really only work with the second. As such, statements about \"valid cut\"s and \"original space\" are unclear without further qualification. I'd suggest rewriting it, and maybe adding some discussion about how P and tilde{P} should or do relate to each other: \"subproblem\" suggests some relationship (maybe containment in a projected space?), but is vague.\n\nWe appreciate your feedback and will work on providing a clearer relationship between the two polyhedra in the revised manuscript. tilde{P} can be thought of as a projection of P onto a lower-dimensional space.\n\n4. L101: You do not assume that tilde{P} is full-dimensional (just P, but see comment above), so there may not exist an interior point.\n\nThank you for pointing this out. We indeed have to assume that the projection is full-dimensional, which we will do in the revised manuscript.\n\n5. Figure 1: The figure and caption are a bit confusing: it's not clear what the tilde{P}_I label refers to; indices t and k are used variously in the caption and figure; there is no explicit reference to (c) in the caption, etc.\n\nThanks for pointing this out! We will definitely fix the figure in the revised version of the manuscript. While the figure itself is correct, \nthe caption does indeed contain several errors; for explanation:\n- (c) shows the iteration \"at convergence\", the reference should be in the last sentence of the caption;\n- the index \"t\" should actually be \"i\" from Figure (c). Due to our assumptions, we know that FW converges, so for every iteration k before convergence, there exists an index i > 0 such that convergence/termination occurs at iteration k + I.\n\nLastly, as we are allowed to provide one PDF page worth of figures and tables as part of our \"global\" rebuttal, we attach the updated figure there for your reference.\n\n6. L151: Is the oracle required to return a solution vertex? If so, you should state that above. If not, does this affect any of the statements to follow?\n\nThanks for raising that point. In our setting and example (MKP), the oracle indeed always returns a vertex, but this is not a requirement for the following statements, especially for the theory of FW (the property is never explicitly used). We will clarify this in the revised version.\n\n7. It is a bit confusing to the reader that you state a percentage solve time improvement in an unqualified manner, when it only applies to a subset of the instances in your test bed (the solved ones). Please be more explicit about this in the test (here, and also earlier in the contributions section).\n\nYour point is well-taken, and we apologize for any confusion. We will revise the manuscript to explicitly state what the percentage refers to.\n\n8. Section: To bolster the takeaways from the computational study, it would be interesting to have more information about the relative performance on the unsolved instances. For instance: How many instances does each method solve to optimality within the time budget? What do the dual and primal/dual integrals look like for the various methods? How long does \"default\" SCIP spend in cut separation? A separate suggestion to isolate the dual effect of the new method would be to seed each method with the best known primal solution as a warm start.\n\nWe appreciate your feedback. For all full branch-and-bound run results, the number of instances each method solved within the time limit is listed (see Tables 1 and 3). Additionally, we already exclude the effect of primal heuristics on the solution process by initializing the runs with the optimal solution values. \nThis fact is only mentioned in the Appendix - we will move this point to the main part of the paper and include details on time spent in cut separation in the revised version of the paper.\n"}, {"review_id": "Ltn2zkErsX", "reviewer": "Reviewer_XrPs", "summary": "The authors propose a new method for generated lifted cuts from a smaller projected polytope that replaces the usually-expensive LP/IP-based separation routines with an optimization-based method that uses the Frank-Wolfe algorithm. The authors present theory showing that the proposed separation routine indeed produces strong cuts. They then validate their methods via a case study on the multidimensional knapsack problems and variants.", "questions": "Methodologically, how does the (high-level) approach differ from lift-and-project? Some brief discussion of the similarities/differences would be nice to include.\n\nDo the authors think this approach would scale beyond the kinds of multi-dimensional knapsack/GAP problems studied? Those problems conveniently have efficient lifting methods, but for general MIP lifting can be expensive (requiring solutions to MIPs). (I do understand that lifting is not the focus of this paper.)\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "The proposed method is novel and is a genuinely new and interesting algorithmic development in cutting plane generation. The paper is written clearly and precisely. The need for faster separation routines that do not rely on large LPs (or even MIPs) requiring expensive column generation routines is clear, and the authors make interesting progress towards a solution.", "weaknesses": "I think the Knapsack case study could’ve used some more details, including comparisons to existing methods of lifting in this domain. E.g., how does the authors’ Frank-Wolfe based method compare to the usual pipelines of lifting for knapsack inequalities – in particular sequential up-lifting/down-lifting for minimal cover inequalities? Also, how does the authors’ separation procedure itself compare to the usual separation routines for cover inequalities (e.g., those in “Lifted Cover Inequalities for 0-1 Integer Programs: Computation” by Gu, Nemhauser, and Savelsbergh)? Does it produce similar cuts? Stronger ones? Weaker ones? Is it faster or slower? Knapsack constraints are one of the main areas where lifting really shines since it can be done fairly efficiently, so some more comparison here would be super interesting. But, I still view this paper as providing a nice contribution without the deeper dive into lifting knapsack cover inequalities.\n\nA comparison to the equivalent local cuts implementation that SCIP uses seems important to include, but maybe SCIP doesn’t do anything like this? Tangentially, to what extent are local cuts actually used by general-purpose MIP solvers? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Comments on weakness:  \n1. [...] E.g., how does the authors’ Frank-Wolfe based method compare to the usual pipelines of lifting for knapsack inequalities – in particular sequential up-lifting/down-lifting for minimal cover inequalities?  [...] Also, how does the authors’ separation procedure itself compare to the usual separation routines for cover inequalities (e.g., those in “Lifted Cover Inequalities for 0-1 Integer Programs: Computation” by Gu, Nemhauser, and Savelsbergh)? Does it produce similar cuts? Stronger ones? Weaker ones? Is it faster or slower? [...]\n\nThe mentioned knapsack separation routines are applied in the default settings of SCIP. Since SCIP is considered state-of-the-art for the open source solvers, we assume that its internal cut selection mechanism would prefer these cuts if they were helpful.\nWhile SCIP is very informative about how many separators were called and how many cuts were effectively applied, we did not analyze this further in the paper, as a discussion here would quickly evolve out of the scope of the paper. However, we would gladly publish all the SCIP logs from the experiments alongside the revised manuscript.\n\n\n2. A comparison to the equivalent local cuts implementation that SCIP uses seems important to include, but maybe SCIP doesn’t do anything like this? Tangentially, to what extent are local cuts actually used by general-purpose MIP solvers?\n\nSCIP currently dooes not include an implementation of either local cuts method (see, e.g. https://www.scipopt.org/doc/html/group__SEPARATORS.php for a list of cuts available). Hence, our experiments focus on comparing our FW-local cuts to \"all that SCIP has to offer\", i.e., the default configuration which permits all cuts subject to SCIP's built-in cut selection mechanism.\n\nAnswers to questions\n  \n1. Methodologically, how does the (high-level) approach differ from lift-and-project? Some brief discussion of the similarities/differences would be nice to include.\n\nWe appreciate your suggestion and agree that a comparative discussion would be useful. Lift-and-project methods share some high-level ideas with our approach, such as exploring solutions in a different space and then projecting back to the original space. However, their mechanics are significantly different. Lift-and-project methods convert the problem, e.g., into an equivalent quadratic formulation to simulate non-linearity in integer programs, which is then linearized in the lifting phase. Afterward, this extended formulation is projected onto the original variable space, resulting in a strengthened binary MIP formulation. This step is the projection phase. In contrast, our approach, maintains the linearity of the program. We work with a trivial projection of the polytope onto a lower-dimensional variable space where the problem can be solved more efficiently, and then the solution is lifted back to the full variable space. We will elaborate on this comparison in the revised manuscript.\n\n2. Do the authors think this approach would scale beyond the kinds of multi-dimensional knapsack/GAP problems studied? Those problems conveniently have efficient lifting methods, but for general MIP lifting can be expensive (requiring solutions to MIPs). (I do understand that lifting is not the focus of this paper.)\n\nWe recognize that the effectiveness of our approach partly relies on the availability of efficient lifting routines, which might not be the case for all problem classes. However, the final impact of our method on the overall solving process involves a tradeoff between the runtime of the lifting routine and the strength of the produced cuts, both of which can vary with the problem class. Thus, even problem classes with less efficient lifting routines might theoretically benefit from our method. Many significant and widely applicable problem classes do possess efficient lifting methods and local cuts have been successfully applied to them (as referenced in the \"Related Work\" section). For some problems, no lifting is required at all (for instance, when the Trivial Lifting Lemma holds, see Section 3.2), such as with the Linear Ordering Problem. We did not conduct thorough experiments on other problem classes, but this is a part of our planned future work. It is challenging to make confident predictions due to the numerous factors involved in evaluating MIP/IP solver performance.\n"}, {"review_id": "IdKWvBx9x2", "reviewer": "Reviewer_avng", "summary": "The paper proposes an efficient algorithm for learning local cuts used in integer programming relaxations. The algorithm uses a variant of the Frank-Wolfe algorithm and employs a stopping criterion for reducing the number of iterations during the application of the Frank-Wolfe algorithm. The paper showcases the effectiveness of the proposed algorithm by applying it to the multidimensional knapsack problem and reports its findings. \n\nI have read the authors' rebuttal.", "questions": "Please include a discussion about the relevance of the problem to NeurIPS audience. I appreciate the theoretical work, but I am not sure about its relevance to the broad  NeurIPS audience. At least this warrants further discussion and motivation, which are currently lacking from the paper.", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "* The paper contributes to solving the generic IP problem efficiently.\n* The paper includes experimental results showing the usefulness of the proposed algorithm.", "weaknesses": "The paper lack a discussion about the relevant of the studied problem to the NeurIPS community. I am not sure how much the results would appeal to the broad NeurIPS audience.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": " \n1. The paper lack a discussion about the relevant of the studied problem to the NeurIPS community. I am not sure how much the results would appeal to the broad NeurIPS audience. Please include a discussion about the relevance of the problem to NeurIPS audience. I appreciate the theoretical work, but I am not sure about its relevance to the broad NeurIPS audience. At least this warrants further discussion and motivation, which are currently lacking from the paper.\n\nWe understand the concern about the direct relevance of our work to the broader NeurIPS audience. Although the intersection of learning methods and integer problem-solving might not be a mainstream application in Machine Learning, there has been a rising trend of studies in this area, spurred by advancements in learning techniques. In fact, several past NeurIPS publications align with our topic. Some of these include:\n\n- Wu, Y., Song, W., Cao, Z., Zhang, J., Gupta, A., & Lin, M. S. (2022). Graph Learning Assisted Multi-Objective Integer Programming. In NeurIPS.\n- Chmiela, A., Khalil, E., Gleixner, A., Lodi, A., & Pokutta, S. (2021). Learning to Schedule Heuristics in Branch-and-Bound. In NeurIPS.\n- Wu, Y., Song, W., Cao, Z., & Zhang, J. (2021). Learning large neighborhood search policy for integer programming. In NeurIPS.\n- Chen, X., & Tian, Y. (2019). Learning to perform local rewriting for combinatorial optimization. In NeurIPS.\n- He, H., Daume III, H., & Eisner, J. M. (2014). Learning to search in branch and bound algorithms. In NeurIPS.\n\nThis point is also reinforced by the review of reviewer kHh3 (see \"Strengths\").\n\nGiven this context, we are confident that our interdisciplinary exploration holds value for the community. Such work could stimulate knowledge exchange and potentially motivate machine learning enthusiasts to devise novel applications or enhancements in optimization problems using machine learning techniques. Acknowledging your feedback, we agree that the paper should offer more clarity on the significance of employing learning methods in integer programming. To this end, we will add a dedicated paragraph in our paper's revised version to elucidate this relationship further.\n\n"}]

Author rebuttal:
Dear Reviewers,

We sincerely thank you all for reviewing our paper. Your insights and suggestions have been incredibly valuable in refining our work and will undoubtedly lead to enhancing the quality and impact of our research. We appreciate your time and dedication to peer review and are grateful for your contributions. 

Below you will find our answers to each specific question you raised. Additionally, we use the optional PDF page for figures and tables to provide the updated Figure 1, following the incorporation of comments from Reviewer kHh3.

Thank you once again for your valuable feedback.

Sincerely,

Authors

Meta-review: The paper focuses on the cutting plane methods for integer programming and presents an efficient separation oracle that first attempts to find facets of a polytope in reduced dimensions (by solving the associated subproblem by using the Frank-Wolfe algorithm), and subsequently transforming them into cutting planes for the actual problem. While some reviewers raised concerns that the method falls out of the scope of the conference, I believe that the paper fits within the Optimization subject area. Not only have both cutting plane and Frank-Wolfe methods received attention within this community across various applications, but this community has also played a significant role in the theoretical development of such optimization methods in the past. The remaining comments for the paper were largely positive, although many reviewers noted some shortcomings in the numerical experiments. I strongly encourage the authors to carefully consider all feedback and address these points in the final version of the paper.
Decision: Accept (poster)