• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

3小时前 1次浏览

# 02 Column Selection

• Let (ell) be the CG iteration number
• (Omega_{ell}) the set of columns present in the RMP at the start of iteration (ell)
• (mathcal{G}_{ell}) the generated columns at this iteration
• For each column (p in mathcal{G}_{ell}), we define a decision variable (y_p) that takes value one if column (p) is selected and zero otherwise

# 03 Graph Neural Networks

• (h^{(k)}_v) be the representation vector of node (v in V)（注意和(x_v)区分开）at iteration (k=0,1,…,K)
• Let (mathcal{N}(v)) be the set of neighbor (adjacent) nodes of (v in V)

# 04 A Bipartite Graph for Column Selection

nodes (C). An edge ((v, c)) exists between a node (v in V) and a node (c in C) if column (v) contributes to constraint (c). 这样做的好处是可以在节点(c)上附加特征向量，例如对偶解的信息，如下图(a)所示：

As described in the previous section, we start by initializing the representation vectors of both the column and constraint nodes by the feature vectors (x_v) and (x_c), respectively (steps 1 and 2). For each iteration (k), we perform the two phases: updating the constraint representations (steps 4 and 5), then the column ones (steps 6 and 7). The sum function is used for the `aggr` function and the vector concatenation for the `comb` function.

The functions (phi^{(k)}_C, psi^{(k)}_C, phi^{(k)}_V), and (psi^{(k)}_V) are two-layer feed forward neural networks with rectified linear unit (`ReLU`) activation functions and out is a three-layer feed forward neural network with a sigmoid function for producing the final probabilities (step 9).

A weighted binary cross entropy loss is used to evaluate the performance of the model, where the weights are used to deal with the imbalance between the two classes. Indeed, about 90% of the columns belong to the unselected class, that is, their label (y_v = 0).

# 05 数据采集

• The sets of column and constraint nodes;
• A sparse matrix (E in mathbb{R}^{ntimes m}) storing the edges;
• A column feature matrix (X^V in mathbb{R}^{ntimes d}), where (n) is the number of columns and d the number of column features;
• A constraint feature matrix (X^C in mathbb{R}^{ntimes p}), where (m) is the number of constraints and (p) the number of constraint features;
• The label vector y of the newly generated
columns in (mathcal{G}‘).

# 06 Case Study I: Vehicle and Crew Scheduling Problem

## 6.2 Comparison

• `No selection (NO-S)`: This is the standard CG algorithm with no selection involved, with the use of the acceleration strategies described in Section 2.
• `MILP selection (MILP-S)`: The MILP is used to select the columns at each iteration, with 50% additional columns to avoid convergence issues. Because the MILP is considered to be the expert we want to learn from and we are looking to replace it with a fast approximation, the total computational time does not include the time spent solving the MILP.
• `GNN selection (GNN-S)`: The learned model is used to select the columns. At every CG iteration, the column features are extracted, the predictions are obtained, and the selected columns are added to the RMP.
• `Sorting selection (Sort-S)`: The generated columns are sorted by reduced cost in ascending order, and a subset of the columns with the lowest reduced cost are selected. The number of columns selected is on average the same as with the GNN selection.
• `Random selection (Rand-S)`: A subset of the columns is selected randomly. The number of columns selected is on average the same as with the GNN selection

# 07 Case Study II: Vehicle Routing Problem with Time Windows

The last column corresponds to the time reduction when comparing GNN-S with NO-S. One can see that the column selection with the GNN model gives positive results, yielding average reductions ranging from 20%–29%. These reductions could have been larger if the number of CG iterations performed had not increased.

# 参考文献

• [1] Mouad Morabit, Guy Desaulniers, Andrea Lodi (2021) Machine-Learning–Based Column Selection for Column Generation. Transportation Science