summaries: This submission addresses the problem of constructing a good initialized pretrained network for the object detection task. Compared to previous work, the authors argue that pretraining should be adapted to object detection by focusing on object-level features learning. Instead of pretraining on ImageNet, the authors pretrain the model by designing an object level contrastive learning framework. Experiments on COCO and PASCAL show that the proposed method achieves higher performance.

summaries: The paper aims to design a self-supervised pre-training method for the downstream object detection task.  The authors propose to perform self-supervised object-level representation learning. Specifically, this method uses selective search to obtain object proposals in unlabeled images and extract the object-level features as in Mask R-CNN. Clear improvements have been achieved on COCO object detection and instance segmentation with Mask R-CNN.

summaries: This paper provides a self supervised method tailored for object detection (in the RCNN paradigm), inspired from BYOL.   The general idea is to use a non-parametric method (selective search) to generate some boxes, then apply a BYOL-style loss between ROI-Aligned features of each box coming from different augmentations of the image.   It differs from other SSL methods (BYOL, SWAV,...) in that it instead of pretraining solely the backbone, this methods ensures that all the components of the detector (FPN, RCNN head) are pre-trained.  It shows convincing results on COCO and pascal as well as some subsets, in a few shot setting. The code is made available as part of the supplementary, thus helping with reproducibility.

summaries: This paper proposes SoCo, a method for self-supervised representation learning for downstream object detection and instance segmentation tasks.  They argue for stronger alignment between downstream tasks and self-supervised pre-training. They demonstrate this in the case of object detection by (a) developing a representation learning scheme that encourages object level scale and translation invariance and (b) pre-training several components of the downstream detector such as FPN and R-CNN head unlike prior work which mostly just trains the ResNet backbone.  The former property will help their model detect objects at several locations and scales as is needed for object detection.  The latter property helps them get stronger alignment between the upstream and downstream setups. To this end they propose "scale aware assignment". The ideas is that, representations for small objects are taken from finer FPN pyramid levels and for bigger objects are taken from coarser FPN pyramid levels. This matches what happens in the actual FPN where anchors at finer pyramid levels are smaller and at coarser pyramid levels are bigger.  The overall recipe is as follows: Selective search, a hand-crafted region proposal technique, is used to suggest boxes on all images. K of these boxes are randomly selected in each training step per image and three views of that image are constructed using random resized crop and resize operations. FPN features are extracted using RoiAlign for these box locations using "scale aware assignment". A BYOL loss is applied between representations of the same box across the three views. As in BYOL an EMA teacher network and projection head are used.  They pretrain R50-C4 and R50-FPN  models upstream and fine-tune corresponding Mask-RCNN models downstream for MS COCO and Pascal VOC object detection and MS COCO instance segmentation. Low data regime is explored using 5% and 10% "Mini" COCO setups. ImageNet linear eval results are included in the appendix. Ablation experiments evaluate whether stronger alignment in terms of architecture between pre-training and fine-tuning were helpful and sensitivity w.r.t. hyper-parameters such as view size, momentum for EMA, batch-size etc.

abstractText: Image-level contrastive representation learning has proven to be highly effective as a generic model for transfer learning. Such generality for transfer learning, however, sacrifices specificity if we are interested in a certain downstream task. We argue that this could be sub-optimal and thus advocate a design principle which encourages alignment between the self-supervised pretext task and the downstream task. In this paper, we follow this principle with a pretraining method specifically designed for the task of object detection. We attain alignment in the following three aspects: 1) object-level representations are introduced via selective search bounding boxes as object proposals; 2) the pretraining network architecture incorporates the same dedicated modules used in the detection pipeline (e.g. FPN); 3) the pretraining is equipped with object detection properties such as object-level translation invariance and scale invariance. Our method, called Selective Object COntrastive learning (SoCo), achieves state-of-the-art results for transfer performance on COCO detection using a Mask R-CNN framework. Code is available at https://github.com/hologerry/SoCo.

authors:
Jia Deng
Wei Dong
Richard Socher
Li-Jia Li
Kai Li
Li Fei-Fei

title: Imagenet: A largescale hierarchical image database

venue: IEEE conference on computer vision and pattern recognition,

authors:
Zhirong Wu
Yuanjun Xiong
X Yu Stella
Dahua Lin

title: Unsupervised feature learning via non-parametric instance discrimination

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Jean-Bastien Grill
Florian Strub
Florent Altché
Corentin Tallec
Pierre H Richemond
Elena Buchatskaya
Carl Doersch
Bernardo Avila Pires
Zhaohan Daniel Guo
Mohammad Gheshlaghi Azar

title: Bootstrap your own latent: A new approach to self-supervised learning

venue: arXiv preprint arXiv:2006.07733,

authors:
Kaiming He
Haoqi Fan
Yuxin Wu
Saining Xie
Ross Girshick

title: Momentum contrast for unsupervised visual representation learning

venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,

authors:
Xinlei Chen
Haoqi Fan
Ross Girshick
Kaiming He

title: Improved baselines with momentum contrastive learning

venue: arXiv preprint arXiv:2003.04297,

authors:
Yonglong Tian
Chen Sun
Ben Poole
Dilip Krishnan
Cordelia Schmid
Phillip Isola

title: What makes for good views for contrastive learning

venue: arXiv preprint arXiv:2005.10243,

authors:
Mathilde Caron
Ishan Misra
Julien Mairal
Priya Goyal
Piotr Bojanowski
Armand Joulin

title: Unsupervised learning of visual features by contrasting cluster assignments

venue: arXiv preprint arXiv:2006.09882,

authors:
Xinlei Chen
Kaiming He

title: Exploring simple siamese representation learning

venue: arXiv preprint arXiv:2011.10566,

authors:
Ting Chen
Simon Kornblith
Mohammad Norouzi
Geoffrey Hinton

title: A simple framework for contrastive learning of visual representations

venue: In International conference on machine learning,

authors:
Zhenda Xie
Yutong Lin
Zheng Zhang
Yue Cao
Stephen Lin
Han Hu

title: Propagate yourself: Exploring pixel-level consistency for unsupervised visual representation learning

venue: arXiv preprint arXiv:2011.10043,

authors:
Xinlong Wang
Rufeng Zhang
Chunhua Shen
Tao Kong
Lei Li

title: Dense contrastive learning for self-supervised visual pre-training

venue: arXiv preprint arXiv:2011.09157,

authors:
Ceyuan Yang
Zhirong Wu
Bolei Zhou
Stephen Lin

title: Instance localization for selfsupervised detection pretraining

venue: arXiv preprint arXiv:2102.08318,

authors:
Olivier J Hénaff
Skanda Koppula
Jean-Baptiste Alayrac
Aaron van den Oord
Oriol Vinyals
João Carreira

title: Efficient visual pretraining with contrastive detection

venue: arXiv preprint arXiv:2103.10957,

authors:
Jasper RR Uijlings
Koen EA Van De Sande
Theo Gevers
Arnold WM Smeulders

title: Selective search for object recognition

venue: International journal of computer vision,

authors:
Tsung-Yi Lin
Piotr Dollár
Ross Girshick
Kaiming He
Bharath Hariharan
Serge Belongie

title: Feature pyramid networks for object detection

authors:
Shaoqing Ren
Kaiming He
Ross Girshick
Jian Sun

title: Faster r-cnn: Towards real-time object detection with region proposal networks

venue: arXiv preprint arXiv:1506.01497,

authors:
Kaiming He
Georgia Gkioxari
Piotr Dollár
Ross Girshick

title: Mask r-cnn

venue: In Proceedings of the IEEE international conference on computer vision,

authors:
Pascal Vincent
Hugo Larochelle
Isabelle Lajoie
Yoshua Bengio
Pierre-Antoine Manzagol
Léon Bottou

title: Stacked denoising autoencoders: Learning useful representations in a deep network with a local denoising criterion

authors:
Ruslan Salakhutdinov
Geoffrey Hinton

title: Deep boltzmann machines. In Artificial intelligence and statistics, pages 448–455

venue: PMLR,

authors:
Gustav Larsson
Michael Maire
Gregory Shakhnarovich

title: Colorization as a proxy task for visual understanding

authors:
Carl Doersch
Abhinav Gupta
Alexei A Efros

title: Unsupervised visual representation learning by context prediction

authors:
Deepak Pathak
Philipp Krahenbuhl
Jeff Donahue
Trevor Darrell
Alexei A Efros

title: Context encoders: Feature learning by inpainting

authors:
Spyros Gidaris
Praveer Singh
Nikos Komodakis

title: Unsupervised representation learning by predicting image rotations

venue: arXiv preprint arXiv:1803.07728,

title: Data-efficient image recognition with contrastive predictive coding

venue: In International Conference on Machine Learning,

authors:
Jure Zbontar
Li Jing
Ishan Misra
Yann LeCun
Stéphane

title: Deny. Barlow twins: Selfsupervised learning via redundancy reduction

venue: arXiv preprint arXiv:2103.03230,

authors:
Mathilde Caron
Hugo Touvron
Ishan Misra
Hervé Jégou
Julien Mairal
Piotr Bojanowski
Armand Joulin

title: Emerging properties in self-supervised vision transformers

venue: arXiv preprint arXiv:2104.14294,

authors:
Mathilde Caron
Piotr Bojanowski
Julien Mairal
Armand Joulin

