kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Partition-Based Formulations for Mixed-Integer Optimization of Trained ReLU Neural Networks
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.ORCID iD: 0000-0003-0299-5745
2021 (English)In: Advances in Neural Information Processing Systems, Neural information processing systems foundation , 2021, p. 3068-3080Conference paper, Published paper (Refereed)
Abstract [en]

This paper introduces a class of mixed-integer formulations for trained ReLU neural networks. The approach balances model size and tightness by partitioning node inputs into a number of groups and forming the convex hull over the partitions via disjunctive programming. At one extreme, one partition per input recovers the convex hull of a node, i.e., the tightest possible formulation for each node. For fewer partitions, we develop smaller relaxations that approximate the convex hull, and show that they outperform existing formulations. Specifically, we propose strategies for partitioning variables based on theoretical motivations and validate these strategies using extensive computational experiments. Furthermore, the proposed scheme complements known algorithmic approaches, e.g., optimization-based bound tightening captures dependencies within a partition.

Place, publisher, year, edition, pages
Neural information processing systems foundation , 2021. p. 3068-3080
Keywords [en]
Integer programming, Algorithmic approach, Balance model, Computational experiment, Convex hull, Disjunctive programming, Mixed integer, Mixed integer optimization, Model size, Neural-networks, Optimisations, Computational geometry
National Category
Computer graphics and computer vision
Identifiers
URN: urn:nbn:se:kth:diva-316181ISI: 000922928402052Scopus ID: 2-s2.0-85131781027OAI: oai:DiVA.org:kth-316181DiVA, id: diva2:1699251
Conference
35th Conference on Neural Information Processing Systems, NeurIPS 2021, 6 December - 14 December 2021, Virtual/Online
Note

Part of proceedings: ISBN 978-1-7138-4539-3

QC 20220927

Available from: 2022-09-27 Created: 2022-09-27 Last updated: 2025-02-07Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Authority records

Kronqvist, Jan

Search in DiVA

By author/editor
Kronqvist, Jan
By organisation
Optimization and Systems Theory
Computer graphics and computer vision

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 39 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf