An Exact Cutting Plane Method for hBcsubmodular Function Maximization

  • Simge Küçükyavuz
  • Qimeng Yu
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra

    A natural and important generalization of submodularity—$k$-submodularity—applies to set functions with $k$ arguments and appears in a broad range of applications, such as infrastructure design, machine learning, and healthcare. In this paper, we study maximization problems with $k$-submodular objective functions. We propose valid linear inequalities, namely the $k$-submodular inequalities, for the hypograph of any $k$-submodular … Read more

    Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function and a full Lagrange multiplier update

  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    This paper establishes the iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian (IAPIAL) method for solving linearly constrained smooth nonconvex composite optimization problems which is based on the classical Lagrangian function and, most importantly, performs a full Lagrangian multiplier update, i.e., no shrinking factor is incorporated on it. More specifically, each IAPIAL iteration consists … Read more

    Inverse Mixed Integer Optimization: Polyhedral Insights and Trust Region Methods

  • Merve Bodur
  • Timothy C.Y. Chan
  • Ian Yihang Zhu
    • Categories Integer Programming Tags , , , , ,

    Inverse optimization – determining parameters of an optimization problem that render a given solution optimal – has received increasing attention in recent years. While significant inverse optimization literature exists for convex optimization problems, there have been few advances for discrete problems, despite the ubiquity of applications that fundamentally rely on discrete decision-making. In this paper, … Read more

    Spatially Adaptive Regularization in Image Segmentation

  • Laura Antonelli
  • Valentina De Simone
  • Daniela di Serafino
    • Categories Applications - Science and Engineering, Convex and Nonsmooth Optimization

    We modify the total-variation-regularized image segmentation model proposed by Chan, Esedoglu and Nikolova [SIAM Journal on Applied Mathematics 66, 2006] by introducing local regularization that takes into account spatial image information. We propose some techniques for defining local regularization parameters, based on the cartoon-texture decomposition of the given image, on the mean and median filters, … Read more

    Computational advances in polynomial optimization: RAPOSa, a freely available global solver

  • Julio González-Díaz
  • Joaquín Ossorio-Castillo
  • Brais González-Rodríguez
  • Ángel M. González-Rueda
  • David R. Penas
  • Diego Rodríguez-Martínez
    • Categories Nonlinear Optimization Tags , ,

    In this paper we introduce RAPOSa, a global optimization solver specifically designed for (continuous) polynomial programming problems with box-constrained variables. Written entirely in C++, RAPOSa is based on the Reformulation-Linearization Technique developed by Sherali and Tuncbilek (1992) and subsequently improved in Sherali et al. (2012a), Sherali et al. (2012b) and Dalkiran and Sherali (2013). We … Read more

    Convexifying Multilinear Sets with Cardinality Constraints: Structural Properties, Nested Case and Extensions

  • Rui Chen
  • Sanjeeb Dash
  • Oktay Gunluk
    • Categories 0-1 Programming, Cutting Plane Approaches Tags , ,

    The problem of minimizing a multilinear function of binary variables is a well-studied NP-hard problem. The set of solutions of the standard linearization of this problem is called the multilinear set. We study a cardinality constrained version of it with upper and lower bounds on the number of nonzero variables. We call the set of … Read more

    Strategic Positioning of Empty Containers and Minimising Backhauls in Inland Supply Chain Network

  • Sajini Anand P S
  • Veena Bhat
    • Categories Applications - OR and Management Sciences, Network Optimization, Transportation

    An end-to-end supply chain operation for inland logistics requires coordination and planning among various operations of import pickups, export delivery and empty container positioning for reuse and evacuations of unused containers through the ports. A major business goal of all these operations focuses on reducing the transport costs by utilizing maximum network capacity across active … Read more

    Equilibrium Oil Market Share under the COVID-19 Pandemic

  • Xiaojun Chen
  • Yun Shi
  • Xiaozhou Wang
    • Categories Applications - OR and Management Sciences, Complementarity and Variational Inequalities, Stochastic Programming Tags , , ,

    Equilibrium models for energy markets under uncertain demand and supply have attracted considerable attentions. This paper focuses on modelling crude oil market share under the COVID-19 pandemic using two-stage stochastic equilibrium. We describe the uncertainties in the demand and supply by random variables and provide two types of production decisions (here-and-now and wait-and-see). The here-and-now … Read more

    Branch-and-Bound Solves Random Binary IPs in Polytime

  • Santanu S. Dey
  • Yatharth Dubey
  • Marco Molinaro
    • Categories 0-1 Programming, Branch and Cut Algorithms, Global Optimization Theory Tags ,

    Branch-and-bound is the workhorse of all state-of-the-art mixed integer linear programming (MILP) solvers. These implementations of branch-and-bound typically use variable branching, that is, the child nodes are obtained by fixing some variable to an integer value v in one node and to v + 1 in the other node. Even though modern MILP solvers are … Read more

    A Subspace Acceleration Method for Minimization Involving a Group Sparsity-Inducing Regularizer

  • Frank E. Curtis
  • Daniel P. Robinson
  • Yutong Dai
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , , , , ,

    We consider the problem of minimizing an objective function that is the sum of a convex function and a group sparsity-inducing regularizer. Problems that integrate such regularizers arise in modern machine learning applications, often for the purpose of obtaining models that are easier to interpret and that have higher predictive accuracy. We present a new … Read more