title: Unsupervised pretraining of image features on non-curated data

venue: In Proceedings of the IEEE/CVF International Conference on Computer Vision,

authors:
Priya Goyal
Mathilde Caron
Benjamin Lefaudeux
Min Xu
Pengchao Wang
Vivek Pai
Mannat Singh
Vitaliy Liptchinsky
Ishan Misra
Armand Joulin

title: Self-supervised pretraining of visual features in the wild

venue: arXiv preprint arXiv:2103.01988,

authors:
Pedro O Pinheiro
Amjad Almahairi
Ryan Y Benmaleck
Florian Golemo
Aaron Courville

title: Unsupervised learning of dense visual representations

venue: arXiv preprint arXiv:2011.05499,

authors:
Pablo Arbeláez
Jordi Pont-Tuset
Jonathan T Barron
Ferran Marques
Jitendra Malik

title: Multiscale combinatorial grouping

authors:
Zhigang Dai
Bolun Cai
Yugeng Lin
Junying Chen

title: Up-detr: Unsupervised pre-training for object detection with transformers

authors:
Songtao Liu
Zeming Li
Jian Sun

title: Self-emd: Self-supervised object detection without imagenet

venue: arXiv preprint arXiv:2011.13677,

authors:
Bharat Singh
Larry S. Davis

title: An analysis of scale invariance in object detection - snip, 2018

authors:
Ross Girshick
Jeff Donahue
Trevor Darrell
Jitendra Malik

title: Rich feature hierarchies for accurate object detection and semantic segmentation

title: Fast r-cnn

authors:
Kaiming He
Xiangyu Zhang
Shaoqing Ren
Jian Sun

title: Deep residual learning for image recognition

authors:
Sergey Ioffe
Christian Szegedy

title: Batch normalization: Accelerating deep network training by reducing internal covariate shift

authors:
Vinod Nair
Geoffrey E Hinton

title: Rectified linear units improve restricted boltzmann machines

venue: In Icml,

authors:
Yang You
Igor Gitman
Boris Ginsburg

title: Scaling sgd batch size to 32k for imagenet training

venue: arXiv preprint arXiv:1708.03888,

authors:
Ilya Loshchilov
Frank Hutter

title: Sgdr: Stochastic gradient descent with warm restarts

venue: arXiv preprint arXiv:1608.03983,

authors:
Priya Goyal
Piotr Dollár
Ross Girshick
Pieter Noordhuis
Lukasz Wesolowski
Aapo Kyrola
Andrew Tulloch
Yangqing Jia
Kaiming He

title: Accurate, large minibatch sgd: Training imagenet in 1 hour

venue: arXiv preprint arXiv:1706.02677,

authors:
Tsung-Yi Lin
Michael Maire
Serge Belongie
James Hays
Pietro Perona
Deva Ramanan
Piotr Dollár
C Lawrence Zitnick

title: Microsoft coco: Common objects in context

venue: In European conference on computer vision,

authors:
Mark Everingham
Luc Van Gool
Christopher KI Williams
John Winn
Andrew Zisserman

title: The pascal visual object classes (voc) challenge

authors:
Tete Xiao
Colorado J Reed
Xiaolong Wang
Kurt Keutzer
Trevor Darrell

title: Region similarity representation learning

venue: arXiv preprint arXiv:2103.12902,

authors:
Agrim Gupta
Piotr Dollar
Ross Girshick

title: Lvis: A dataset for large vocabulary instance segmentation

authors:
Tsung-Yi Lin
Priya Goyal
Ross Girshick
Kaiming He
Piotr Dollár

title: Focal loss for dense object detection

authors:
Zhi Tian
Chunhua Shen
Hao Chen
Tong He

title: Fcos: Fully convolutional one-stage object detection

venue: In Proceedings of the IEEE/CVF international conference on computer vision,

authors:
Kai Chen
Jiaqi Wang
Jiangmiao Pang
Yuhang Cao
Yu Xiong
Xiaoxiao Li
Shuyang Sun
Wansen Feng
Ziwei Liu
Jiarui Xu

title: Mmdetection: Open mmlab detection toolbox and benchmark

venue: arXiv preprint arXiv:1906.07155,

heading: 1 Introduction

text:
Pretraining and finetuning has been the dominant paradigm of training deep neural networks in computer vision. Downstream tasks usually leverage pretrained weights learned on large labeled datasets such as ImageNet [1] for initialization. As a result, supervised ImageNet pretraining has been prevalent throughout the field. Recently, self-supervised pretraining [2, 3, 4, 5, 6, 7, 8, 9] has achieved considerable progress and alleviated the dependency on labeled data. These methods aim to learn generic visual representations for various downstream tasks by means of image-level pretext tasks, such as instance discrimination. Some recent works [10, 11, 12, 13] observe that the image-level representations are sub-optimal for dense prediction tasks such as object detection and semantic segmentation. A potential reason is that image-level pretraining may overfit to holistic representations and fail to learn properties that are important outside of image classification.
The goal of this work is to develop self-supervised pretraining that is aligned to object detection. In object detection, bounding boxes are widely adopted as the representation for objects. Translation and scale invariance for object detection are reflected by the location and size of the bounding boxes. An obvious representation gap exists between image-level pretraining and the object-level bounding boxes of object detection.
Motivated by this, we present an object-level self-supervised pretraining framework, called Selective Object COntrastive learning (SoCo), specifically for the downstream task of object detection. To introduce object-level representations into pretraining, SoCo utilizes off-the-shelf selective search [14] to generate object proposals. Different from prior image-level contrastive learning methods which
∗Equal contribution.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
treat the whole image as an instance, SoCo treats each object proposal in the image as an independent instance. This enables us to design a new pretext task for learning object-level visual representations with properties that are compatible with object detection. Specifically, SoCo constructs object-level views where the scales and locations of the same object instance are augmented. Contrastive learning follows to maximize the similarity of the object across augmented views.
The introduction of the object-level representation also allows us to further bridge the gap in network architecture between pretraining and finetuning. Object detection often involves dedicated modules, e.g., feature pyramid network (FPN) [15], and special-purpose sub-networks, e.g., R-CNN head [16, 17]. In contrast to image-level contrastive learning methods where only feature backbones are pretrained and transferred, SoCo performs pretraining over all the network modules used in detectors. As a result, all layers of the detectors can be well-initialized.
Experimentally, the proposed SoCo achieves state-of-the-art transfer performance from ImageNet to COCO. Concretely, by using Mask R-CNN with an R50-FPN backbone, it obtains 43.2 APbb / 38.4 APmk on COCO with a 1× schedule, which are +4.3 APbb / +3.0 APmk better than the supervised pretraining baseline, and 44.3 APbb / 39.6 APmk on COCO with a 2× schedule, which are +3.0 APbb / +2.3 APmk better than the supervised pretraining baseline. When transferred to Mask R-CNN with an R50-C4 backbone, it achieves 40.9 APbb / 35.3 APmk and 42.0 APbb / 36.3 APmk on the 1× and 2× schedule, respectively.

heading: 2 Related Work

text:
Unsupervised feature learning has a long history in training deep neural networks. Auto-encoders [18] and Deep Boltzmann Machines [19] learn layers of representations by reconstructing image pixels. Unsupervised pretraining is often used as a method for initialization, which is followed by supervised training on the same dataset such as handwritten digits for classification.
Recent advances in unsupervised learning, especially self-supervised learning, tend to formulate the problem in a transfer learning scenario, where pretraining and finetuning are trained on different datasets with different purposes. Pretext tasks such as colorization [20], context prediction [21], inpainting [22] and rotation prediction [23] force the network to learn semantic information in order to solve the pretext tasks. Contrastive methods based on the instance discrimination pretext task [2] learn to map augmented views of the same instance to similar embeddings. Such approaches [24, 4, 5, 9, 25, 26] have shown strong transfer ability for a number of downstream tasks, sometimes even outperforming the supervised counterpart by large margins [4].
With new technical innovations such as learning clustering assignments [7], large-scale contrastive learning has been successfully applied on non-curated data sets [27, 28]. While the linear evaluation result on ImageNet classification has improved significantly [3], the progress on transfer performance for dense prediction tasks has been limited. Due to this, a growing number of works investigate pretraining specifically for object detection and semantic segmentation. The idea is to shift imagelevel representations to pixel-level or region-level representations. VADer [29], PixPro [10] and DenseCL [11] propose to learn pixel-level representations by matching point features of the same physical location under different views. InsLoc [12] learns to match region-level features from composited imagery. DetCon [13] additionally uses the bottom-up segmentation of MCG [30] for supervising intra-segment pixel variations. UP-DETR [31] proposes a pretext task named random query patch detection to pretrain DETR detector. Self-EMD [32] explores self-supervised representation learning for object detection without using Imagenet images.
Our work is also motivated and inspired by object detection methods which advocate architectures and training schemes invariant to translation and scale transformations [15, 33]. We find that incorporating them in the pretraining stage also benefits object detection, which has largely been overlooked in previous self-supervised learning works.

heading: 3 Method

