Timezone: »
Combinatorial Optimization (CO) has been a long-standing challenging research topic featured by its NP-hard nature. Traditionally such problems are approximately solved with heuristic algorithms which are usually fast but may sacrifice the solution quality. Currently, machine learning for combinatorial optimization (MLCO) has become a trending research topic, but most existing MLCO methods treat CO as a single-level optimization by directly learning the end-to-end solutions, which are hard to scale up and mostly limited by the capacity of ML models given the high complexity of CO. In this paper, we propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph (e.g. add, delete or modify edges in a graph), fused with a lower-level heuristic algorithm solving on the optimized graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity. The experiments and results on several popular CO problems like Directed Acyclic Graph scheduling, Graph Edit Distance and Hamiltonian Cycle Problem show its effectiveness over manually designed heuristics and single-level learning methods.
Author Information
Runzhong Wang (Shanghai Jiao Tong University)
Zhigang Hua (Ant Group)
Gan Liu (Ant Group)
Jiayi Zhang (Shanghai Jiao Tong University)
Junchi Yan (Shanghai Jiao Tong University)
Feng Qi (Meta)
Shuang Yang (Facebook)
Jun Zhou (Ant Financial)
Xiaokang Yang (Shanghai Jiao Tong University)
More from the Same Authors
-
2022 Poster: Iso-Dream: Isolating and Leveraging Noncontrollable Visual Dynamics in World Models »
Minting Pan · Xiangming Zhu · Yunbo Wang · Xiaokang Yang -
2022 Poster: Perceptual Attacks of No-Reference Image Quality Models with Human-in-the-Loop »
Weixia Zhang · Dingquan Li · Xiongkuo Min · Guangtao Zhai · Guodong Guo · Xiaokang Yang · Kede Ma -
2022 Poster: ZARTS: On Zero-order Optimization for Neural Architecture Search »
Xiaoxing Wang · Wenxuan Guo · Jianlin Su · Xiaokang Yang · Junchi Yan -
2023 Poster: FAST: a Fused and Accurate Shrinkage Tree for Heterogeneous Treatment Effects Estimation »
Jia Gu · Caizhi Tang · Han Yan · Qing Cui · Longfei Li · Jun Zhou -
2023 Poster: Unleashing the Power of Graph Data Augmentation on Covariate Shift »
Yongduo Sui · Qitian Wu · Jiancan Wu · Qing Cui · Longfei Li · Jun Zhou · Xiang Wang · Xiangnan He -
2023 Poster: Language Models Can Improve Event Prediction by Few-Shot Abductive Reasoning »
Xiaoming Shi · Siqiao Xue · Kangrui Wang · Fan Zhou · James Zhang · Jun Zhou · Chenhao Tan · Hongyuan Mei -
2023 Poster: Prompt-augmented Temporal Point Process for Streaming Event Sequence »
Siqiao Xue · Yan Wang · Zhixuan Chu · Xiaoming Shi · Caigao JIANG · Hongyan Hao · Gangwei Jiang · Xiaoyun Feng · James Zhang · Jun Zhou -
2023 Poster: NeRF-IBVS: Visual Servo Based on NeRF for Visual Localization and Navigation »
Yuanze Wang · Yichao Yan · Dianxi Shi · Wenhan Zhu · Jianqiang Xia · Tan Jeff · Songchang Jin · KE GAO · XIAOBO LI · Xiaokang Yang -
2022 Spotlight: Lightning Talks 5A-3 »
Minting Pan · Xiang Chen · Wenhan Huang · Can Chang · Zhecheng Yuan · Jianzhun Shao · Yushi Cao · Peihao Chen · Ke Xue · Zhengrong Xue · Zhiqiang Lou · Xiangming Zhu · Lei Li · Zhiming Li · Kai Li · Jiacheng Xu · Dongyu Ji · Ni Mu · Kun Shao · Tianpei Yang · Kunyang Lin · Ningyu Zhang · Yunbo Wang · Lei Yuan · Bo Yuan · Hongchang Zhang · Jiajun Wu · Tianze Zhou · Xueqian Wang · Ling Pan · Yuhang Jiang · Xiaokang Yang · Xiaozhuan Liang · Hao Zhang · Weiwen Hu · Miqing Li · YAN ZHENG · Matthew Taylor · Huazhe Xu · Shumin Deng · Chao Qian · YI WU · Shuncheng He · Wenbing Huang · Chuanqi Tan · Zongzhang Zhang · Yang Gao · Jun Luo · Yi Li · Xiangyang Ji · Thomas Li · Mingkui Tan · Fei Huang · Yang Yu · Huazhe Xu · Dongge Wang · Jianye Hao · Chuang Gan · Yang Liu · Luo Si · Hangyu Mao · Huajun Chen · Jianye Hao · Jun Wang · Xiaotie Deng -
2022 Spotlight: Iso-Dream: Isolating Noncontrollable Visual Dynamics in World Models »
Minting Pan · Xiangming Zhu · Yunbo Wang · Xiaokang Yang -
2022 Spotlight: Lightning Talks 4B-2 »
Artem Moskalev · Weixia Zhang · Vudtiwat Ngampruetikorn · Anna Sepliarskaia · Dingquan Li · David Schwab · Ivan Sosnovik · Xiongkuo Min · Arnold Smeulders · Guangtao Zhai · Guodong Guo · Xiaokang Yang · Kede Ma -
2022 Spotlight: Perceptual Attacks of No-Reference Image Quality Models with Human-in-the-Loop »
Weixia Zhang · Dingquan Li · Xiongkuo Min · Guangtao Zhai · Guodong Guo · Xiaokang Yang · Kede Ma -
2022 Spotlight: Debiased Causal Tree: Heterogeneous Treatment Effects Estimation with Unmeasured Confounding »
Caizhi Tang · Huiyuan Wang · Xinyu Li · Qing Cui · Ya-Lin Zhang · Feng Zhu · Longfei Li · Jun Zhou · Linbo Jiang -
2022 Poster: Adv-Attribute: Inconspicuous and Transferable Adversarial Attack on Face Recognition »
Shuai Jia · Bangjie Yin · Taiping Yao · Shouhong Ding · Chunhua Shen · Xiaokang Yang · Chao Ma -
2022 Poster: Debiased Causal Tree: Heterogeneous Treatment Effects Estimation with Unmeasured Confounding »
Caizhi Tang · Huiyuan Wang · Xinyu Li · Qing Cui · Ya-Lin Zhang · Feng Zhu · Longfei Li · Jun Zhou · Linbo Jiang -
2022 Poster: CageNeRF: Cage-based Neural Radiance Field for Generalized 3D Deformation and Animation »
Yicong Peng · Yichao Yan · Shengqi Liu · Yuhao Cheng · Shanyan Guan · Bowen Pan · Guangtao Zhai · Xiaokang Yang -
2021 Poster: GRIN: Generative Relation and Intention Network for Multi-agent Trajectory Prediction »
Longyuan Li · Jian Yao · Li Wenliang · Tong He · Tianjun Xiao · Junchi Yan · David Wipf · Zheng Zhang -
2021 Poster: From Canonical Correlation Analysis to Self-supervised Graph Neural Networks »
Hengrui Zhang · Qitian Wu · Junchi Yan · David Wipf · Philip S Yu -
2021 Poster: MixSeq: Connecting Macroscopic Time Series Forecasting with Microscopic Time Series Data »
Zhibo Zhu · Ziqi Liu · Ge Jin · Zhiqiang Zhang · Lei Chen · Jun Zhou · Jianyong Zhou -
2021 Poster: Towards Open-World Feature Extrapolation: An Inductive Graph Learning Approach »
Qitian Wu · Chenxiao Yang · Junchi Yan -
2021 Poster: Learning High-Precision Bounding Box for Rotated Object Detection via Kullback-Leibler Divergence »
Xue Yang · Xiaojiang Yang · Jirui Yang · Qi Ming · Wentao Wang · Qi Tian · Junchi Yan -
2021 Poster: On Joint Learning for Solving Placement and Routing in Chip Design »
Ruoyu Cheng · Junchi Yan -
2020 Poster: Graduated Assignment for Joint Multi-Graph Matching and Clustering with Application to Unsupervised Graph Matching Network Learning »
Runzhong Wang · Junchi Yan · Xiaokang Yang -
2020 Poster: Bandit Samplers for Training Graph Neural Networks »
Ziqi Liu · Zhengwei Wu · Zhiqiang Zhang · Jun Zhou · Shuang Yang · Le Song · Yuan Qi -
2019 Poster: Generalization in Generative Adversarial Networks: A Novel Perspective from Privacy Protection »
Bingzhe Wu · Shiwan Zhao · Chaochao Chen · Haoyang Xu · Li Wang · Xiaolu Zhang · Guangyu Sun · Jun Zhou -
2018 Poster: Video Prediction via Selective Sampling »
Jingwei Xu · Bingbing Ni · Xiaokang Yang -
2017 Poster: Wasserstein Learning of Deep Generative Point Process Models »
Shuai Xiao · Mehrdad Farajtabar · Xiaojing Ye · Junchi Yan · Xiaokang Yang · Le Song · Hongyuan Zha -
2009 Poster: Dirichlet-Bernoulli Alignment: A Generative Model for Multi-Class Multi-Label Multi-Instance Corpora »
Shuang Yang · Hongyuan Zha · Bao-Gang Hu