Computational evaluation of cut-strengthening techniques in logic-based Benders’ decomposition

  • Aigerim Saken
  • Emil Karlsson
  • Stephen J. Maher
  • Elina Rönnberg
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Scheduling Tags , , , , ,

    Cut-strengthening techniques have a significant impact on the computational effectiveness of the Logic-based Benders’ decomposition (LBBD) scheme. While there have been numerous cut-strengthening techniques proposed, very little is understood about which techniques achieve the best computational performance for the LBBD scheme. This is typically due to implementations of LBBD being problem specific and thus, no … Read more

    On the Optimization Landscape of Burer-Monteiro Factorization: When do Global Solutions Correspond to Ground Truth?

  • Jianhao Ma
  • Salar Fattahi
    • Categories Global Optimization, Nonlinear Optimization, Optimization in Data Science Tags , ,

    In low-rank matrix recovery, the goal is to recover a low-rank matrix, given a limited number of linear and possibly noisy measurements. Low-rank matrix recovery is typically solved via a nonconvex method called Burer-Monteiro factorization (BM). If the rank of the ground truth is known, BM is free of sub-optimal local solutions, and its true solutions … Read more

    Yet another fast variant of Newton’s method for nonconvex optimization

  • Serge Gratton
  • Sadok Jerad
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    A second-order algorithm is proposed for minimizing smooth nonconvex functions that alternates between regularized Newton and negative curvature steps. In most cases, the Hessian matrix is regularized with the square root of the current gradient and an additional term taking moderate negative curvature into account, a negative curvature step being taken only exceptionnally. As a … Read more

    A Test Instance Generator for Multiobjective Mixed-integer Optimization

  • Gabriele Eichfelder
  • Tobias Gerlach
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization Tags , , ,

    Application problems can often not be solved adequately by numerical algorithms as several difficulties might arise at the same time. When developing and improving algorithms which hopefully allow to handle those difficulties in the future, good test instances are required. These can then be used to detect the strengths and weaknesses of different algorithmic approaches. … Read more

    Political districting to minimize county splits

  • Maral Shahmizad
  • Austin Buchanan
    • Categories Applications - OR and Management Sciences, Integer Programming, Network Optimization

    When partitioning a state into political districts, a common criterion is that political subdivisions like counties should not be split across multiple districts. This criterion is encoded into most state constitutions and is sometimes enforced quite strictly by the courts. However, map drawers, courts, and the public typically do not know what amount of splitting … Read more

    A successive centralized circumcentered-reflection method for the convex feasibility problem

  • Yunier Bello-Cruz
  • Roger Behling
  • A. N. Iusem
  • Luiz-Rafael Santos
  • Di Liu
    • Categories Convex Optimization Tags , , ,

    In this paper, we present a successive centralization process for the circumcentered-reflection scheme with several control sequences for solving the convex feasibility problem in Euclidean space. Assuming that a standard error bound holds, we prove the linear convergence of the method with the most violated constraint control sequence. Moreover, under additional smoothness assumptions on the … Read more

    Variable Selection for Kernel Two-Sample Tests

  • Jie Wang
  • Santanu S. Dey
  • Yao Xie
    • Categories (Mixed) Integer Nonlinear Programming, Optimization in Data Science Tags , ,

    We consider the variable selection problem for two-sample tests, aiming to select the most informative variables to determine whether two collections of samples follow the same distribution. To address this, we propose a novel framework based on the kernel maximum mean discrepancy (MMD). Our approach seeks a subset of variables with a pre-specified size that … Read more

    Robust Two-Dose Vaccination Schemes and the Directed b-Matching Problem

  • Jenny Segschneider
  • Arie M.C.A. Koster
    • Categories Applications - OR and Management Sciences, Robust Optimization Tags , , , ,

    In light of the recent pandemic and the shortage of vaccinations during their roll-out, questions arose regarding the best strategy to achieve immunity throughout the population by adjusting the time gap between the two necessary vaccination doses. This strategy has already been studied from different angles by various researches. However, the deliveries of vaccination doses … Read more

    A Sequential Quadratic Programming Method for Optimization with Stochastic Objective Functions, Deterministic Inequality Constraints and Robust Subproblems

  • Songqiang Qiu
  • Vyacheslav Kungurtsev
    • Categories Constrained Nonlinear Optimization, Other Topics, Stochastic Programming Tags , , ,

    In this paper, a robust sequential quadratic programming method of Burke and Han (Math Programming, 1989)  for constrained optimization is generalized to problem with stochastic objective function, deterministic equality and inequality constraints. A stochastic line search scheme in Paquette and Scheinberg (SIOPT, 2020) is employed to globalize the steps. We show that in the case … Read more