text:
We introduce a new contrastive learning method which maximizes the similarity of object-level features representing different augmentations of the same object. Meanwhile, we introduce architectural alignment and important properties of object detection into pretraining when designing the objectlevel pretext task. We use an example where transfer learning is performed on Mask-RCNN with a R50-FPN backbone to illustrate the core design principles. To further demonstrate the extensibility
and flexibility of our method, we also apply SoCo on a R50-C4 structure. In this section, we first present an overview of the proposed SoCo in Section 3.1. Then we describe the process of object proposal generation and view construction in Section 3.2. Finally, the object-level contrastive learning and our design principles are introduced in Section 3.3.

heading: 3.1 Overview

text: Figure 1 displays an overview of SoCo. SoCo aims to align pretraining to object detection in two aspects: 1) network architecture alignment between pretraining and object detection; 2) introducing central properties of detection. Concretely, besides pretraining a backbone as done in existing selfsupervised contrastive learning methods, SoCo also pretrains all the network modules used in an object detector, such as FPN and the head in the Mask R-CNN framework. As a result, all layers of the detector can be well-initialized. Furthermore, SoCo strives to learn object-level representations which are not only meaningful, but also invariant to translation and scale. To achieve this, it encourages diversity of scales and locations of objects by constructing multiple augmented views and applying a scale-aware assignment strategy for different levels of a feature pyramid. Finally, object-level contrastive learning is applied to maximize the feature similarity of the same object across augmented views.

heading: 3.2 Data Preprocessing

text:
Object Proposal Generation. Inspired by R-CNN [34] and Fast R-CNN [35], we use selective search [14], an unsupervised object proposal generation algorithm which takes into account color similarity, texture similarity, size of region and fit between regions, to generate a set of object proposals for each of the raw images. We represent each object proposal as a bounding box b = {x, y, w, h}, where (x, y) denotes the coordinates of the bounding box center, and w and h are the corresponding width and height, respectively. We keep only the proposals that satisfy the following requirements: 1) 1/3 ≤ w/h ≤ 3; 2) 0.3 ≤ √ wh/ √ WH ≤ 0.8, where W and H denote width and height of the input image. The object proposal generation step is performed offline. In each training iteration, we randomly select K proposals for each input image.
View Construction. Three views, namely V1, V2 and V3, are used in SoCo. The input image is resized to 224× 224 to obtain V1. Then we apply a random crop with a scale range of [0.5, 1.0] on V1 in generating V2. V2 is then resized to the same size as V1 and object proposals outside of V2 are dropped. Next, we downsample V2 to a fixed size (e.g. 112 × 112) to produce V3. In all of these cases, the bounding boxes transformed according to the cropping and resizing of the RGB images
(see Figure 1, Data Preprocessing). Finally, each view is randomly and independently augmented. We adopt the augmentation pipeline of BYOL [3] but discard the random crop augmentation since spatial transformation is already applied on all three views. Notice that the scale and location of the same object proposal are different across the augmented views, which enables the model to learn translation-invariant and scale-invariant object-level representations.
Box Jitter. To further encourage variance of scales and locations of object proposals across views, we adopt a box jitter strategy on the generated proposals as an object-level data augmentation. Specifically, given an object proposal b = {x, y, w, h}, we randomly generate a jittered box b̂ = {x̂, ŷ, ŵ, ĥ} as follows: 1) x̂ = x + r · w; 2) ŷ = y + r · h; 3) ŵ = w + r · w; 4) ĥ = h + r · h, where r ∈ [−0.1, 0.1]. The box jitter is randomly applied on each proposal with a probability of 0.5.

heading: 3.3 Object-Level Contrastive Learning

text:
The goal of SoCo is to align pretraining to object detection. Here, we use the representative framework Mask R-CNN [17] with feature pyramid network (FPN) [15] to demonstrate our key design principles. The alignment mainly involves aligning the pretraining architecture with that of object detection and integrating important object detection properties such as object-level translation invariance and scale invariance into the pretraining.
Aligning Pretraining Architecture to Object Detection. Following Mask R-CNN, we use a backbone with FPN as the image-level feature extractor f I . We denote the output of FPN as {P2, P3, P4, P5} with a stride of {4, 8, 16, 32}. Here, we do not use P6 due to its low resolution. With the bounding box representation b, RoIAlign [17] is applied to extract the foreground feature from the corresponding scale level. For further architectural alignment, we additionally introduce an R-CNN head fH into pretraining. The object-level feature representation h of bounding box b is extracted from an image view V as:
h = fH(RoIAlign(f I(V ), b)). (1)
SoCo uses two neural networks to learn, namely an online network and a target network. The online network and the target network share the same architecture but with different sets of weights. Concretely, the target network weights f Iξ , f H ξ are the exponential moving average (EMA) with the momentum coefficient τ of the online parameters f Iθ and f H θ . Denote the set of object proposals {bi} considered in the image. Let hi be the object-level representation of proposal bi in view V1, and h′i, h ′′ i be the representation of bi in view V2, V3. They are extracted using the online network and the target network respectively,
hi = f H θ (RoIAlign(f I θ (V1), bi)), (2)
h′i = f H ξ (RoIAlign(f I ξ (V2), bi)), h ′′ i = f H ξ (RoIAlign(f I ξ (V3), bi)). (3)
We follow BYOL [3] for learning contrastive representations. The online network is appended with a projector gθ, and a predictor qθ for obtaining latent embeddings. Both gθ and qθ are two-layer MLPs. The target network is only appended with the projector gξ for avoiding trivial solutions. We use vi, v′i and v′′i to denote the latent embeddings of object-level representations {hi, h ′ i, h ′′ i }, respectively:
vi = qθ(gθ(hi)), v ′ i = gξ(h ′ i), v ′′ i = gξ(h ′′ i ). (4)
The contrastive loss for the i-th object proposal is defined as:
Li = −2 · 〈vi, v′i〉 ‖vi‖2 · ‖v′i‖2 − 2 · 〈vi, v ′′ i 〉 ‖vi‖2 · ‖v′′i ‖2 . (5)
Then we can formulate the overall loss function for each image as:
L = 1 K K∑ i=1 Li, (6)
where K is the number of object proposals. We symmetrize the loss L in Eq. 6 by separately feeding V1 to the target network and {V2, V3} to the online network to compute L̃. At each training iteration, we perform a stochastic optimization step to minimize LSoCo = L+ L̃.
Scale-Aware Assignment. Mask R-CNN with FPN uses the IoU between anchors and ground-truth boxes to determine positive samples. It defines anchors to have areas of {322, 642, 1282, 2562} pixels on {P2, P3, P4, P5}, respectively, which means ground-truth boxes of scale within a range are assigned to a specific pyramid level. Inspired by this, we propose a scale-aware assignment strategy, which greatly encourages the pretraining model to learn object-level scaleinvariant representations. Concretely, we assign object proposals of area within a range of {0 − 482, 492 − 962, 972 − 1922, 1932 − 2242} pixels to {P2, P3, P4, P5}, respectively. Notice that the maximum proposal size is 224× 224 since all of the views are resized to a fixed resolution smaller than 224. The advantage is that the same object proposals at different scales are encouraged to learn consistent representations through contrastive learning. As a result, SoCo learns object-level scale-invariant visual representations, which is important for object detection.
Introducing Properties of Detection to Pretraining. Here, we discuss how SoCo promotes important properties of object detection in the pretraining. Object detection uses tight bounding boxes to represent objects. To introduce object-level representations, SoCo generates object proposals by selective search. Translation invariance and scale invariance at the object level are regarded as the most important properties for object detection, i.e., feature representations of objects belonging to same category should be insensitive to scale and location. Recall that V2 is a randomly cropped patch of V1. Random cropping introduces box shift and thus contrastive learning between V1 and V2 encourages the pretraining model to learn location-invariant representations. V3 is generated by downsampling V2, which results in a scale augmentation of object proposals. With our scale-aware assignment strategy, the contrastive loss between V1 and V3 guides the pretraining towards learning scale-invariant visual representations.
Extending to Other Object Detectors. SoCo can be easily extended to align to other detectors besides Mask R-CNN with FPN. Here, we apply SoCo to Mask R-CNN with a C4 structure, which is a popular non-FPN detection framework. The modification is three-fold: 1) for all object proposals, RoIAlign is performed on C4; 2) the R-CNN head is replaced by the entire 5-th residual block; 3) view V3 is discarded and the remaining V1 and V2 are kept for object-level contrastive learning. Experiments and comparisons with state-of-the-art methods in Section 4.3 demonstrate the extensibility and flexibility of SoCo.

heading: 4 Experiments

heading: 4.1 Pretraining Settings

