nach oben

Neural Processing Letters

Erschienen in:

15.06.2022

Heavy-Head Sampling for Fast Imitation Learning of Machine Learning Based Combinatorial Auction Solver

verfasst von: Chen Peng, Bolin Liao

Erschienen in: Neural Processing Letters | Ausgabe 1/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The winner determination problem of a combinatorial auction can be modeled as mixed-integer linear programming, and is a popular benchmark to evaluate modern solvers. Recent advancements in combinatorial optimization improve the branch-and-bound solving process by replacing the time-consuming heuristics with machine learning models. In this paper, by taking advantage of the heavy-head maximum depth distribution of the branch-and-bound solution trees, a heavy-head sampling strategy is proposed for the imitation learning on the combinatorial auction problems. Experimental results show that, under the small-dataset fast-training scheme and using the heavy-head sampling strategy, the final evaluation results of the trained policy on the combinatorial auction problems are improved significantly (in the sense of statistical testing), compared to using the uniform sampling strategy in previous studies.

Vorheriger Artikel ChaInNet: Deep Chain Instance Segmentation Network for Panoptic Segmentation

Nächster Artikel Stability Analysis of the Impulsive Projection Neural Network

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Newman AM, Weiss M (2013) A survey of linear and mixed-integer optimization tutorials. Inf Trans Educ 14(1):26–38CrossRef

Peter C, Yoav S, Richard S (2006) Combinatorial auctions. MIT Press, CambridgeMATH

Triki C, Piya S, Fu LL (2020) Integrating production scheduling and transportation procurement through combinatorial auctions. Networks 76(2):147–163MathSciNetCrossRef

Song W et al (2017) A multi-unit combinatorial auction based approach for decentralized multi-project scheduling. Auton Agents Multi-Agent Syst 31(6):1548–1577CrossRef

Zaidi BH et al (2021) Incentive based load shedding management in a microgrid using combinatorial auction with IoT infrastructure. Sensors 21(6):1935CrossRef

Ehsanfar A, Grogan PT (2020) Auction-based algorithms for routing and task scheduling in federated networks. J Netw Syst Manag 28(2):271–297CrossRef

Zhang Z et al (2019) Exact algorithms for the vehicle routing problem with time windows and combinatorial auction. Transp Sci 53(2):427–441CrossRef

Hou L et al (2021) A simultaneous multi-round auction design for scheduling multiple charges of battery electric vehicles on highways. IEEE Trans Intell Transp Syst. https://doi.org/10.1109/TITS.2021.3075202CrossRef

Leyton-Brown K, Pearson M, Shoham Y (2000) Towards a universal test suite for combinatorial auction algorithms. In: Proceedings of the 2nd ACM conference on electronic commerce. association for computing machinery, Minneapolis, Minnesota, USA, EC ’00, pp. 66–76

10.

Balcan MF et al (2018) Learning to branch. In: International conference on machine learning. PMLR, Stockholm, Sweden, 80: 344–353

11.

Bengio Y, Lodi A, Prouvost A (2020) Machine learning for combinatorial optimization: a methodological tour d’horizon. Eur J Oper Res 290(2):405–421MathSciNetCrossRefMATH

12.

Gasse M et al (2019) Exact combinatorial optimization with graph convolutional neural networks. In: Proceedings of the 33rd international conference on neural information processing systems. Curran Associates Inc., Red Hook, NY, USA

13.

Silver D et al (2016) Mastering the game of Go with deep neural networks and tree search. Nature 529(7587):484–489CrossRef

14.

Li W, Chiu PWY, Li Z (2021) A novel neural approach to infinity-norm joint-velocity minimization of kinematically redundant robots under joint limits. IEEE Trans Neural Netw Learn Syst. https://doi.org/10.1109/TNNLS.2021.3095122CrossRef

15.

Li W, Song C, Li Z (2020) An accelerated recurrent neural network for visual servo control of a robotic flexible endoscope with joint limit constraint. IEEE Trans Ind Electron 67(12):10787–10797CrossRef

16.

Verma P, Parouha RP (2021) An advanced hybrid algorithm for engineering design optimization. Neural Process Lett 53:3693CrossRef

17.

Pooya A et al (2021) Neural network for a novel disturbance optimal control model for inventory and production planning in a four-echelon supply chain with reverse logistic. Neural Process Lett 53:4549CrossRef

18.

Linderoth JT, Savelsbergh MW (1999) A computational study of search strategies for mixed integer programming. Inf J Comput 11(2):173–187MathSciNetCrossRefMATH

19.

Jin L et al (2021) Perturbed manipulability optimization in a distributed network of redundant robots. IEEE Trans Ind Electron 68(8):7209–7220CrossRef

20.

Xiao L, Li K, Duan M (2019) Computing time-varying quadratic optimization with finite-time convergence and noise tolerance: a unified framework for zeroing neural network. IEEE Trans Neural Netw Learn Syst 30(11):3360–3369MathSciNetCrossRef

