Paper 2021/1099 Original: eprint.iacr.org/2021/1099 ↗
MILP modeling of Boolean functions by minimum number of inequalities
Abstract
This work presents techniques for modeling Boolean functions by mixed-integer linear inequalities (MILP) on binary variables in-place (without auxiliary variables), reaching minimum possible number of inequalities for small functions and providing meaningful lower bounds on the number of inequalities when reaching the minimum is infeasible. While the minimum number of inequalities does not directly translate to best performance in MILP applications, it nonetheless provides a useful benchmark. We remark that our framework is heuristic and relies on SAT solvers and MILP optimization and so its feasibility is limited.
Metadata
- Available format(s)
PDF- Category
- Secret-key cryptography
- Publication info
- Preprint.
- History
- 2021-08-26: last updated
- 2021-08-26: published
- Short URL
- https://ia.cr/2021/1099
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2021/1099,
author = {Aleksei Udovenko},
title = {MILP modeling of Boolean functions by minimum number of inequalities},
howpublished = {Cryptology {ePrint} Archive, Paper 2021/1099},
year = {2021},
url = {https://eprint.iacr.org/2021/1099}
}