text:
Architecture. Through the introduction of object proposals, the architectural discrepancy is reduced between pretraining and downstream detection finetuning. Mask R-CNN [17] is a commonly adopted framework to evaluate transfer performance. To demonstrate the extensibility and flexibility of SoCo, we provide details of SoCo alignment for the detection architectures R50-FPN and R50C4. SoCo-R50-FPN: ResNet-50 [36] with FPN [15] is used as the image-level feature encoder. RoIAlign [17] is then used to extract RoI features on feature maps {P2, P3, P4, P5} with a stride of {4, 8, 16, 32}. According to the image areas of object proposals, each RoI feature is then transformed to an object-level representation by the head network as in Mask R-CNN. SoCo-R50-C4: on the standard ResNet-50 architecture, we insert the RoI operation on the output of the 4-th residual block. The entire 5-th residual block is treated as the head network to encode object-level features. Both the projection network and prediction network are 2-layer MLPs which consist of a linear layer with output size 4096 followed by batch normalization [37], rectified linear units (ReLU) [38], and a final linear layer with output dimension 256.
Dataset. We adopt the widely used ImageNet [1] which consists of ∼1.28 million images for self-supervised pretraining.
Data Augmentation. Once all views are constructed, we employ the data augmentation pipeline of BYOL [3]. Specifically, we apply random horizontal flip, color distortion, Gaussian blur, grayscaling, and the solarization operation. We remove the random crop augmentation since spatial transformations have already been applied on all views.
Optimization. We use a 100-epoch training schedule in all the ablation studies and report the results of 100-epochs and 400-epochs in the comparisons with state-of-the-art methods. We use the LARS optimizer [39] with a cosine decay learning rate schedule [40] and a warm-up period of 10 epochs.
The base learning rate lrbase is set to 1.0 and is scaled linearly [41] with the batch size (lr = lrbase× BatchSize/256). The weight decay is set to 1.0 × e−5. The total batch size is set to 2048 over 16 Nvidia V100 GPUs. For the update of the target network, following [3], the momentum coefficient τ starts from 0.99 and is increased to 1 during training. Synchronized batch normalization is enabled.

heading: 4.2 Transfer Learning Settings

text:
COCO [42] and Pascal VOC [43] datasets are used for transfer learning. Detectron2 [44] is used as the code base.
COCO Object Detection and Instance Segmentation. We use the COCO train2017 set which contains ∼118k images with bounding box and instance segmentation annotations in 80 object categories. Transfer performance is evaluated on the COCO val2017 set. We adopt the Mask R-CNN detector [17] with the R50-FPN and the R50-C4 backbones. We report APbb, APbb50 and AP bb 75 for object detection, and APmk, APmk50 and AP mk 75 for instance segmentation. We report the results under the COCO 1× and 2× schedules in comparisons with state-of-the-art methods. All ablation studies are conducted on the COCO 1× schedule. Pascal VOC Object Detection. We use the Pascal VOC trainval07+12 set which contains∼16.5k images with bounding box annotations in 20 object categories as the training set. Transfer performance is evaluated on the Pascal VOC test2007 set. We report the results of APbb, APbb50 and AP bb 75 for object detection.
Optimization. All the pretrained weights except for projection and prediction are loaded into the object detection network for transfer. Following [5], synchronized batch normalization is used across all layers including the newly initialized batch normalization layers in finetuning. For both the COCO and Pascal VOC datasets, we finetune with stochastic gradient descent and a batch size of 16 split across 8 GPUs. For COCO transfer, we use a weight decay of 2.5× e−5, and a base learning rate of 0.02 that increases linearly for the first 1000 iterations and drops twice by a factor of 10, after 23 and 8 9 of the total training time. For Pascal VOC transfer, the weight decay is 1.0 × e
−4, and the base learning rate is set to 0.02 and divided by 10 at 34 and 11 12 of the total training time.

heading: 4.3 Comparison with State-of-the-Art Methods

text:
Mask R-CNN with R50-FPN on COCO. Table 1 shows the transfer results for Mask R-CNN with R50-FPN backbone. We compare SoCo with the state-of-the-art unsupervised pretraining methods on the COCO 1× and 2× schedules. We report our results under 100 epochs and 400 epochs of pretraining. On the 100-epoch training schedule, SoCo achieves 42.3 APbb / 37.6 APmk and 43.2 APbb / 38.8 APmk on the 1× and 2× schedules, respectively. Pretrained for 400 epochs, SoCo outperforms all previous pretraining methods designed for either image classification or object detection, achieving 43.0 APbb / 38.2 APmk for the 1× schedule and 44.0 APbb / 39.0 APmk for the 2×
schedule. Moreover, we propose an enhanced version named SoCo*, which constructs an additional view V4 for pretraining. Similar to the construction step of V2, V4 is a randomly cropped patch of V1. We resize V4 to 192× 192 and perform the same forward process as for V2 and V3. Compared with SoCo, SoCo* further boosts the performance and obtains an improvement of +0.2 APbb / +0.2 APmk on the 1× schedule, achieving 43.2 APbb / 38.4 APmk, and +0.3 APbb / +0.6 APmk on the 2× schedule, achieving 44.3 APbb / 39.6 APmk, respectively.
Mask R-CNN with R50-C4 on COCO. To demonstrate the extensibility and flexibility of SoCo, we also evaluate transfer performance using Mask R-CNN with R50-C4 backbone on the COCO benchmark. We report the results of SoCo under 100 epochs and 400 epochs. Table 2 compares the proposed method to previous state-of-the-art methods. Without bells and whistles, SoCo obtains state-of-the-art performance, achieving 40.9 APbb / 35.3 APmk and 42.0 APbb / 36.3 APmk on the COCO 1× and 2× schedules, respectively. Faster R-CNN with R50-C4 on Pascal VOC. We also evaluate the transfer ability of SoCo on the Pascal VOC benchmark. Following [5], we adopt Faster R-CNN with R50-C4 backbone for transfer learning. Table 3 shows the comparison. SoCo obtains an improvement of +6.2 APbb against the supervised pretraining baseline, achieving 59.7 APbb for VOC object detection.

heading: 4.4 Ablation Study

text:
To further understand the advantages of SoCo, we conduct a series of ablation studies that examine the effectiveness of object-level contrastive learning, the effects of alignment between pretraining and detection, and different hyper-parameters. For all ablation studies, we use Mask R-CNN with R50-FPN backbone for transfer learning and adopt a 100-epoch SoCo pretraining schedule. Transfer performance is evaluated under the COCO 1× schedule. For the ablation of each hyper-parameter or component, we fix all other hyper-parameters to the following default settings: view V3 with 112× 112 resolution, batch size of 2048, momentum coefficient τ = 0.99, proposal number K = 4,
box jitter and scale-aware assignment are used, FPN and R-CNN head are pretrained and transferred, and selective search is used as the proposal generator.
Effectiveness of Aligning Pretraining to Object Detection. We ablate each component of SoCo step by step to demonstrate the the effectiveness of aligning pretraining to object detection. Table 4 reports the studies. The baseline treats the whole image as an instance, without considering any detection properties or architecture alignment. It obtains 38.1 APbb and 34.4 APmk. Selective search introduces object-level representations. By leveraging generated object proposals and conducting contrastive learning at the object level, our method obtains an improvement of +2.5 APbb and +2.4 APmk. Next, we further minimize the architectural discrepancy between pretraining and object detection pipeline by introducing FPN and an R-CNN head into the pretraining architecture. We observe that only introducing FPN into pretraining slightly hurt the performance. In contrast, including both FPN and the R-CNN head improves the transfer performance to 41.2 APbb / 37.0 APmk, which verifies the effectiveness of architectural alignment between self-supervised pretraining and downstream tasks. On top of architectural alignment, we further leverage scale-aware assignment which encourages scale-invariant object-level visual representations, and an improvement of +3.5 APbb / +2.9 APmk against the baseline is found. The box jitter strategy slightly elevates performance. Finally, multiple views (V3) further directs SoCo towards learning scale-invariant and translationinvariant representations, and our method achieves 42.3 APbb and 37.6 APmk.
Ablation Study on Hyper-Parameters. Table 5 examines sensitivity to the hyper-parameters of SoCo.
Table 5(a) ablates the resolution of view V3. SoCo is found to be insensitive to the image size of V3. We use 112 × 112 as the default resolution due to its slightly better transfer performance and low training computation cost.
Table 5(b) ablates the training batch size of SoCo. It can be seen that larger or smaller batch sizes hurt the performance. We use a batch size of 2048 by default.
Table 5(c) ablates the effectiveness of object proposal generation strategies. To demonstrate the superiority of meaningful proposals generated by selective search, we randomly generate K bounding boxes in each of the training images to replace the selective search proposals (namely Random in Table 5(c)). SoCo can still yield satisfactory results using a single random bounding box to learn object-level representations, which is not surprising, since the RoIAlign operation performed on the randomly generated bounding boxes also introduces object-level representation learning. This fact indirectly demonstrates that downstream object detectors can benefit from self-supervised pretraining that involves object-level representations. However, the result is still slightly worse than the case where only one object proposal generated by selective search is used in the pretraining. For the cases where we randomly generate 4 and 8 bounding boxes, the noisy and meaningless proposals cause the pretraining to diverge. From the table, we also find that applying more object proposals (K = 8 and K = 16) generated by selective search can be harmful. One potential reason is that most of the images in the ImageNet dataset only contain a few objects, so a larger K may create duplicated and redundant proposals.
Table 5(d) ablates the momentum coefficient τ of the exponential moving average, and τ = 0.99 yields the best performance.

heading: 4.5 More Experiments