21.

Xiao L et al (2019) Zeroing neural dynamics for control design: comprehensive analysis on stability, robustness, and convergence speed. IEEE Trans Ind Inform 15(5):2605–2616CrossRef

22.

He H, Daume H III, Eisner JM (2014) Learning to search in branch and bound algorithms. Adv Neural Inf Process Syst 27:3293–3301

23.

Song J et al (2019) Learning to search via retrospective imitation. arXiv:1804.00846

24.

Baltean-Lugojan R et al (2018) Selecting cutting planes for quadratic semidefinite outer-approximation via trained neural networks. Technical report, CPLEX Optimization, IBM

25.

Tang Y, Agrawal S, Faenza Y (2020) Reinforcement learning for integer programming: learning to cut. In: International conference on machine learning. PMLR, Virtual Event, pp 9367–9376

26.

Hendel G, Miltenberger M, Witzig J (2019) Adaptive algorithmic behavior for solving mixed integer programs using bandit algorithms. In: Fortz B, Labbé M (eds) Operations research proceedings 2018. Springer, Cham, pp 513–519CrossRef

27.

Khalil EB et al (2017) Learning to run heuristics in tree search. In: Proceedings of the 26th international joint conference on artificial intelligence. AAAI Press, Melbourne, Australia, IJCAI’17, pp. 659–666

28.

Gupta P et al (2020) Hybrid models for learning to branch. Adv Neural Inf Process Syst 33:18087–18097

29.

Khalil E et al (2016) Learning to branch in mixed integer programming. In: Proceedings of the thirtieth AAAI conference on artificial intelligence. AAAI Press, Phoenix, Arizona, AAAI’16, pp. 724–731

30.

Achterberg T, Wunderling R (2013) Mixed integer programming: analyzing 12 years of progress. In: Jünger M, Reinelt G (eds) Facets of combinatorial optimization: festschrift for Martin Grötschel. Springer, Berlin, Heidelberg, pp 449–481CrossRefMATH

31.

Lodi A, Zarpellon G (2017) On learning and branching: a survey. TOP 25(2):207–236MathSciNetCrossRefMATH

32.

Alvarez AM, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. Inf J Comput 29(1):185–195MathSciNetCrossRefMATH

33.

Lu J, Kumar MP (2019) Neural network branching for neural network verification. In: International conference on learning representations

34.

Prouvost A et al (2020) Ecole: A Gym-like library for machine learning in combinatorial optimization solvers. ArXiv Prepr arXiv:2011.06069

35.

Balas E, Ho A (1980) Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study. In: Padberg MW (ed) Combinatorial optimization. Springer, Berlin, Heidelberg, pp 37–60CrossRefMATH

36.

Hashemi A et al (2021) A new direct coefficient-based heuristic algorithm for set covering problems. Int J Fuzzy Syst 24:1131CrossRef

37.

Avella P et al (2021) Weak flow cover inequalities for the capacitated facility location problem. Eur J Oper Res 289(2):485–494MathSciNetCrossRefMATH

38.

Cornuejols G, Sridharan R, Thizy JM (1991) A comparison of heuristics and relaxations for the capacitated plant location problem. Eur J Oper Res 50(3):280–297CrossRefMATH

39.

Bergman D et al (2016) Decision diagrams for optimization. Springer, Cham, GermanyCrossRefMATH

40.

Grzesik A et al (2022) Polynomial-time algorithm for maximum weight independent set on P 6-free graphs. ACM Trans Algorithms TALG 18(1):1–57MathSciNetCrossRef

41.

Gamrath G et al (2020) The SCIP optimization suite 7.0. Technical Report 20-10, Zuse Institute Berlin

Titel: Heavy-Head Sampling for Fast Imitation Learning of Machine Learning Based Combinatorial Auction Solver
verfasst von: Chen Peng
Bolin Liao
Publikationsdatum: 15.06.2022
Verlag: Springer US
Erschienen in: Neural Processing Letters / Ausgabe 1/2023
Print ISSN: 1370-4621
Elektronische ISSN: 1573-773X
DOI: https://doi.org/10.1007/s11063-022-10900-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2023

Stability Analysis of the Impulsive Projection Neural Network

Weighted Pseudo Almost-Automorphic Solutions of Quaternion-Valued RNNs With Mixed Delays

Author Profiling in Code-Mixed WhatsApp Messages Using Stacked Convolution Networks and Contextualized Embedding Based Text Augmentation

ChaInNet: Deep Chain Instance Segmentation Network for Panoptic Segmentation

HoINT: Learning Explicit and Implicit High-order Feature Interactions for Click-through Rate Prediction

Improving the Accuracy of Diabetes Diagnosis Applications through a Hybrid Feature Selection Algorithm

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.