Two-stage distributionally robust noncooperative games: Existence of Nash equilibrium and its application to Cournot-Nash competition

  • Atsushi Hori
  • Nobuo Yamashita
    • Categories Game Theory Tags , , ,

    Two-stage distributionally robust stochastic noncooperative games with continuous decision variables are studied. In such games, each player solves a two-stage distributionally robust optimization problem depending on the decisions of the other players. Existing studies in this area have been limited with strict assumptions, such as linear decision rules, and supposed that each player solves a … Read more

    Worst-Case Analysis of Heuristic Approaches for the Temporal Bin Packing Problem with Fire-Ups

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Approximation Algorithms, Scheduling Tags , , , ,

    We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing … Read more

    Weighted Geometric Mean, Minimum Mediated Set, and Optimal Second-Order Cone Representation

  • Jie Wang
    • Categories Cone Programming, Convex Optimization, Second-Order Cone Programming Tags , , , ,

    We study optimal second-order cone representations for weighted geometric means, which turns out to be closely related to minimum mediated sets. Several lower bounds and upper bounds on the size of optimal second-order cone representations are proved. In the case of bivariate weighted geometric means (equivalently, one dimensional mediated sets), we are able to prove … Read more

    Superadditive duality and convex hulls for mixed-integer conic optimization

  • Akshay Gupte
  • Temitayo Ajayi
  • Amin Khademi
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Nonlinear Programming, Cone Programming, Cutting Plane Approaches Tags , , ,

    We present an infinite family of linear valid inequalities for a mixed-integer conic program, and prove that these inequalities describe the convex hull of the feasible set when this set is bounded and described by integral data. The main element of our proof is to establish a new strong superadditive dual for mixed-integer conic programming … Read more

    Linear-size formulations for connected planar graph partitioning and political districting

  • Jack Zhang
  • Hamidreza Validi
  • Austin Buchanan
  • Illya V. Hicks
    • Categories Combinatorial Optimization, Integer Programming, Network Optimization

    Motivated by applications in political districting, we consider the task of partitioning the n vertices of a planar graph into k connected components. We propose an extended formulation that has two desirable properties: (i) it uses just O(n) variables, constraints, and nonzeros, and (ii) it is perfect. To explore its ability to solve real-world problems, … Read more

    An Efficient Pixel-based Packing Algorithm for Additive Manufacturing Production Planning

  • Hu Kanxin
    • Categories Meta Heuristics, Production and Logistics, Scheduling Tags , , ,

    Additive Manufacturing (AM), the technology of rapid prototyping directly from 3D digital models, has made a significant impact on both academia and industry. When facing the growing demand of AM services, AM production planning (AMPP) plays a vital role in reducing makespan and costs for AM service companies. This research focuses on the AMPP problem … Read more

    D-optimal Data Fusion: Exact and Approximation Algorithms

  • Yongchun Li
  • Marcia Fampa
  • Jon Lee
  • Feng Qiu
  • Weijun Xie
    • Categories Combinatorial Optimization, Integer Programming Tags , , , , , , ,

    We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. … Read more

    A primal-dual majorization-minimization method for large-scale linear programs

  • Xin-Wei Liu
  • Yu-Hong Dai
  • Yakui Huang
    • Categories Linear Programming Tags , , , ,

    We present a primal-dual majorization-minimization method for solving large-scale linear programs. A smooth barrier augmented Lagrangian (SBAL) function with strict convexity for the dual linear program is derived. The majorization-minimization approach is naturally introduced to develop the smoothness and convexity of the SBAL function. Our method only depends on a factorization of the constant matrix … Read more

    The Hyperbolic Augmented Lagrangian Algorithm

  • Lennin Mallma Ramirez
    • Categories Convex Optimization, Nonlinear Optimization

    The hyperbolic augmented Lagrangian algorithm (HALA) is introduced in the area of continuous optimization for solving nonlinear programming problems. Under mild assumptions, such as: convexity, Slater’s qualification and differentiability, the convergence of the proposed algorithm is proved. We also study the duality theory for the case of the hyperbolic augmented Lagrangian function. Finally, in order … Read more

    Large independent sets in Markov random graphs

  • Akshay Gupte
  • Yiran Zhu
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids

    Computing the maximum size of an independent set in a graph is a famously hard combinatorial problem that has been well-studied for various classes of graphs. When it comes to random graphs, only the classical binomial random graph \(G_{n,p}\) has been analysed and shown to have largest independent sets of size \(\Theta(\log{n})\) w.h.p. This classical … Read more