text:
Transfer Learning on LVIS Dataset. In addition to COCO and PASCAL VOC object detection, we also consider the challenging LVIS v1 dataset [46] to demonstrate the effectiveness and generality of our approach. The LVIS v1 detection benchmark contains 1203 categories in a long-tailed distribution with few training samples. It is considered to be more challenging than the COCO benchmark. We use Mask R-CNN with R50-FPN backbone and follow the standard LVIS 1× and 2× training schedules. We do not use any training or post-processing tricks. Table 6 shows the results. We can see that our method achieves +5.9 APbb/+5.6 APmk and +4.9 APbb/+4.6 APmk improvements under the LVIS 1× and 2× training schedules, respectively. Transfer Learning on Different Object Detectors. In addition to two-stage detectors, we further conduct experiments on RetinaNet [47] and FCOS [48], which are representative works for singlestage detectors and anchor-free detectors. We transfer the weights of backbone and FPN layers learned by SoCo* to RetinaNet and FCOS architectures and follow the standard COCO 1× schedule. We use MMDetection [49] as code base and default optimization configs are adopted. Table 7 shows the comparison.
Evaluation on Mini COCO. Transfer to the full COCO dataset may be of limited significance due to the extensive supervision available from its large-scale annotated training data. To further demonstrate the generalization ability of SoCo, we conduct an experiment on a mini version of the COCO dataset, named Mini COCO. Concretely, we randomly select 5% or 10% of the training data from COCO train2017 to form Mini COCO benchmarks. Mask-RCNN with R50-FPN backbone is adopted to evaluate the transfer performance on the COCO 1× schedule. COCO val2017 is still used
as the evaluation set. The other settings remain unchanged. Table 8 summarizes the results. Compared with the supervised pretraining baseline which achieves 19.4 APbb / 18.3 APmk and 24.7 APbb / 22.9 APmk on the 5% and 10% Mini COCO benchmarks, SoCo obtains large improvements of +6.6 APbb / +4.6 APmk and +5.7 APbb / +3.9 APmk, respectively. SoCo* further boosts performance with improvements of +7.4 APbb / +5.5 APmk and +6.4 APbb / +4.7 APmk over the supervised pretraining baseline.
Pretraining on Non-object-centric Dataset. We use COCO training set and unlabeled set as pretraining data. Since ImageNet is ∼5.3 times larger than COCO, we pretrain our method on COCO for 100 epochs and prolonged 530 epochs respectively. Furthermore, we also generate a dataset named ImageNet-Subset which contains the same number of images of COCO to verify the impact of different pretraining datasets. Table 9 shows the results. Compared with the ImageNet pretrained model, the COCO pretrained model under 530 epochs is lower by 1.7 AP, possibly because the scale of COCO is smaller than ImageNet. Compared with the ImageNet-Subset pretrained model, the COCO pretrained model under 100 epochs is +0.4 AP higher, which demonstrates the importance of domain alignment between the pretraining dataset and detection dataset.
Longer Finetuning. We transfer SoCo* to Mask R-CNN with R50-FPN under the COCO 4× schedule. Table 10 shows the results. Our model continues to improve the performance with the 4× finetuning schedule, surpassing the supervised baseline by +2.6 APbb/ +1.9 APmk.

heading: 5 Conclusion

text: In this paper, we propose a novel object-level self-supervised pretraining method named Selective Object COntrastive learning (SoCo), which aims to align pretraining to object detection. Different from prior image-level contrastive learning methods which treat the whole image as an instance, SoCo treats each object proposal generated by the selective search algorithm as an independent instance, enabling SoCo to learn object-level visual representations. Further alignment is obtained in two ways. One is through network alignment between pretraining and downstream object detection, such that all layers of the detectors can be well-initialized. The other is by accounting for important properties of object detection such as object-level translation invariance and scale invariance. SoCo achieves state-of-the-art transfer performance on COCO detection using a Mask R-CNN detector. Experiments on two-stage and single-stage detectors demonstrate the generality and extensibility of SoCo.

title: Aligning Pretraining for Detection via Object-Level Contrastive Learning


summaries: The paper introduces a local search technique for vehicle routing problems (VRP) that decomposes the general problem and delegates smaller subproblems to a subsolver, e.g. an exact VRP solver. How to decompose the problem is learned from a generated training set using a transformer model and is the main contribution of the paper. Experiments results with a comparison to recent works in the area show the effectiveness of the proposed method.

summaries: This paper proposes an iterative framework to solve large-scale Vehicle Routing Problems. At each iteration, given the current feasible solution, a learned component selects subroutes that form a VRP subproblem. Then the subproblem is solved using a standard VRP solver (LKH-3) and the subsolution is used to update the current solution. The subproblem selector uses a Transformer encoder and predicts the subsolution cost; it is trained in a supervised way. Experimental results show that the method is able to reach the performance of the VRP solver LKH with significantly shorter computation times.

summaries: The paper proposes new ways to learn good decomposition steps in a heuristic search algorithm for the capacitated vehicle routing problem. The learning algorithm can select good seed points for the decomposition, often permitting significant speed-ups (1.5x) over other baseline decomposition algorithms (random and other simple variations). Additional experiments are conducted to evaluate the impact of the client distribution on the performance of the proposed approach.

summaries: The paper proposes a decomposition method for large-scale vehicle routing problems (VRPs) that leverage supervised learning. Specifically, the proposed methodology uses regression to identify a smaller, more tractable subproblem from a given initial solution, which is then addressed by another solver and incorporated into a full solution. Numerical results compare different state-of-the-art heuristics (e.g., LKH-3) and exact approaches (e.g., OR Tool) on different variations of the VRP with up to 3,000 nodes.

abstractText: Vehicle routing problems (VRPs) form a class of combinatorial problems with wide practical applications. While previous heuristic or learning-based works achieve decent solutions on small problem instances, their performance deteriorates in large problems. This article presents a novel learning-augmented local search framework to solve large-scale VRP. The method iteratively improves the solution by identifying appropriate subproblems and delegating their improvement to a black box subsolver. At each step, we leverage spatial locality to consider only a linear number of subproblems, rather than exponential. We frame subproblem selection as regression and train a Transformer on a generated training set of problem instances. Our method accelerates state-of-the-art VRP solvers by 10x to 100x while achieving competitive solution qualities for VRPs with sizes ranging from 500 to 3000. Learned subproblem selection offers a 1.5x to 2x speedup over heuristic or random selection. Our results generalize to a variety of VRP distributions, variants, and solvers.

authors:
E. Aarts
E.H. Aarts
J.K. Lenstra

title: Local search in combinatorial optimization

authors:
S. Ahn
Y. Seo
J. Shin

title: Learning what to defer for maximum independent sets

authors:
A.C. Alvim
E.D. Taillard

title: Popmusic for the world location-routing problem

venue: EURO Journal on Transportation and Logistics,

authors:
F. Arnold
M. Gendreau
K. Sörensen

title: Efficiently solving very large-scale routing problems

venue: Computers & Operations Research,

authors:
J. Błażewicz
W. Domschke
E. Pesch

title: The job shop scheduling problem: Conventional and new solution techniques

venue: European journal of operational research,

authors:
P.A. Bosman
H. La Poutré

title: Computationally intelligent online dynamic vehicle routing by explicit load prediction in an evolutionary algorithm

venue: In Parallel Problem Solving from Nature-PPSN IX,

authors:
X. Chen
Y. Tian

title: Learning to perform local rewriting for combinatorial optimization

venue: Advances in Neural Information Processing Systems,

title: A method for solving traveling-salesman problems

venue: Operations research,

authors:
H. Gehring
J. Homberger

title: A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows

venue: In Proceedings of EUROGEN99,

title: An extension of the lin-kernighan-helsgaun tsp solver for constrained traveling salesman and vehicle routing problems. http://akira.ruc.dk/~keld/research/ LKH-3

title: Using popmusic for candidate set generation in the lin-kernighan-helsgaun tsp solver

venue: Roskilde Universitet,

authors:
A. Hottung
K. Tierney

title: Neural large neighborhood search for the capacitated vehicle routing problem

venue: In 24th European Conference on Artificial Intelligence

title: Robust estimation of a location parameter

venue: In Breakthroughs in statistics,

authors:
B. Kallehauge
J. Larsen
O.B. Madsen
M.M. Solomon

title: Vehicle routing problem with time windows

venue: In Column generation,

authors:
E.B. Khalil
H. Dai
Y. Zhang
B. Dilkina
L. Song

title: Learning combinatorial optimization algorithms over graphs

venue: In Advances in Neural Information Processing Systems

authors:
N. Kohl
J. Desrosiers
O.B. Madsen
M.M. Solomon
F. Soumis

title: 2-path cuts for the vehicle routing problem with time windows

venue: Transportation Science,

authors:
W. Kool
H. van Hoof
M. Welling

title: Attention, learn to solve routing problems

venue: In International Conference on Learning Representations

authors:
Kwon
Y.-D
J. Choo
B. Kim
I. Yoon
Y. Gwon
S. Min

title: Pomo: Policy optimization with multiple optima for reinforcement learning

authors:
E. Lalla-Ruiz
S. Voss

title: Popmusic as a matheuristic for the berth allocation problem

venue: Annals of Mathematics and Artificial Intelligence,

title: Fifty years of vehicle routing

venue: Transportation science,

authors:
M. Laurent
É.D. Taillard
O. Ertz
F. Grin
D. Rappo
S. Roh

title: From point feature label placement to map labelling

venue: In Proceedings, metaheuristic international conference (MIC’09), Hamburg. Citeseer

authors:
J.K. Lenstra
A.R. Kan

title: Complexity of vehicle routing and scheduling problems

authors:
S. Lin
B.W. Kernighan

title: An effective heuristic algorithm for the traveling-salesman problem

authors:
H. Lu
X. Zhang
S. Yang

title: A learning-based iterative method for solving vehicle routing problems

authors:
J. Lysgaard
A.N. Letchford
R.W. Eglese

