Document Open Access Logo

Differential Programming via OR Methods

Authors Shannon Sweitzer, T. K. Satish Kumar

PDF
Thumbnail PDF

File

LIPIcs.CP.2021.53.pdf
  • Filesize: 1.01 MB
  • 15 pages

Document Identifiers

Author Details

Shannon Sweitzer
  • Department of Industrial and Systems Engineering, University of Southern California, Los Angeles, CA, USA
T. K. Satish Kumar
  • Department of Computer Science, Department of Physics and Astronomy, Department of Industrial and Systems Engineering, Information Sciences Institute, University of Southern California, Los Angeles, CA, USA

Cite AsGet BibTex

Shannon Sweitzer and T. K. Satish Kumar. Differential Programming via OR Methods. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CP.2021.53

Abstract

Systems of ordinary differential equations (ODEs) and partial differential equations (PDEs) are extensively used in many fields of science, including physics, biochemistry, nonlinear control, and dynamical systems. On the one hand, analytical methods for solving systems of ODEs/PDEs mostly remain an art and are largely insufficient for complex systems. On the other hand, numerical approximation methods do not yield a viable analytical form of the solution that is often required for downstream tasks. In this paper, we present an approximate approach for solving systems of ODEs/PDEs analytically using solvers like Gurobi developed in Operations Research (OR). Our main idea is to represent entire functions as Bézier curves/surfaces with to-be-determined control points. The ODEs/PDEs as well as their boundary conditions can then be reformulated as constraints on these control points. In many cases, this reformulation yields quadratic programming problems (QPPs) that can be solved in polynomial time. It also allows us to reason about inequalities. We demonstrate the success of our approach on several interesting classes of ODEs/PDEs.

Subject Classification

ACM Subject Classification
  • Applied computing
Keywords
  • Differential Programming
  • Operations Research
  • Bézier Curves

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ji-wung Choi, Renwick Curry, and Gabriel Elkaim. Path planning based on bézier curve for autonomous ground vehicles. In Advances in Electrical and Electronics Engineering - IAENG Special Edition of the World Congress on Engineering and Computer Science, pages 158-166, 2008. Google Scholar
  2. Ken Dill and Sarina Bromberg. Molecular Driving Forces: Statistical Thermodynamics in Biology, Chemistry, Physics, and Nanoscience. Garland Science, 2012. Google Scholar
  3. Robert Eymard, Thierry Gallouët, and Raphaèle Herbin. Finite volume methods. Handbook of Numerical Analysis, 7:713-1018, 2000. Google Scholar
  4. N. Fallah and N. Nikraftar. Meshless finite volume method for the analysis of fracture problems in orthotropic media. Engineering Fracture Mechanics, 204:46-62, 2018. Google Scholar
  5. Gerald Farin. Curves and Surfaces for Computer-Aided Geometric Design: A Practical Guide. Elsevier, 2014. Google Scholar
  6. Torkel Glad and Lennart Ljung. Control Theory. CRC Press, 2018. Google Scholar
  7. Antonio Huerta, Ted Belytschko, Sonia Fernández-Méndez, Timon Rabczuk, Xiaoying Zhuang, and Marino Arroyo. Meshfree methods. Encyclopedia of Computational Mechanics (Second Edition), pages 1-38, 2018. Google Scholar
  8. Thomas Hughes, Giancarlo Sangalli, and Mattia Tani. Isogeometric Analysis: Mathematical and Implementational Aspects, with Applications. Lecture Notes in Mathematics Book Series (LNM, volume 2219), 2018. Google Scholar
  9. I. Krasilshchik and A. Vinogradov. Nonlocal trends in the geometry of differential equations: Symmetries, conservation laws, and bäcklund transformations. In Symmetries of Partial Differential Equations, pages 161-209. Springer, 1989. Google Scholar
  10. Tadeusz Liszka and Janusz Orkisz. The finite difference method at arbitrary irregular grids and its application in applied mechanics. Computers & Structures, 11(1-2):83-95, 1980. Google Scholar
  11. George Lorentz. Bernstein Polynomials. American Mathematical Soc., 1986. Google Scholar
  12. Michael Mortenson. Mathematics for Computer Graphics Applications. Industrial Press Inc., 1999. Google Scholar
  13. Lev Ovsiannikov. Group Analysis of Differential Equations. Academic Press, 2014. Google Scholar
  14. Michael Renardy and Robert Rogers. An Introduction to Partial Differential Equations. Springer, 2006. Google Scholar
  15. Alberto Rojo and Anthony Bloch. The Principle of Least Action: History and Physics. Cambridge University Press, 2018. Google Scholar
  16. Sarah Tang and Vijay Kumar. Safe and complete trajectory generation for robot teams with higher-order dynamics. In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1894-1901, 2016. Google Scholar
  17. Lianqiang Yang and Xiao-Ming Zeng. Bézier curves and surfaces with shape parameters. International Journal of Computer Mathematics, 86:1253-1263, 2009. Google Scholar
  18. Hugh Young, Roger Freedman, and Albert Ford. Sears and Zemansky’s University Physics. Pearson Addison-Wesley, 2006. Google Scholar
  19. Han Zhang, Neelesh Tiruviluamala, Sven Koenig, and T. K. Satish Kumar. Temporal reasoning with kinodynamic networks. In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling, 2021. Google Scholar
  20. Olgierd Zienkiewicz, Robert Taylor, Perumal Nithiarasu, and J. Zhu. The Finite Element Method. McGraw-Hill London, 1977. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact