Mon 19 Jun 2023 10:00 - 10:20 at Royal - PLDI: Welcome & Opening Session Chair(s): Nate Foster

While mixed integer linear programming (MILP) solvers are routinely used to solve a wide range of important science and engineering problems, it remains a challenging task for end users to write correct and efficient MILP constraints, especially for problems specified using the inherently non-linear Boolean logic operations. To overcome this challenge, we propose a syntax guided synthesis (SyGuS) method capable of generating high-quality MILP constraints from the specifications expressed using arbitrary combinations of Boolean logic operations. At the center of our method is an extensible domain specification language (DSL) whose expressiveness may be improved by adding new integer variables as decision variables, together with an iterative procedure for synthesizing linear constraints from non-linear Boolean logic operations using these integer variables. To make the synthesis method efficient, we also propose an over-approximation technique for soundly proving the correctness of the synthesized linear constraints, and an under-approximation technique for safely pruning away the incorrect constraints. We have implemented and evaluated the method on a wide range of benchmark specifications from statistics, machine learning, and data science applications. The experimental results show that the method is efficient in handling these benchmarks, and the quality of the synthesized MILP constraints is close to, or higher than, that of manually-written constraints in terms of both compactness and solving time.

Mon 19 Jun

Displayed time zone: Eastern Time (US & Canada) change

09:00 - 11:00
PLDI: Welcome & Opening SessionPLDI Research Papers at Royal
Chair(s): Nate Foster Cornell University

#pldi-mon-0900-opening-royal Discord icon small YouTube icon small

09:00
20m
Day opening
Welcome to PLDI
PLDI Research Papers
Steve Blackburn Google and Australian National University, Nate Foster Cornell University
09:20
20m
Talk
Mosaic: An Interoperable Compiler for Tensor AlgebraDistinguished Paper
PLDI Research Papers
Manya Bansal Stanford University, Olivia Hsu Stanford University, Kunle Olukotun Stanford University, Fredrik Kjolstad Stanford University
DOI
09:40
20m
Talk
CryptOpt: Verified Compilation with Randomized Program Search for Cryptographic PrimitivesDistinguished Paper
PLDI Research Papers
Joel Kuepper University of Adelaide, Andres Erbsen MIT, Jason Gross MIT CSAIL, Owen Conoly MIT, Chuyue Sun Stanford, Samuel Tian MIT, David Wu University of Adelaide, Adam Chlipala Massachusetts Institute of Technology, Chitchanok Chuengsatiansup The University of Melbourne, Daniel Genkin Georgia Tech, Markus Wagner Monash University, Australia, Yuval Yarom Ruhr University Bochum
DOI Pre-print
10:00
20m
Talk
Synthesizing MILP Constraints for Efficient and Robust OptimizationDistinguished Paper
PLDI Research Papers
Jingbo Wang University of Southern California, Aarti Gupta Princeton University, Chao Wang University of Southern California
DOI
10:20
20m
Talk
An Automata-Based Framework for Verification and Bug Hunting in Quantum CircuitsDistinguished Paper
PLDI Research Papers
Yu-Fang Chen Academia Sinica, Taiwan, Kai-Min Chung Academia Sinica, Ondřej Lengál Brno University of Technology, Jyun-Ao Lin Academia Sinica, Wei-Lun Tsai Academia Sinica, Di-De Yen Academia Sinica
DOI
10:40
20m
Talk
Covering All the Bases: Type-Based Verification of Test Input GeneratorsDistinguished Paper
PLDI Research Papers
Zhe Zhou Purdue University, Ashish Mishra Purdue University, Benjamin Delaware Purdue University, Suresh Jagannathan Purdue University
DOI Pre-print