CaVE: A Cone-Aligned Approach for Fast Predict-then-optimize with Binary Linear Programs

Abstract

The end-to-end predict-then-optimize framework, also known as decision-focused learning, has gained popularity for its ability to integrate optimization into the training procedure of machine learning models that predict the unknown cost (objective function) coefficients of optimization problems from contextual instance information. Naturally, most of the problems of interest in this space can be cast as integer linear programs. In this work, we focus on binary linear programs (BLPs) and propose a new end-to-end training method to predict-then-optimize. Our method, Cone-aligned Vector Estimation (CaVE), aligns the predicted cost vectors with the normal cone corresponding to the true optimal solution of a training instance. When the predicted cost vector lies inside the cone, the optimal solution to the linear relaxation of the binary problem is optimal. This alignment not only produces decision-aware learning models, but also dramatically reduces training time as it circumvents the need to solve BLPs to compute a loss function with its gradients. Experiments across multiple datasets show that our method exhibits a favorable trade-off between training time and solution quality, particularly with large-scale optimization problems such as vehicle routing, a hard BLP that has yet to benefit from predict-then-optimize methods in the literature due to its difficulty.

A More Experiments

1.1 A.1 TSP Relaxation

To enhance training efficiency, it has been proposed in [17] that a linear relaxation can be used as a substitute for the original BLP during training. Because the DFJ formulation utilizes constraint generation to handle subtour elimiation constraints, it is challenging to achieve linear relaxation due to the exponential number of constraints. In this study, we used the LP relaxation of the Miller-Tucker-Zemlin (MTZ) formulation [18] of the TSP, and trained SPO+ Rel and PFYL Rel on the same TSP instances with 20 and 50 nodes. Although relaxation methods are more efficient than CaVE in TSP20, they result in higher regret. As the size of the model increases, the relaxation approach also loses its efficiency advantage (Tables 7 and 8).

Table 7. Experimental Results for TSP20 Relaxation

Table 8. Experimental Results for TSP50 Relaxation

1.2 A.2 CVRP Relaxation

Similarly, the CVRP formulation with k-path cuts also struggles to obtain a linear relaxation. Thus, the MTZ formulation can be modified with constraints

$$ u_j - u_i \ge Q (x_{ij} - 1) + q_j \quad \forall i \ne j, i \ne 0, j \ne 0 $$

for subtour elimilation and customer demand, where Q is the capacity and $q_i$ is the demand of customer i. The SPO+ Rel and PFYL Rel are trained for the same VRP instances with 20 customers. While the linear relaxation approach demonstrates high efficiency in these scenarios, it does not guarantee a low regret compared to CaVE (Table 9).

Table 9. Experimental Results for CVRP20 Relaxation