-
作者：Pulyassary, Haripriya; Kollias, Kostas; Schild, Aaron; Shmoys, David; Wu, Manxi
作者单位：Cornell University; Alphabet Inc.; Google Incorporated; University of California System; University of California Berkeley
摘要：In this article, we introduce new models and algorithms that extend the classical network flow problems to the setting with electric vehicles (EV) that accommodate EV-specific constraints such as range limitations, charging strategies, and station capacities. Our work focuses on solving three key problems: single EV optimal charging strategy, maximum EV flow, and minimum-cost EV flow, each central to the efficient operation of EV routing systems. We establish the computational complexity of th...
-
作者：Lovitz, Benjamin; Johnston, Nathaniel
作者单位：Northeastern University; Mount Allison University
摘要：We introduce a convergent hierarchy of lower bounds on the minimum value of a real form over the unit sphere. The main practical advantage of our hierarchy over the real sum-of-squares (RSOS) hierarchy is that the lower bound at each level of our hierarchy is obtained by a minimum eigenvalue computation, as opposed to the full semidefinite program (SDP) required at each level of RSOS. In practice, this allows us to compute bounds on much larger forms than are computationally feasible for RSOS....
-
作者：Cornuejols, Gerard; Dubey, Yatharth
作者单位：Carnegie Mellon University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：In this note, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis by streamlining the definition of branch-and-bound. We introduce skewed k-trees which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also give an example where lift-and-project does very well and branch-and-bound does not. Finally, we study the set of branc...
-
作者：He, Chang; Jiang, Yuntian; Zhang, Chuwen; Ge, Dongdong; Jiang, Bo; Ye, Yinyu
作者单位：Shanghai University of Finance & Economics; Shanghai Jiao Tong University; Stanford University
摘要：This paper proposes a homogeneous second-order descent framework (HSODF) for nonconvex and convex optimization based on the generalized homogeneous model (GHM). In comparison to the Newton steps, the GHM can be solved by extremal symmetric eigenvalue procedures and thus grant an advantage in ill-conditioned problems. Moreover, GHM extends the ordinary homogeneous model (Zhang et al. A homogenous second-order descent method for nonconvex optimization, 2022. arXiv:2211.08212 [math]) to allow ada...
-
作者：Leyffer, Sven; Manns, Paul
作者单位：United States Department of Energy (DOE); Argonne National Laboratory; Dortmund University of Technology
摘要：McCormick envelopes are a standard tool for deriving convex relaxations of optimization problems that involve polynomial terms. Such McCormick relaxations provide lower bounds, for example, in branch-and-bound procedures for mixed-integer nonlinear programs but have not gained much attention in PDE-constrained optimization so far. This lack of attention may be due to the distributed nature of such problems, which on the one hand leads to infinitely many linear constraints (generally state cons...