title: A new branch-and-cut algorithm for the capacitated vehicle routing problem

venue: Mathematical Programming,

authors:
M. Nazari
A. Oroojlooy
L. Snyder
M. Takac

title: Reinforcement learning for solving the vehicle routing problem

title: Leveraging machine learning to solve The vehicle Routing Problem with Time Windows

venue: PhD thesis,

authors:
J. Renaud
F.F. Boctor

title: A sweep-based algorithm for the fleet size and mix vehicle routing problem

venue: European Journal of Operational Research,

authors:
S. Salhi
G. Nagy

title: A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling

venue: Journal of the operational Research Society,

authors:
A. Santini
M. Schneider
T. Vidal
D. Vigo

title: Decomposition strategies for vehicle routing heuristics

title: Using constraint programming and local search methods to solve vehicle routing problems

venue: In International conference on principles and practice of constraint programming,

authors:
S. Sivanandam
S. Deepa

title: Genetic algorithms. In Introduction to genetic algorithms, pages

title: Algorithms for the vehicle routing and scheduling problems with time window constraints

authors:
J. Song
R. Lanka
Y. Yue
B. Dilkina

title: A general large neighborhood search framework for solving integer linear programs

title: Heuristic methods for large centroid clustering problems

venue: Journal of heuristics,

authors:
É.D. Taillard
L.M. Gambardella
M. Gendreau
Potvin
J.-Y

title: Adaptive memory programming: A unified view of metaheuristics

authors:
É.D. Taillard
K. Helsgaun

title: Popmusic for the travelling salesman problem

authors:
É.D. Taillard
S. Voss

title: Popmusic—partial optimization metaheuristic under special intensification conditions

venue: In Essays and surveys in metaheuristics,

authors:
É.D. Taillard
S. Voß

title: POPMUSIC, pages 687–701

authors:
E. Uchoa
D. Pecin
A. Pessoa
M. Poggi
T. Vidal
A. Subramanian

title: New benchmark instances for the capacitated vehicle routing problem

authors:
A. Vaswani
N. Shazeer
N. Parmar
J. Uszkoreit
L. Jones
A.N. Gomez
L. Kaiser

title: u., and Polosukhin, I

authors:
M. Ventresca
B. Ombuki-Berman
A. Runka

title: Predicting genetic algorithm performance on the vehicle routing problem using information theoretic landscape measures

venue: In European Conference on Evolutionary Computation in Combinatorial Optimization,

title: Hybrid genetic search for the cvrp: Open-source implementation and swap* neighborhood. arXiv preprint arXiv:2012.10384

authors:
T. Vidal
T.G. Crainic
M. Gendreau
N. Lahrichi
W. Rei

title: A hybrid genetic algorithm for multidepot and periodic vehicle routing problems

venue: Operations Research,

authors:
C. Voudouris
E.P. Tsang

title: Guided local search

venue: In Handbook of metaheuristics,

authors:
C. Wu
K. Shankari
E. Kamar
R. Katz
D. Culler
C. Papadimitriou
E. Horvitz
A. Bayen

title: Optimizing the diamond lane: A more tractable carpool problem and algorithms

venue: IEEE 19th International Conference on Intelligent Transportation Systems (ITSC),

heading: 1 Introduction

text:
Vehicle routing problems (VRPs) have enjoyed ample applications in logistics and ride-hailing services [23] around the world for decades. While determining the optimal solution to a VRP is NP-hard [25], there have been numerous attempts to solve VRPs both exactly and approximately: provable algorithms have been designed for specific problem instances up to size 130 [28], and powerful heuristic solvers such as LKH-3 [13] and HGS [49, 48] find good solutions in practice for problems of size more than 1000. However, heuristics methods often suffer from inflexibility due to extensive hand-crafting and the heavy computational burden from lengthy iterative procedures, as in the case of LKH-3. For example, LKH-3 takes more than an hour to solve a size 2000 CVRP instance (Table 1), which is impractical for applications such as large-scale courier or municipal services.
More recently, machine learning methods inspired by the Pointer Network [50] provide alternatives to traditional solvers: the learning-based methods greatly reduce computation time while maintaining decent solution quality on small problem instances (less than 100 cities), by training on diverse sets of problem distributions either via supervised [50] or reinforcement learning [29, 20]. However, these methods remain difficult to scale, and few report results on problems of size more than 200.
Our work aims to address scalability by learning to identify smaller subproblems which can be readily solved by existing methods. Our learned subproblem selector guides the problem-solving process to focus local improvement on promising subregions. While there exists a combinatorial number
⇤Equal Contribution
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
of subproblems that can be selected at each step, we leverage spatial locality commonly found in combinatorial optimization problems to restrict the selection space size to be linear in the problem size. Intuitively, objects far away from each other generally have very small influence on each other’s solution and are likely to be in different routes, so they should not be part of the same subproblem. The greatly reduced search space enables us to feasibly train an attention-based subproblem selector.
Our framework combines the advantages of learning and heuristics: our network identifies promising subproblems to improve upon, dramatically speeding up solution times. Using a competitive subsolver on subproblems, we achieve good solution quality without the high computational costs of running the subsolver on large problem instances. In summary, our contributions are:
• We propose learning-to-delegate, a learning-based framework for solving large-scale VRPs by iteratively identifying and solving smaller subproblems.
• Despite the high dimensionality and NP-hardness of subproblems, we design a Transformer architecture that effectively predicts the subsolver’s solution quality for a subproblem.
• With extensive validation, we show that learning-to-delegate offers significant speedups and/or objective improvements over both its base subsolver and random (or heuristic) subproblem selection, for a variety of VRP variants, distributions, and solvers.

heading: 2 Preliminary: Capacitated Vehicle Routing Problems (CVRP)

text:
In CVRP, there is a depot node 0 and city nodes {1, ..., N}. Each city node i has demand di to fulfill. A vehicle with capacity C starts and ends at the depot and visits a route of city nodes such that the sum of city demands along the route does not exceed C, after which the vehicle starts a new route again. The objective is to find a valid solution minimizing the solution cost. We define the following:
• Route: a sequence of nodes, where the first and last node are the depot 0, and the rest are city nodes. In a valid route, the sum of demands of the city nodes does not exceed C.
• Route cost: the sum of edge costs for the sequence of nodes. For an edge from node i to node j, the edge cost is the Euclidean distance between node i and j.
• Solution: a feasible solution consists of a set of valid routes visiting each city exactly once. • Solution cost: the sum of route costs for all routes in the solution. An optimal solution is a
feasible solution with the minimum solution cost. • Subproblem: a CVRP consisting of the depot, a subset of cities, and corresponding demands.

heading: 3 Related Work

text:
Classical methods. Heuristics for solving combinatorial optimization problems have been studied for decades. The most powerful methods, such as local search [1], genetic algorithms [36], and ant colony methods [10], involve iteratively improving the solution in a hand-designed neighborhood. For example, move, swap [52], and 2-opt [9] are well-known heuristics for the traveling salesman and vehicle routing problems. The competitive VRP solver LKH-3 [13] uses the Lin–Kernighan heuristic [26] as a backbone, which involves swapping pairs of sub-routes to create new routes, whereas the CVRP solver HGS [49, 48] uses a hybrid genetic and local search procedure to achieve state-of-the-art solution qualities on problems up to size 1000. While LKH-32 tackles a variety of VRP variants, the publicly available implementation of HGS 3 only solves CVRP.
For large problems, low-level heuristics are combined with meta-heuristics, including Tabu Search with Adaptive Memory [40], guided local search [51], and Large Neighborhood Search [35]. The inspiration for our work derives from Partial OPtimization Metaheuristic Under Special Intensification Conditions (POPMUSIC), which iteratively optimizes problem subparts and has been used to solve problems as diverse as map labeling [24], berth allocation [22], and p-median clustering [39].
Despite the promise of the POPMUSIC framework for large-scale combinatorial optimization, the impact of certain design choices is not well understood, such as the subproblem selection ordering
2We refer to the LKH-3 code at http://webhotel4.ruc.dk/~keld/research/LKH-3/. 3We refer to the HGS code at https://github.com/vidalt/HGS-CVRP.
and size [43]. For example, it is not clear how to meaningfully order the subproblems. One early work in this direction demonstrated that a last-in-first-out stack order performs better than random [3]. Our work provides a natural approach to order the subproblems based on predicted improvement.
Deep learning methods. Recently, there has been a surge of interest in training deep neural networks (DNN) to solve combinatorial problems. As observed by Kwon et al. [21], most methods fall into one of the following two categories: 1) construction methods [29, 20], where an autoregressive model such as the Pointer Network [50] directly outputs a solution, and 2) improvement methods [7, 15], where the DNN iteratively performs local updates to the solution, resembling local search.
These methods are approaching the solution quality of LKH-3 [13] on small problem instances. For example, Kwon et al. [21] extends a construction approach [20] to encourage more diverse output samples on N  100 VRPs. Among improvement methods, Lu et al. [27] learn a meta-controller to select among a set of local search heuristics, marking the first learning-based approach to outperform LKH-3 on N  100 VRPs. Despite these successes, learning-based approaches for large-scale VRPs are poorly understood. In addition, all of the aforementioned methods are trained using deep reinforcement learning; for large problems, trajectory collection becomes prohibitively expensive.
Scaling up learning methods. A few recent works have begun to investigate scaling of learned networks for NP-hard graph problems. For example, Ahn et al. [2] propose an iterative scheme called learning-what-to-defer for maximum independent set. At each stage, for each node in the graph, the network either outputs the solution for the node or defers the determination to later stages. Song et al. [38] proposes an imitation-learning-based pipeline for Integer Linear Programs (ILP), where at each stage they partition all variables into disjoint subsets, and use the Gurobi [12] ILP solver to solve the partitions. Due to differences in graph structure, our work presents a more natural scheme to handle VRP constraints and structures. A few works attempt to incorporate learning to decompose large-scale VRPs [6, 47, 31]. However, the decomposition approaches proposed appear to be experimentally less effective than ours.

