{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T08:26:58Z","timestamp":1768120018545,"version":"3.49.0"},"reference-count":60,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T00:00:00Z","timestamp":1767830400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Robot. AI"],"abstract":"<jats:p>\n                    This paper presents a comparative study of data-driven acceleration techniques for mixed-integer bilinear programs (MIBLPs) applied to robot motion planning. MIBLPs combine discrete decision variables and nonlinear constraints, making them computationally challenging for real-time robotics applications. We investigate two reformulation strategies: (1) converting binary variables into continuous variables with complementarity constraints (MPCC), and (2) converting bilinear constraints into mixed-integer linear constraints using McCormick envelopes (MICP). Using offline computed solutions as datasets, we apply K-nearest neighbor methods to warm-start both reformulations. We experimented with the proposed data-driven MIBLP formulation for motion planning on a linear inverted pendulum with contacts, and planning motion using a single rigid body model with mode transitions and contacts. Our results demonstrate that when sufficient data is available, MICP achieves consistently fast solving speeds that are suitable for real-time computation, while MPCC achieves higher success rates with limited amount of data. Our approach is capable of planning motions for the SCALER robot platform to transition between bipedal and quadrupedal configurations to navigate around obstacles without pre-specified gaits. Code for reproducing our results is available at\n                    <jats:ext-link>https:\/\/github.com\/XuanLin\/MIBLP_benchmark<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.3389\/frobt.2025.1656564","type":"journal-article","created":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T12:53:02Z","timestamp":1767876782000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Data-driven acceleration of mixed-integer bilinear programs: a comparative study for robot motion planning"],"prefix":"10.3389","volume":"12","author":[{"given":"Xuan","family":"Lin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1965","published-online":{"date-parts":[[2026,1,8]]},"reference":[{"key":"B1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1023\/a:1008292328909","article-title":"Formulating dynamic multi-rigid-body contact problems with friction as solvable linear complementarity problems","volume":"14","author":"Anitescu","year":"1997","journal-title":"Nonlinear Dyn."},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2024.3435423","article-title":"Consensus complementarity control for multi-contact mpc","author":"Aydinoglu","year":"2023","journal-title":"arXiv Prepr. arXiv:2304"},{"key":"B3","article-title":"Deep learning warm starts for trajectory optimization on the international space station","author":"Banerjee","year":"2025"},{"key":"B4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/s0005-1098(01)00174-1","article-title":"The explicit linear quadratic regulator for constrained systems","volume":"38","author":"Bemporad","year":"2002","journal-title":"Automatica"},{"key":"B5","volume-title":"Branch and bound methods","author":"Boyd","year":"2007"},{"key":"B6","doi-asserted-by":"publisher","first-page":"2272","DOI":"10.2514\/1.g008791","article-title":"Constraint-informed learning for warm-starting trajectory optimization","volume":"48","author":"Briden","year":"2025","journal-title":"J. Guid. Control, Dyn."},{"key":"B7","first-page":"1916","volume-title":"Motion planning diffusion: learning and planning of robot motions with diffusion models","author":"Carvalho","year":"2023"},{"key":"B8","doi-asserted-by":"publisher","first-page":"1447","DOI":"10.1109\/lra.2021.3135931","article-title":"Coco: online mixed-integer control via supervised learning","volume":"7","author":"Cauligi","year":"2021","journal-title":"IEEE Robotics Automation Lett."},{"key":"B10","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-11008-0","volume-title":"Integer programming models","author":"Conforti","year":"2014"},{"key":"B11","first-page":"295","article-title":"Whole-body motion planning with centroidal dynamics and full kinematics","author":"Dai","year":"2014"},{"key":"B12","doi-asserted-by":"publisher","first-page":"1420","DOI":"10.1177\/0278364919846512","article-title":"Global inverse kinematics via mixed-integer convex optimization","volume":"38","author":"Dai","year":"2019","journal-title":"Int. J. Robotics Res."},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2409.05864","article-title":"Neural mp: a generalist neural motion planner","author":"Dalal","year":"2024","journal-title":"arXiv Prepr. arXiv:2409.05864"},{"key":"B14","first-page":"279","article-title":"Footstep planning on uneven terrain with mixed-integer convex optimization","author":"Deits","year":"2014"},{"key":"B15","first-page":"1","article-title":"Dynamic locomotion in the mit cheetah 3 through convex model-predictive control","author":"Di Carlo","year":"2018"},{"key":"B16","first-page":"299","article-title":"Orientation-aware model predictive control with footstep adaptation for dynamic humanoid walking","author":"Ding","year":"2022"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1504.00719","article-title":"Rapidly computable viscous friction and no-slip rigid contact models","author":"Drumwright","year":"2015","journal-title":"arXiv Prepr. arXiv:1504.00719"},{"key":"B18","doi-asserted-by":"publisher","first-page":"3976","DOI":"10.1021\/ie980792u","article-title":"Algorithms for the solution of multiparametric mixed-integer nonlinear optimization problems","volume":"38","author":"Dua","year":"1999","journal-title":"Industrial and Eng. Chem. Res."},{"key":"B19","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1023\/a:1019241000636","article-title":"An algorithm for the solution of multiparametric mixed integer linear programming problems","volume":"99","author":"Dua","year":"2000","journal-title":"Ann. Operations Res."},{"key":"B20","volume-title":"Ntroduction to sensitivity and stability analysis in nonlinear programmingI","author":"Fiacco","year":"1983"},{"key":"B21","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1016\/j.ejor.2019.09.043","article-title":"A branch-and-cut algorithm for mixed-integer bilinear programming","volume":"282","author":"Fischetti","year":"2020","journal-title":"Eur. J. Operational Res."},{"key":"B22","volume-title":"Postoptimal analyses in Parametric Programming, and Related Topics: degeneracy, multicriteria decision making, redundancy (Walter de Gruyter)","author":"Gal","year":"2010"},{"key":"B23","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/bf00934810","article-title":"Generalized benders decomposition","volume":"10","author":"Geoffrion","year":"1972","journal-title":"J. Optim. Theory Appl."},{"key":"B24","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1137\/110836183","article-title":"Solving mixed integer bilinear problems using milp formulations","volume":"23","author":"Gupte","year":"2013","journal-title":"SIAM J. Optim."},{"key":"B25","volume-title":"Gurobi optimizer reference manual","year":"2024"},{"key":"B26","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1109\/tro.2016.2623345","article-title":"Learning the problem-optimum map: analysis and application to global optimization in robotics","volume":"33","author":"Hauser","year":"2016","journal-title":"IEEE Trans. Robotics"},{"key":"B27","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1177\/0278364920913938","article-title":"Reactive planar non-prehensile manipulation with hybrid model predictive control","volume":"39","author":"Hogan","year":"2020","journal-title":"Int. J. Robotics Res."},{"key":"B28","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0167-6377(91)90010-m","article-title":"A unified approach to interior point algorithms for linear complementarity problems: a summary","volume":"10","author":"Kojima","year":"1991","journal-title":"Operations Res. Lett."},{"key":"B9","doi-asserted-by":"publisher","first-page":"1617","DOI":"10.1109\/TRO.2024.3351554","article-title":"Fast contact-implicit model predictive control","volume":"40","author":"Le Cleac\u2019h","year":"2024","journal-title":"IEEE Transactions on Robotics"},{"key":"B29","first-page":"308","article-title":"Constraint-aware diffusion models for trajectory optimization","author":"Li","year":"2024"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2406.00780","article-title":"Accelerate hybrid model predictive control using generalized benders decomposition","author":"Lin","year":"2024","journal-title":"arXiv Prepr. arXiv:2406.00780"},{"key":"B31","first-page":"1918","article-title":"Optimization based motion planning for multi-limbed vertical climbing robots","author":"Lin","year":"2019"},{"key":"B32","doi-asserted-by":"crossref","DOI":"10.1109\/ICRA48506.2021.9561418","article-title":"Designing multi-stage coupled convex programming with data-driven mccormick envelope relaxations for motion planning","author":"Lin","year":"2021"},{"key":"B33","first-page":"4459","article-title":"Reduce: reformulation of mixed integer programs using data from unsupervised clusters for learning efficient strategies","author":"Lin","year":"2022"},{"key":"B34","first-page":"482","article-title":"Evaluating data-driven performances of mixed integer bilinear formulations for book placement planning","author":"Lin","year":"2024"},{"key":"B35","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511983658","volume-title":"Mathematical programs with equilibrium constraints","author":"Luo","year":"1996"},{"key":"B36","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/S0166-218X(01)00348-1","article-title":"Cutting planes in integer and mixed integer","volume":"11","author":"Marchand","year":"2002","journal-title":"Discrete Optim. State Art"},{"key":"B37","volume-title":"Graphs of convex sets with applications to optimal control and motion planning","author":"Marcucci","year":"2024"},{"key":"B38","doi-asserted-by":"publisher","first-page":"2433","DOI":"10.1109\/tac.2020.3007688","article-title":"Warm start of mixed-integer programs for model predictive control of hybrid systems","volume":"66","author":"Marcucci","year":"2020","journal-title":"IEEE Trans. Automatic Control"},{"key":"B39","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/bf01580665","article-title":"Computability of global solutions to factorable nonconvex programs: part i\u2014convex underestimating problems","volume":"10","author":"McCormick","year":"1976","journal-title":"Math. Program."},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2012.13349","article-title":"Solving mixed integer programs using neural networks","author":"Nair","year":"2020","journal-title":"arXiv Prepr. arXiv:2012.13349"},{"key":"B41","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s11590-017-1132-y","article-title":"A semidefinite programming method for integer convex quadratic minimization","volume":"12","author":"Park","year":"2018","journal-title":"Optim. Lett."},{"key":"B42","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/s0098-1354(01)00739-6","article-title":"On-line optimization via off-line parametric optimization tools","volume":"26","author":"Pistikopoulos","year":"2002","journal-title":"Comput. and Chem. Eng."},{"key":"B43","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1177\/0278364913506757","article-title":"A direct method for trajectory optimization of rigid bodies through contact","volume":"33","author":"Posa","year":"2014","journal-title":"Int. J. Robotics Res."},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2205.04667","article-title":"Variational inference mpc using normalizing flows and out-of-distribution projection","author":"Power","year":"2022","journal-title":"arXiv Prepr. arXiv:2205.04667"},{"key":"B45","doi-asserted-by":"publisher","first-page":"3139","DOI":"10.1002\/oca.3030","article-title":"Tailored presolve techniques in branch-and-bound method for fast mixed-integer optimal control applications","volume":"44","author":"Quirynen","year":"2023","journal-title":"Optim. Control Appl. Methods"},{"key":"B46","first-page":"1","article-title":"Adaptive force controller for contact-rich robotic systems using an unscented kalman filter","author":"Schperberg","year":"2023"},{"key":"B47","doi-asserted-by":"publisher","first-page":"4994","DOI":"10.1109\/lra.2020.3001503","article-title":"Risk-aware motion planning for a limbed robot with stochastic gripping forces using nonlinear programming","volume":"5","author":"Shirai","year":"2020","journal-title":"IEEE Robotics Automation Lett."},{"key":"B48","doi-asserted-by":"publisher","first-page":"1951","DOI":"10.1016\/j.compchemeng.2004.03.011","article-title":"Continuous reformulations of discrete\u2013continuous optimization problems","volume":"28","author":"Stein","year":"2004","journal-title":"Comput. and Chem. Eng."},{"key":"B49","first-page":"5632","article-title":"Scaler: a tough versatile quadruped free-climber robot","author":"Tanaka","year":"2022"},{"key":"B50","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/s42064-019-0051-3","article-title":"A data-driven indirect method for nonlinear optimal control","volume":"3","author":"Tang","year":"2019","journal-title":"Astrodynamics"},{"key":"B51","first-page":"9367","article-title":"Reinforcement learning for integer programming: learning to cut","author":"Tang","year":"2020"},{"key":"B52","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1016\/s0005-1098(02)00250-9","article-title":"An algorithm for multi-parametric quadratic programming and explicit mpc solutions","volume":"39","author":"T\u00f8ndel","year":"2003","journal-title":"Automatica"},{"key":"B53","first-page":"1934","volume-title":"Faster: fast and safe trajectory planner for flights in unknown environments","author":"Tordesillas","year":"2019"},{"key":"B54","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s10107-009-0295-4","article-title":"Modeling disjunctive constraints with a logarithmic number of binary variables and constraints","volume":"128","author":"Vielma","year":"2011","journal-title":"Math. Program."},{"key":"B55","volume-title":"An interior point algorithm for large-scale nonlinear optimization with applications in process engineering","author":"Wachter","year":"2002"},{"key":"B56","volume-title":"Model building in mathematical programming","author":"Williams","year":"2013"},{"key":"B57","doi-asserted-by":"publisher","first-page":"1560","DOI":"10.1109\/lra.2018.2798285","article-title":"Gait and trajectory optimization for legged systems through phase-based end-effector parameterization","volume":"3","author":"Winkler","year":"2018","journal-title":"IEEE Robotics Automation Lett."},{"key":"B58","first-page":"665","article-title":"Trajectory optimization of mechanical hybrid systems using sumt","author":"Yunt","year":"2006"},{"key":"B59","first-page":"2033","article-title":"Transition motion planning for multi-limbed vertical climbing robots using complementarity constraints","author":"Zhang","year":"2021"},{"key":"B60","doi-asserted-by":"publisher","first-page":"5239","DOI":"10.1016\/j.ifacol.2020.12.1200","article-title":"Fast non-parametric learning to accelerate mixed-integer programming for hybrid model predictive control","volume":"53","author":"Zhu","year":"2020","journal-title":"IFAC-Papers Online"}],"container-title":["Frontiers in Robotics and AI"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/frobt.2025.1656564\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T12:53:06Z","timestamp":1767876786000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/frobt.2025.1656564\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,8]]},"references-count":60,"alternative-id":["10.3389\/frobt.2025.1656564"],"URL":"https:\/\/doi.org\/10.3389\/frobt.2025.1656564","relation":{},"ISSN":["2296-9144"],"issn-type":[{"value":"2296-9144","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,8]]},"article-number":"1656564"}}