Towards a geometric characterization of unbounded integer cubic optimization problems via thin rays

  • Alberto Del Pia
    • Categories (Mixed) Integer Nonlinear Programming

    We study geometric characterizations of unbounded integer polynomial optimization problems. While unboundedness along a ray fully characterizes unbounded integer linear and quadratic optimization problems, we show that this is not the case for cubic polynomials. To overcome this, we introduce thin rays, which are rays with an arbitrarily small neighborhood, and prove that they characterize … Read more

    Projection-width: a unifying structural parameter for separable discrete optimization

  • Alberto Del Pia
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, 0-1 Programming

    We introduce the notion of projection-width for systems of separable constraints, defined via branch decompositions of variables and constraints. We show that several fundamental discrete optimization and counting problems can be solved in polynomial time when the projection-width is polynomially bounded. These include optimization, counting, top-k, and weighted constraint violation. Our results identify a broad … Read more

    Branch-and-Cut for Computing Approximate Equilibria of Mixed-Integer Generalized Nash Games

  • Alois Duguet
  • Tobias Harks
  • Martin Schmidt
  • Julian Schwarz
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Game Theory Tags , , , ,

    Generalized Nash equilibrium problems with mixed-integer variables constitute an important class of games in which each player solves a mixed-integer optimization problem, where both the objective and the feasible set is parameterized by the rivals’ strategies. However, such games are known for failing to admit exact equilibria and also the assumption of all players being … Read more

    Lyapunov-based Analysis on First Order Method for Composite Strong-Weak Convex Functions

  • Milan Barik
  • Suvendu Ranjan Pattanaik
    • Categories Convex Optimization, Nonsmooth Optimization, Unconstrained Optimization Tags , , , , ,

    The Nesterov’s accelerated gradient (NAG) method generalizes the classical gradient descent algorithm by improving the convergence rate from $\mathcal{O}\left(\frac{1}{t}\right)$ to $\mathcal{O}\left(\frac{1}{t^2}\right)$ in convex optimization. This study examines the proximal gradient framework for additively separable composite functions with smooth and non-smooth components. We demonstrate that Nesterov’s accelerated proximal gradient (NAPG$_\alpha$) method attains a convergence rate of … Read more

    Counterfactual explanations with the k-Nearest Neighborhood classifier and uncertain data

  • Emilio Carrizosa
  • Renato De Leone
  • Marica Magagnini
    • Categories Bilevel Optimization, Robust Optimization Tags , , , ,

    Counterfactual Analysis is a powerful tool in Explainable Machine Learning. Given a classifier and a record, one seeks the smallest perturbation necessary to have the perturbed record, called the counterfactual explanation, classified in the desired class. Feature uncertainty in data reflects the inherent variability and noise present in real-world scenarios, and therefore, there is a … Read more

    Distributionally Robust Optimization with Integer Recourse: Convex Reformulations and Critical Recourse Decisions

  • Yiling Zhang
    • Categories Integer Programming, Robust Optimization, Stochastic Programming Tags , , , ,

    The paper studies distributionally robust optimization models with integer recourse. We develop a unified framework that provides finite tight convex relaxations under conic moment-based ambiguity sets and Wasserstein ambiguity sets.  They provide tractable primal representations without relying on sampling or semi-infinite optimization. Beyond tractability, the relaxations offer interpretability that captures the criticality of recourse decisions. … Read more

    Improving Directions in Mixed Integer Bilevel Linear Optimization

  • Federico Battista
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Bilevel Optimization, Branch and Cut Algorithms Tags , ,

    We consider the central role of improving directions in solution methods for mixed integer bilevel linear optimization problems (MIBLPs). Current state-of-the-art methods for solving MIBLPs employ the branch-and-cut framework originally developed for solving mixed integer linear optimization problems. This approach relies on oracles for two kinds of subproblems: those for checking whether a candidate pair … Read more

    On the Convexification of a Class of Mixed-Integer Conic Sets

  • GuxinDU
  • Rui Chen
  • Linchuan Wei
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming

    We investigate mixed-integer second-order conic (SOC) sets with a nonlinear right-hand side in the SOC constraint, a structure frequently arising in mixed-integer quadratically constrained programming (MIQCP). Under mild assumptions, we show that the convex hull can be exactly described by replacing the right-hand side with its concave envelope. This characterization enables strong relaxations for MIQCPs … Read more

    Closing the Gap: Efficient Algorithms for Discrete Wasserstein Barycenters

  • Jiaqi Wang
  • Weijun Xie
    • Categories Integer Programming, Optimization in Data Science Tags , , , ,

    The Wasserstein barycenter problem seeks a probability measure that minimizes the weighted average of the Wasserstein distances to a given collection of probability measures. We study the discrete setting, where each measure has finite support — a regime that frequently arises in machine learning and operations research. The discrete Wasserstein barycenter problem is known to … Read more

    An Exact Penalty Method for Stochastic Equality-Constrained Optimization

  • Yawen Cui
  • Qiankun Shi
  • Xiao Wang
  • Xiantao Xiao
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization

    In this paper, we study a penalty method for stochastic equality-constrained optimization, where both the objective and constraints are expressed in general expectation form. We introduce a novel adaptive strategy for updating the penalty parameter, guided by iteration progress to balance reductions in the penalty function with improvements in constraint violation, while each penalty subproblem … Read more