heading: 4 An Iterative Framework for VRPs

text:
While CVRPs are NP-hard and thus require worst-case exponential time in the problem size to solve optimally, typical CVRPs exhibit structure that practical solvers may exploit. We hypothesize that in
such situations, the larger problem can be efficiently approximately solved as a sequence of smaller subproblems, which can be delegated to efficient subsolvers. To test this hypothesis, we propose a learning-based, iterative framework with two components: 1) a subsolver capable of solving a small problem instance (exactly or approximately), and 2) a learned model for identifying suitable subproblems within a larger problem to delegate to the subsolver.
Algorithm 1: Learning to Delegate Input: Problem instance P , initialized solution X , subproblem selector f✓, subsolver
Subsolver, number of steps T , parameter k denoting the size of subproblems 1 for Step t = 1: T do 2 Sk,local ConstructSubproblems(P,X, k) 3 S f✓(Sk,local) 4 X 0S Subsolver(S) 5 X X 0S [XP\S 6 end for
We illustrate our iterative framework in Figure 1, which takes in a problem instance P with a feasible initial solution X0. At each step, given the current solution X , we select a smaller subproblem S ⇢ P with our learned model f✓ then apply the subsolver to solve S; we then update X with the new solution for S. To maintain feasibility after an update, we restrict S to be the set S of visited cities of a subset of routes from X . Since routes with cities in P \ S remain valid routes, we obtain a new feasible solution X 0 = X 0S [XP\S , where X 0S is the subsolution for S and XP\S consists of unselected routes from X . Intuitively, a strong f✓ should identify a subproblem S such that the subsolver solution X 0S results in a large improvement in objective from X to X 0.

heading: 4.1 The Restricted Subproblem Selection Space

text:
As the number of routes in P is R = O(N), the cardinality of the selection space S is O(2R), which is exponential in the problem size N and difficult for learned models to consider. If we restrict each subproblem to cities from exactly k routes, there are still
R k = O(Rk) subproblems to consider.
Therefore we further restrict selection to subproblems with spatial locality. As shown in Figure 1(d), we only consider subproblems from Sk,local, where each subproblem is centered around a particular route r and contains the k routes whose centroids have the smallest Euclidean distance to the centroid of r. In this way, we reduce the selection space to |Sk,local| = R = O(N) from |S| = O(2N ). In Algorithm 1, we refer to this restriction as ConstructSubproblems. Our restriction to a local selection space is motivated by the fact that many combinatorial optimizations problems have inherent spatial locality, i.e. problem entities are more strongly affected by nearby entities than faraway entities. Earlier heuristical methods such as POPMUSIC [42] leverage similar spatial locality.

heading: 5 Learning to Delegate

text:
In this section, we discuss criteria for selecting subproblems, and how to train the subproblem selector.
Improvement as the criteria for subproblem selection. Given a selected subproblem S with a current solution XS on the subproblem, we obtain from LKH-3 a new solution X 0S on the same subproblem (step (d) to (e) in Figure 1). We then define the immediate improvement
(S) = c(XS) c(X 0S) (1) where c(XS) is the total cost of subsolution XS and (S) is the improvement in the solution cost. In this way, the sum of improvements along T steps is the total improvement in solution quality. As we empirically find that providing the previous subsolution XS to the subsolver may trap the subsolver in a local optimum, we withhold XS from the solver and thus may see non-positive improvement (S)  0, especially after many steps of subproblem selection. At test time, to avoid worsening the objective, we adopt a hill-climbing procedure such that when (S)  0, we keep XS instead of X 0S (Figure 1, step (e)). With proper masking, we avoid selecting the same non-improving subproblem S again. The hill-climbing and masking procedures are applied to both our subproblem-selection network f✓ and the three heuristic selection rules, described in 6.1, to maintain fair comparisons.
Subproblem selection. The goal of our subproblem selector is to select the subproblem leading to the best immediate improvement. While our subproblem selection does not directly optimize for the total improvement, we observe that (1) our subsolver may perform many low-level operations internally, so high-level problem selection may still benefit greatly from maximizing the immediate improvement, and (2) numerous reinforcement learning approaches to VRP [53, 18] choose a small discount factor such as = 0.25 when optimizing a multi-step objective TP
t=1 t t, as doing
so encourage faster convergence. Moreover, our subproblem selector may instead be trained on multi-step search data to select subproblems offering the best multi-step improvement.
Ground-truth labels. Our restricted selection space allows us to enumerate all possible subproblems at each step. In a typical large scale CVRP instance with N = 2000 cities, a solution consists of roughly R = 200 routes, so the size of the selection space is 200. We obtain the immediate improvement (S) by running the subsolver on each subproblem S 2 Sk,local. Although our enumeration strategy is feasible for generating training data, it is much too slow to execute on a test CVRP instance. However, if our subproblem selector can predict the best immediate improvement at test time (that is, without running the subsolver on multiple subproblems), then we can combine the best of both worlds to obtain a fast and accurate selection strategy.
Selection strategies: regression vs classification. Given a labeled dataset, we may treat the task of identifying the best subproblem as either regression or classification. In the context of imitation learning with a greedy expert, the former learns a value function while the latter learns a policy. Due to space limitation, we focus discussion on regression and reserve comparison with classification for Appendix A.5.1. The regression-based subproblem selector uses a trained f✓ to predict the subsolution cost c(X 0S); we then simply compute argmaxS c(XS) f✓(S) to select the best subproblem.
Network architecture. We define f✓ with a Transformer encoder architecture [45]. The input representing each subproblem S is the unordered set of featurized cities in S. The features for each city consist of the demand d and the location of the city (x, y) relative to the depot. As we do not feed the existing subsolution XS to the subsolver, the dense multi-head attention mechanism does not need to be modified to take the routes in XS into account. The output of the Transformer encoder is fed into a linear layer then mean-pooled to obtain the scalar prediction f✓(S). In Appendix A.5.5, we perform an ablation study with simpler architectures.
Loss function. We empirically find mean squared error to be less stable than Huber loss [16], which we set as our loss function
L(✓;S) =
⇢ 1 2 (f✓(S) c(X 0 S)) 2 , if |f✓(S) c(X 0S)|  1
|f✓(S) c(X 0S)| 12 , otherwise (2)

heading: 6 Experiments and Analysis

text:
We illustrate the CVRP distributions considered in our work in Figure 3. We perform extensive experiments to evaluate our learning framework, aiming to answer the following questions:
1. Uniform distribution. How does our method compare with baselines, in terms of solution time and quality, on problems with uniformly distributed cities?
2. Clustered distributions. How does our method perform on problems with clustered cities? 3. Out-of-distribution. Can our model generalize, such as to larger or real-world instances? 4. VRP variants. Can our method address more sophisticated VRPs? E.g., CVRP with Time
Windows (CVRPTW) [37] or VRP with Mixed Pickup and Delivery (VRPMPD) [33]. 5. VRP solvers. Can our method be adapted to leverage other VRP subsolvers?
We reserve additional ablations on subproblem selection as classification, effect of subproblem size k and discussion of asymptotic behavior, subproblem selection with the HGS subsolver, effect of weaker initialization methods, and comparison with simpler architectures for Appendix A.5.

heading: 6.1 Setup

text:
We briefly describe experimental setup in the main text and defer full details to Appendix A.1. Given a particular distribution of VRP, we generate separate sets of training, validation, and test problem instances. Unless otherwise stated, our validation and test sets contain 40 instances each. For each problem instance, we generate a rough initial solution by partitioning it into disjoint subsets of cities and briefly running the subsolver on each subset. Due to its compatibility with many VRP variants, we use LKH-3 [13] as the subsolver for all VRP distributions unless otherwise stated.
We generate the training set by running our iterative framework and selecting subproblems by enumerating the subsolver on all S 2 Sk,local. As many subproblems remain unchanged from X to X
0, we use previously cached subsolutions when possible instead of re-running the subsolver. While generation times differ depending on several factors, typically it takes less than 10 hours with 200 Intel Xeon Platinum 8260 CPUs to generate a training set of 2000 instances.
To avoid training multiple models for different problem sizes N , we train a single model for each VRP distribution with combined data from multiple N 2 {500, 1000, 2000}. Training takes at most 8 hours on a single NVIDIA V100 GPU. To exploit symmetry in problem instances, we apply rotation and flip augmentation at training time. To evaluate trained selectors on a problem instance, we run the iterative selection framework on a single CPU, with disabled multithreading and no GPU.
We select the best hyperparameters via manual search based on validation set performance. We record final results on the test set as the mean and standard error over 5 runs with different random seeds.
Baselines. By default, as we use LKH-3 as the subsolver, we run LKH-3 on the full problem instances with our initialization for 30000 local update steps, which takes 2-3 hours on average for N = 2000. If using HGS as the subsolver, we also run HGS on the full problem instances for the same amount of time as our LKH-3 baseline. These baselines allow us to compute the speedup of our framework over the subsolver alone. We also compare against OR Tools [30], another open source
heuristic VRP solver employing iterative search, terminating runs at 15 minutes, as OR Tools stops improving the solution within this time for all instances.
We include results for previous learning methods AM [20] and NeuRewriter [7]. These do not outperform LKH-3 even on small problem sizes, and learning methods have had more difficulty generalizing to larger instances. In fact, these methods are trained on problems of size N  100, and we find that they yield poor solutions on N 500 without architecture modifications and extensive re-training. The AM and NeuRewriter results demonstrate the difficulty of scaling up previous learning methods. We do not initialize OR-Tools, AM, and NeuRewriter because we empirically find that these methods have limited solution capability and do not improve our decent initialization.
To validate our subproblem selector’s ability to identify promising subproblems, we design three additional baselines that employ our iterative framework using hand-crafted heuristics to select subproblems. The three heuristics that we use are: (1) Random, selecting subproblem S from Sk,local uniformly; (2) Count-based, which avoids repetitive selections by selecting the subproblem centered at the route whose city nodes have been selected cumulatively the least often in previous steps; and (3) Max Min Distance, which encourages coverage of the entire problem instance by selecting subproblems with the maximum distance from the nearest centroid of previously selected subproblems. We run the heuristic baselines with the same setup as our learned subproblem selector.
Metrics. We refer to two metrics to compare our method against baseline methods.
1. Improvement over method X: at a specified computation time, the improvement of method Y over method X is the total improvement of method Y minus that of method X.
2. Speedup over method X: at a specified solution quality that method X attains, the speedup of method Y over method X is the computation time required for method X to attain the solution quality divided by the time for method Y to attain the solution quality.
We define 95% solution quality of running a method X over a computation time as the solution quality with 95% of the total improvement. We report speedup at 95% solution quality of a method X because X may take a disproportionate amount of time on the last 5% of improvement; reporting speedup at 100% solution quality inflates the speedup.

heading: 6.2 Uniform CVRP Distribution

text:
As seen in Table 1, our method achieves the best performance for all problem sizes, matching LKH-3’s solution quality with more than 7x to 15x less computation time and offering even more improvements with longer computation time. Although we need to evaluate all R = O(N) subproblems of the initial solution with our subproblem selector, subsequent per-step computation time of our method is mostly independent of the problem size N since we only evaluate changed subproblems.
Running LKH-3 for 30k local update steps achieves superior performance to all previous other heuristic and learning-based baselines. Its solution quality scales well to large problem sizes, yet the solution time is significantly longer. Previous learning-based methods, though fast, result in much worse solution qualities. Our heuristic baselines Random, Count-based, and Max Min Distance demonstrate that our iterative framework, even without the learned subproblem selector, may achieve over 5x to 10x speedup over LKH-3. Nevertheless, our results demonstrate that learning the subproblem selector may offer an additional 1.5x speedup over non-learning heuristics.
In Figure 4, we demonstrate the solution quality of our method and baselines compared to LKH-3. We see that, compared to baseline methods, the learned subproblem selector obtains the best solution quality when run for a reasonable amount of time. The improvement of most methods based on our iterative framework converge when run for an excessive amount of time; this is unsurprising, as Random and other baselines are eventually able to select all subproblems offering improvements.
In Figure 5, we demonstrate the speedup of our method over LKH-3, comparing to baseline methods. The speedup is often significant even at low levels of solution quality, and improves with higher solution quality. The speedup is not as meaningful beyond 95% LKH-3 solution quality, as LKH-3 takes a disproportionate amount of time to attain the last 5% of improvement.

heading: 6.3 Clustered and Mixed CVRP Distributions

text:
We further examine the framework’s performance on CVRP distributions with clusters of cities, such as studied in [8, 44]. We generate a clustered instance by first sampling (x, y) locations of nc cluster centroids then sampling the cities around the centroids. The mixed distribution samples 50% of the cities from a uniform distribution and the rest from around cluster centers. We generate a dataset
of instances for every (N,nc,m) 2 {500, 1000, 2000}⇥ {3, 5, 7}⇥ {Clustered,Mixed} and train a single model on the entire dataset. We evaluate the model on validation and test sets of 10 instances per (N,nc,m) combination (i.e. 60 instances per N ). Due to space limitation, we provide more details about the data distribution and full results in Appendix A.2.
Table 2 reports speedups of our method and the Random baseline over LKH-3. Our method sees at least 2x speedup over Random in all settings. We see larger speedups for clustered distributions than for mixed or uniform distributions (Table 1).

heading: 6.4 Out-of-distribution Generalization

text:
We study how our subproblem selector generalize to a uniform CVRP distribution with larger problem size N = 3000 and to a realworld CVRP distributions, both unseen at training time. The real-world CVRP distribution derives from a CVRP dataset [4] consisting of 10 very-large-scale instances on 5 Belgium regions with N ranging from 3000 to 30000 and randomly generated demand distribution. To generate an instance, we subsample the cities in a region without replacement to N = 2000, while regenerating the demands to match our training distribution. For each original instance, we generate 5 subsampled instances to form the test set of 50 total instances. We visualize the original and subsampled datasets in Appendix A.3.
We apply subproblem selectors trained on uniform and clustered data without finetuning on the new data distributions and report the speedup comparison with the Random baseline in Figure 6. We see that when transferring to N = 3000, subproblem selectors trained on uniform and clustered data offer similar performance. However, the model trained on the clustered distribution generalizes well to the real-world distribution while the model trained on the uniform distribution fails to generalize, with worse speedup than the Random baseline. These results suggest that the domain variability of the clustered distribution strongly improves generalization performance.

heading: 6.5 Other VRP Variants

text:
While our previous experiments vary the distribution of city locations in CVRP, here we consider two VRP variants with uniform city distribution but with additional constraints: CVRPTW [37] and VRPMPD [33]. The former specifies a hard time window constraint for visiting each city, while the latter specifies pick up and delivery constraints in addition to capacity constraint. A detailed description of the variants can be found in Appendix A.4.
Similar to CVRP, we observe significant speedup with our iterative framework alone, while learning offers additional speedup. For CVRPTW, our method offers a 8.2x speedup while our Random baseline offers a 5.9x speedup; for VRPMPD, our method offers a 31x speedup while our Random baseline offers a 20x speedup. We suspect that the time window constraint in CVRPTW imposes strict orderings on the order of city visitations, increasing the difficulty for the subproblem selector.

heading: 6.6 A State-of-the-Art CVRP Subsolver: HGS

text:
While we focus our analysis on LKH-3 due to its applicability to many variants of VRPs, HGS [49, 48] is a state-of-the-art solver focused on CVRP. Thus, we apply our method to train subproblem selectors for the HGS subsolver. We discuss the full experimental setup and results in Appendix A.5.3.
With HGS as the subsolver, we observe a 103x speedup for our method on N = 2000, compared with a 77x speedup for the Random baseline. Similarly, we observe a 198x speedup for our method on N = 3000, compared with a 152x speedup for our Random baseline. The large speedup may be due to the fact that HGS is designed and calibrated for medium-scale problems of 500 to 1000 cities, allowing it to function better as a subsolver for large-scale VRPs.

heading: 7 Conclusion

text:
This paper presents a learning-based framework which learns which subproblems to delegate to a subsolver when solving large VRPs. Spatial locality allows us to learn the subproblem selector over a reduced selection space. The proposed method accelerates competitive VRP solvers on problems of sizes up to 3000, requiring an order of magnitude less computation time. We identify a 1.5x to 2x speedup over non-learning selection strategies. Our results generalize to a variety of VRP distributions, variants, and solvers.
While most previous learning-based combinatorial optimization methods [20, 21, 2] rely on reinforcement learning due to the unavailability of optimal solutions as high-quality labels, our work highlights the counterintuitive effectiveness of supervised learning with only moderate-quality labels to achieve high-quality solutions with iterative subproblem selection. An interesting line of future work may explore other ways to effectively leverage moderate-quality labels for combinatorial optimization tasks. In particular, we discuss in Appendix A.6 the applicability of our method to other combinatorial optimization problems with spatial locality. We believe that our learning framework can serve as a powerful technique for both the learning and operations research communities to scale up combinatorial optimization solvers.
Our code is publicly available at https://github.com/mit-wu-lab/learning-to-delegate.
Negative Social Impact. Enabling more efficient solutions of large-scale VRPs may exhibit negative externalities such as inducing additional traffic from delivery vehicles and centralizing services that pose a stronger competition to brick-and-mortar retail.

heading: 8 Acknowledgements

text: This research was supported by MIT Indonesia Seed Fund, US DOT DDETFP, and the MIT-IBM Watson AI Lab. The authors are grateful to the anonymous reviewers for detailed comments that substantially improved the article. The authors acknowledge the MIT SuperCloud and Lincoln Laboratory Supercomputing Center for providing (HPC, database, consultation) resources that have contributed to the research results reported within this paper. We also thank Zongyi Li for helpful discussions and technical advice throughout the project.

title: Learning to Delegate for Large-scale Vehicle Routing