CORE MACHINE LEARNING

Fit The Right NP-Hard Problem: End-to-end Learning of Integer Programming Constraints

December 12, 2020

Abstract

Bridging logical and algorithmic reasoning with modern machine learning techniques is a fundamental challenge with potentially transformative impact. On the algorithmic side, many NP-Hard problems can be expressed as integer programs, in which the constraints play the role of their combinatorial specification. In this work, we aim to fully integrate integer programming solvers into neural network architecture by providing gradient update rules for both the objective and the constraints. The resulting end-to-end trainable architectures have the power of jointly extracting features from raw data and of solving a suitable (learned) combinatorial problem with state-of-the-art integer programming solvers. We experimentally validate our approach in multiple ways: on random constraints, on solving Knapsack instances from their description in natural language, and on a popular computer vision benchmark regarding keypoint matching.

Download the Paper

AUTHORS

Written by

Brandon Amos

Anselm Paulus

Georg Martius

Michal Rolinek

Vit Musil

Publisher

NeurIPS Workshop on Learning Meets Combinatorial Optimization

Research Topics

Core Machine Learning

Related Publications

November 06, 2024

THEORY

CORE MACHINE LEARNING

The Road Less Scheduled

Aaron Defazio, Alice Yang, Harsh Mehta, Konstantin Mishchenko, Ahmed Khaled, Ashok Cutkosky

November 06, 2024

August 16, 2024

THEORY

REINFORCEMENT LEARNING

Dual Approximation Policy Optimization

Zhihan Xiong, Maryam Fazel, Lin Xiao

August 16, 2024

August 12, 2024

CORE MACHINE LEARNING

Contrastive Predict-and-Search for Mixed Integer Linear Programs

Arman Zharmagambetov, Yuandong Tian, Aaron Ferber, Bistra Dilkina, Taoan Huang

August 12, 2024

August 09, 2024

CORE MACHINE LEARNING

Benchmarking Attacks on Learning with Errors

Emily Wenger, Eshika Saxena, Mohamed Malhou, Ellie Thieu, Kristin Lauter

August 09, 2024

Help Us Pioneer The Future of AI

We share our open source frameworks, tools, libraries, and models for everything from research exploration to large-scale production deployment.