“Mixed integer neural inverse design” by Ansari, Seidel and Babaei

In computational design and fabrication, neural networks are becoming important surrogates for bulky forward simulations. A long-standing, intertwined question is that of inverse design: how to compute a design that satisfies a desired target performance? Here, we show that the piecewise linear property, very common in everyday neural networks, allows for an inverse design formulation based on mixed-integer linear programming. Our mixed-integer inverse design uncovers globally optimal or near optimal solutions in a principled manner. Furthermore, our method significantly facilitates emerging, but challenging, combinatorial inverse design tasks, such as material selection. For problems where finding the optimal solution is intractable, we develop an efficient yet near-optimal hybrid approach. Eventually, our method is able to find solutions provably robust to possible fabrication perturbations among multiple designs with similar performances. Our code and data are available at https://gitlab.mpi-klsb.mpg.de/nansari/mixed-integer-neural-inverse-design.

1. Navid Ansari, Omid Alizadeh-Mousavi, Hans-Peter Seidel, and Vahid Babaei. 2020. Mixed integer ink selection for spectral reproduction. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–16.Google ScholarDigital Library
2. Lynton Ardizzone, Jakob Kruse, Carsten Rother, and Ullrich Köthe. 2019. Analyzing Inverse Problems with Invertible Neural Networks. In International Conference on Learning Representations. https://openreview.net/forum?id=rJed6j0cKXGoogle Scholar
3. Vahid Babaei, Kiril Vidimče, Michael Foshey, Alexandre Kaspar, Piotr Didyk, and Wojciech Matusik. 2017. Color contoning for 3D printing. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1–15.Google ScholarDigital Library
4. Pietro Belotti, Christian Kirches, Sven Leyffer, Jeff Linderoth, James Luedtke, and Ashutosh Mahajan. 2013. Mixed-integer nonlinear optimization. Acta Numerica 22 (2013), 1–131.Google ScholarCross Ref
5. Amit H Bermano, Thomas Funkhouser, and Szymon Rusinkiewicz. 2017. State of the art in methods and representations for fabrication-aware design. In Computer Graphics Forum, Vol. 36. Wiley Online Library, 509–535.Google Scholar
6. Katia Bertoldi, Vincenzo Vitelli, Johan Christensen, and Martin Van Hecke. 2017. Flexible mechanical metamaterials. Nature Reviews Materials 2, 11 (2017), 1–11.Google ScholarCross Ref
7. Rudy Bunel, Jingyue Lu, Ilker Turkaslan, Pushmeet Kohli, P Torr, and P Mudigonda. 2020. Branch and bound for piecewise linear neural network verification. Journal of Machine Learning Research 21, 2020 (2020).Google Scholar
8. Rudy R Bunel, Ilker Turkaslan, Philip Torr, Pushmeet Kohli, and Pawan K Mudigonda. 2018. A Unified View of Piecewise Linear Neural Network Verification. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. Curran Associates, Inc., 4790–4799. https://proceedings.neurips.cc/paper/2018/file/be53d253d6bc3258a8160556dda3e9b2-Paper.pdfGoogle Scholar
9. Desai Chen, David IW Levin, Piotr Didyk, Pitchaya Sitthi-Amorn, and Wojciech Matusik. 2013. Spec2Fab: a reducer-tuner model for translating specifications to 3D prints. ACM Transactions on Graphics (TOG) 32, 4 (2013), 135.Google ScholarDigital Library
10. Chih-Hong Cheng, Georg Nührenberg, and Harald Ruess. 2017. Maximum resilience of artificial neural networks. In International Symposium on Automated Technology for Verification and Analysis. Springer, 251–268.Google ScholarCross Ref
11. Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. 2017. Density estimation using Real NVP. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24–26, 2017, Conference Track Proceedings. OpenReview.net. https://openreview.net/forum?id=HkpbnH9lxGoogle Scholar
12. Matteo Fischetti and Jason Jo. 2018. Deep neural networks and mixed integer linear optimization. Constraints 23, 3 (2018), 296–309.Google ScholarDigital Library
13. Christodoulos A Floudas. 1995. Nonlinear and mixed-integer optimization: fundamentals and applications. Oxford University Press.Google Scholar
14. Konstantinos Gavriil, Ruslan Guseinov, Jesús Pérez, Davide Pellis, Paul Henderson, Florian Rist, Helmut Pottmann, and Bernd Bickel. 2020. Computational design of cold bent glass façades. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–16.Google ScholarDigital Library
15. LLC Gurobi Optimization. 2018. Gurobi Optimizer Reference Manual. http://www.gurobi.comGoogle Scholar
16. Robert Hecht-Nielsen. 1992. Theory of the backpropagation neural network. In Neural networks for perception. Elsevier, 65–93.Google ScholarDigital Library
17. Kurt Hornik, Maxwell Stinchcombe, and Halbert White. 1989. Multilayer feedforward networks are universal approximators. Neural networks 2, 5 (1989), 359–366.Google ScholarDigital Library
18. Jiaqi Jiang, Mingkun Chen, and Jonathan A Fan. 2020. Deep neural networks for the evaluation and design of photonic devices. Nature Reviews Materials (2020), 1–22.Google Scholar
19. Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. 2017. Learning Combinatorial Optimization Algorithms over Graphs. In Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. Curran Associates, Inc. https://proceedings.neurips.cc/paper/2017/file/d9896106ca98d3d05b8cbdf4fd8b13a1-Paper.pdfGoogle Scholar
20. Yashar Kiarashinejad, Sajjad Abdollahramezani, and Ali Adibi. 2020. Deep learning approach based on dimensionality reduction for designing electromagnetic nanostructures. npj Computational Materials 6, 1 (2020), 1–12.Google Scholar
21. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014).Google Scholar
22. Diederik P Kingma and Max Welling. 2013. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114 (2013).Google Scholar
23. Ed Klotz and Alexandra M Newman. 2013. Practical guidelines for solving difficult mixed integer linear programs. Surveys in Operations Research and Management Science 18, 1–2 (2013), 18–32.Google ScholarCross Ref
24. Dianjing Liu, Yixuan Tan, Erfan Khoram, and Zongfu Yu. 2018. Training deep neural networks for the inverse design of nanophotonic structures. ACS Photonics 5, 4 (2018), 1365–1369.Google ScholarCross Ref
25. Johan Lofberg. 2004. YALMIP: A toolbox for modeling and optimization in MATLAB. In 2004 IEEE international conference on robotics and automation (IEEE Cat. No. 04CH37508). IEEE, 284–289.Google ScholarCross Ref
26. Carmel Majidi. 2014. Soft robotics: a perspective—current trends and prospects for the future. Soft robotics 1, 1 (2014), 5–11.Google Scholar
27. Harry M Markowitz and Alan S Manne. 1957. On the solution of discrete programming problems. Econometrica: journal of the Econometric Society (1957), 84–110.Google Scholar
28. Wojciech Matusik, Boris Ajdin, Jinwei Gu, Jason Lawrence, Hendrik P. A. Lensch, Fabio Pellacini, and Szymon Rusinkiewicz. 2009. Printing Spatially-varying Reflectance. ACM Trans. Graph. 28, 5 (Dec. 2009), 128:1–128:9.Google ScholarDigital Library
29. Niloy J Mitra and Mark Pauly. 2009. Shadow art. ACM Transactions on Graphics 28, CONF (2009), 156–1.Google Scholar
30. Guido F Montufar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. 2014. On the number of linear regions of deep neural networks. In Advances in neural information processing systems. 2924–2932.Google Scholar
31. Christian C Nadell, Bohao Huang, Jordan M Malof, and Willie J Padilla. 2019. Deep learning for accelerated all-dielectric metasurface design. Optics express 27, 20 (2019), 27523–27535.Google Scholar
32. Thomas Nindel, Tomáš Iser, Tobias Rittig, Alexander Wilkie, and Jaroslav Křivánek. 2021. A Gradient-Based Framework for 3D Print Appearance Optimization. ACM Transactions on Graphics (TOG) 40, 4 (2021).Google ScholarDigital Library
33. John Peurifoy, Yichen Shen, Li Jing, Yi Yang, Fidel Cano-Renteria, Brendan G DeLacy, John D Joannopoulos, Max Tegmark, and Marin Soljačić. 2018. Nanophotonic particle simulation and inverse design using artificial neural networks. Science advances 4, 6 (2018), eaar4206.Google Scholar
34. Michal Piovarči, Michael Foshey, Vahid Babaei, Szymon Rusinkiewicz, Wojciech Matusik, and Piotr Didyk. 2020. Towards spatially varying gloss reproduction for 3D printing. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–13.Google ScholarDigital Library
35. Panagiotis Polygerinos, Zheng Wang, Kevin C Galloway, Robert J Wood, and Conor J Walsh. 2015. Soft robotic glove for combined assistance and at-home rehabilitation. Robotics and Autonomous Systems 73 (2015), 135–143.Google ScholarDigital Library
36. Simiao Ren, Willie Padilla, and Jordan Malof. 2020. Benchmarking Deep Inverse Models over time, and the Neural-Adjoint method. In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (Eds.), Vol. 33. Curran Associates, Inc., 38–48. https://proceedings.neurips.cc/paper/2020/file/007ff380ee5ac49ffc34442f5c2a2b86-Paper.pdfGoogle Scholar
37. Christian Schüller, Daniele Panozzo, and Olga Sorkine-Hornung. 2014. Appearance-mimicking surfaces. ACM Transactions on Graphics (TOG) 33, 6 (2014), 1–10.Google ScholarDigital Library
38. Christian Schumacher, Bernd Bickel, Jan Rys, Steve Marschner, Chiara Daraio, and Markus Gross. 2015. Microstructures to control elasticity in 3D printing. ACM Transactions on Graphics (TOG) 34, 4 (2015), 136.Google ScholarDigital Library
39. Yuliy Schwartzburg, Romain Testuz, Andrea Tagliasacchi, and Mark Pauly. 2014. High-contrast computational caustic design. ACM Transactions on Graphics (TOG) 33, 4 (2014), 1–11.Google ScholarDigital Library
40. Liang Shi, Vahid Babaei, Changil Kim, Michael Foshey, Yuanming Hu, Pitchaya Sitthi-Amorn, Szymon Rusinkiewicz, and Wojciech Matusik. 2018. Deep multispectral painting reproduction via multi-layer, custom-ink printing. ACM Trans. Graph. 37, 6 (Dec. 2018), 271:1–271:15.Google ScholarDigital Library
41. Ole Sigmund. 2009. Manufacturing tolerant topology optimization. Acta Mechanica Sinica 25, 2 (2009), 227–239.Google ScholarCross Ref
42. Denis Sumin, Tobias Rittig, Vahid Babaei, Thomas Nindel, Alexander Wilkie, Piotr Didyk, Bernd Bickel, Jaroslav Krivánek, Karol Myszkowski, and Tim Weyrich. 2019. Geometry-aware scattering compensation for 3D printing. ACM Trans. Graph. 38, 4 (2019).Google ScholarDigital Library
43. Xingyuan Sun, Tianju Xue, Szymon M Rusinkiewicz, and Ryan P Adams. 2021. Amortized Synthesis of Constrained Configurations Using a Differentiable Surrogate. arXiv preprint arXiv:2106.09019 (2021).Google Scholar
44. Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. 2019. Evaluating Robustness of Neural Networks with Mixed Integer Programming. In International Conference on Learning Representations. https://openreview.net/forum?id=HyGIdiRqtmGoogle Scholar
45. Chelsea Tymms, Siqi Wang, and Denis Zorin. 2020. Appearance-preserving tactile optimization. ACM Transactions on Graphics (TOG) 39, 6 (2020), 1–16.Google ScholarDigital Library
46. Juan Pablo Vielma. 2015. Mixed integer linear programming formulation techniques. Siam Review 57, 1 (2015), 3–57.Google ScholarDigital Library
47. Tianju Xue, Alex Beatson, Sigrid Adriaenssens, and Ryan Adams. 2020. Amortized finite element analysis for fast PDE-constrained optimization. In International Conference on Machine Learning. PMLR, 10638–10647.Google Scholar
48. John AC Yule. 1967. Principles of color reproduction: applied to photomechanical reproduction, color photography, and the ink, paper, and other related industries. Wiley New York.Google Scholar
49. Ziwei Zhu, Utsav D Dave, Michal Lipson, and Changxi Zheng. 2020. Inverse geometric design of fabrication-robust nanophotonic waveguides. In 2020 Conference on Lasers and Electro-Optics (CLEO). IEEE, 1–2.Google ScholarCross Ref