Month: July 2024

Nonlinear Derivative-free Constrained Optimization with a Mixed Penalty-Logarithmic Barrier Approach and Direct Search

  • Andrea Brilli
  • Ana Luisa Custódio
  • Giampaolo Liuzzi
  • Everton Silva
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this work, we propose the joint use of a mixed penalty-logarithmic barrier approach and generating set search, for addressing nonlinearly constrained derivative-free optimization problems. A merit function is considered, wherein the set of inequality constraints is divided into two groups: one treated with a logarithmic barrier approach, and another, along with the equality constraints, … Read more

    Generalized Ellipsoids

  • Abraar Chaudhry
  • Amir Ali Ahmadi
  • Cemil Dibek
    • Categories Convex and Nonsmooth Optimization, Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    \(\) We introduce a family of symmetric convex bodies called generalized ellipsoids of degree \(d\) (GE-\(d\)s), with ellipsoids corresponding to the case of \(d=0\). Generalized ellipsoids (GEs) retain many geometric, algebraic, and algorithmic properties of ellipsoids. We show that the conditions that the parameters of a GE must satisfy can be checked in strongly polynomial … Read more

    Equity-Driven Workload Allocation for Crowdsourced Last-Mile Delivery

  • Abhay Sobhanan
  • Hadi Charkhgard
  • Iman Dayarian
    • Categories Meta Heuristics, Multi-Criteria Optimization, Transportation Tags , , , ,

    Crowdshipping, a rapidly growing approach in Last-Mile Delivery (LMD), relies on independent crowdworkers for delivery orders. Building a sustainable network of crowdshippers is essential for the survival and growth of such systems, while their participation is primarily motivated by fair pay. Additionally, the financial well-being of crowdworkers is sensitive to fair compensation, especially for those … Read more

    Local Convergence Analysis for Nonisolated Solutions to Derivative-Free Methods of Optimization

  • Dat Tran
    • Categories Approximation Algorithms, Nonlinear Optimization, Unconstrained Optimization

    This paper provides a local convergence analysis for newly developed derivative-free methods in problems of smooth nonconvex optimization. We focus here on local convergence to local minimizers, which might be nonisolated and hence more challenging for convergence analysis. The main results provide efficient conditions for local convergence to arbitrary local minimizers under the fulfillment of … Read more

    Compact Mixed Integer Programming Formulations for the Minimum Biclique Cover Problem

  • Bruno Burin
  • Hamidreza Validi
  • Bochuan Lyu
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags , ,

    Given a simple graph G = (V, E) with vertex set V and edge set E, the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover … Read more

    An exact method for a class of robust nonlinear optimization problems

  • Danique de Moor
  • Dick den Hertog
  • Jianzhe Zhen
  • Dimitris Bertsimas
  • Thodoris Koukouvinos
    • Categories Nonlinear Optimization, Robust Optimization Tags , , ,

    We introduce a novel exact approach for addressing a broad spectrum of optimization problems with robust nonlinear constraints. These constraints are defined as sums of products of linear times concave (SLC) functions with respect to the uncertain parameters. Our approach synergizes a cutting set method with reformulation-perspectification techniques and branch and bound. We further extend … Read more

    Block cubic Newton with greedy selection

  • Andrea Cristofari
    • Categories Nonlinear Optimization Tags , , ,

    \(\) A second-order block coordinate descent method is proposed for the unconstrained minimization of an objective function with Lipschitz continuous Hessian. At each iteration, a block of variables is selected by means of a greedy (Gauss-Southwell) rule which considers the amount of first-order stationarity violation, then an approximate minimizer of a cubic model is computed … Read more

    Cluster branching for vehicle routing problems

  • Joao Marcos P Silva
  • Eduardo Uchoa
  • Anand Subramanian
    • Categories Applications - OR and Management Sciences, Combinatorial Optimization, Integer Programming Tags , , ,

    This article introduces Cluster Branching, a novel branching strategy for exact algorithms solving Vehicle Routing Problems (VRPs). While branching is crucial for the efficiency of branch-and-bound-based algorithms, existing branching types such as Edge Branching, CutSet Branching, and Ryan&Foster Branching have their limitations. The proposed branching strategy aggregates multiple edge variables into higher-level decision structures corresponding … Read more

    Interdiction of minimum spanning trees and other matroid bases

  • Noah Weninger
  • Ricardo Fukasawa
    • Categories 0-1 Programming, Dynamic Programming, Graphs and Matroids Tags , , , , , ,

    \(\) In the minimum spanning tree (MST) interdiction problem, we are given a graph \(G=(V,E)\) with edge weights, and want to find some \(X\subseteq E\) satisfying a knapsack constraint such that the MST weight in \((V,E\setminus X)\) is maximized. Since MSTs of \(G\) are the minimum weight bases in the graphic matroid of \(G\), this … Read more

    Integer Programming Approaches for Distributionally Robust Chance Constraints with Adjustable Risks

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

    We study distributionally robust chance-constrained programs (DRCCPs) with individual chance constraints under a Wasserstein ambiguity. The DRCCPs treat the risk tolerances associated with the distributionally robust chance constraints (DRCCs) as decision variables to trade off between the system cost and risk of violations by penalizing the risk tolerances in the objective function. The introduction of … Read more