Journal: Informs Journal on Computing

Abbreviation

Publisher

INFORMS

Journal Volumes

ISSN

1091-9856
1526-5528

Description

Filters

2015 - 201912020 - 20254
Reset filters

Search Results

Publications 1 - 5 of 5
  • Robust Optimization for Models with Uncertain Second-Order Cone and Semidefinite Programming Constraints
    Item type: Journal Article
    Zhen, Jianzhe; de Ruiter, Frans J.C.T.; Roos, Ernst; et al. (2022)
    Informs Journal on Computing
    In this paper, we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints with an ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem can then (approximately) be solved by using adjustable robust linear optimization techniques. For example, we show that if linear decision rules are used, then the final robust counterpart consists of SOC or SDP constraints, respectively, which have the same computational complexity as the nominal version of the original constraints. We propose an efficient method to obtain good lower bounds. Moreover, we extend our approach to other classes of robust optimization problems, such as nonlinear problems that contain wait-and-see variables, linear problems that contain bilinear uncertainty, and general conic constraints. Numerically, we apply our approach to reformulate the problem on finding the minimum volume circumscribing ellipsoid of a polytope and solve the resulting reformulation with linear and quadratic decision rules as well as Fourier-Motzkin elimination. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it with the state-of-the-art copositive approach. Moreover, we apply the proposed approach to a robust regression problem and a robust sensor network problem and use linear decision rules to solve the resulting adjustable robust linear optimization problems, which solve the problem to (near) optimality. Summary of Contribution: Computing robust solutions for nonlinear optimization problems with uncertain second-order cone and semidefinite programming constraints are of much interest in real-life applications, yet they are in general computationally intractable. This paper proposes a computationally tractable approximation for such problems. Extensive computational experiments on (i) computing the minimum volume circumscribing ellipsoid of a polytope, (ii) robust regressions, and (iii) robust sensor networks are conducted to demonstrate the effectiveness and efficiency of the proposed approach.
  • Spatial Branch-and-Bound for Nonconvex Separable Piecewise Linear Optimization
    Item type: Journal Article
    Hübner, Thomas; Gupte, Akshay; Rebennack, Steffen (2025)
    Informs Journal on Computing
    Nonconvex separable piecewise linear functions (PLFs) frequently appear in applications and to approximate nonlinearitites. The standard practice to formulate nonconvex PLFs is from the perspective of discrete optimization using special ordered sets and mixed-integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm for optimizing a separable discontinuous PLF over a closed convex set. It offers slim and sparse linear programming relaxations, sharpness throughout the search tree, and an increased flexibility in branching decisions. The main feature of our algorithm is the generation of convex underestimators at the root node of the search tree and their quick and efficient updates at each node after branching. Convergence to the global optimum is achieved when the PLFs are lower semicontinuous. A Python implementation of our algorithm is tested on knapsack and network flow problems for both continuous and discontinuous PLFs. Our algorithm is compared with four logarithmic MILP formulations solved by Gurobi's MILP solver as well as Gurobi's PLF solver. We also compare our method against mixed-integer nonlinear program formulations solved by Gurobi. The numerical experiments indicate significant performance gains up to two orders of magnitude for medium-to large-sized PLFs. Finally, we also give an upper bound on the additive error from PLF approximations of nonconvex separable optimization.
  • Disjoint Bilinear Optimization: A Two-Stage Robust Optimization Perspective
    Item type: Journal Article
    Zhen, Jianzhe; Marandi, Ahmadreza; de Moor, Danique; et al. (2022)
    Informs Journal on Computing
    In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, which enables us to apply robust optimization techniques to solve the resulting problems. To this end, a solution scheme based on a blending of three popular robust optimization techniques is proposed. For disjoint bilinear optimization problems with a polyhedral feasible region and a general convex feasible region, we show that, under mild regularity conditions, the convex relaxations of the original bilinear formulation and its two-stage robust reformulation obtained from a reformulation-linearization-based technique and linear decision rules, respectively, are equivalent. For generic bilinear optimization problems, the convex relaxations from the reformulation-linearization-based technique are generally tighter than the one from linear decision rules. Numerical experiments on bimatrix games, synthetic disjoint bilinear problem instances, and convex maximization problems demonstrate the efficiency and effectiveness of the proposed solution scheme.
  • Construction of Value Functions of Integer Programs with Finite Domain
    Item type: Journal Article
    Huang, Yifei; Zhang, Junlong (2025)
    Informs Journal on Computing
    Value functions play a central role in integer programming duality, and they are also used to develop solution methods for stochastic integer programs, bilevel integer programs, and robust optimization problems. In this paper, we propose a column-by-column algorithm for constructing the value functions of integer programs with finite domain over the set of level-set minimal vectors. The proposed algorithm starts with the first column and sequentially adds the rest of the columns one by one. Each time a column is added, a new set of level-set minimal vectors is generated based on the previous set, and the optimal objective values over the level-set minimal vectors are also computed. The advantage of the proposed algorithm is that no integer program needs to be solved in the algorithm for instances with nonnegative constraint matrices. Computational results on benchmark instances show that the proposed algorithm can achieve a speedup of up to three orders of magnitude compared with a state-of-the-art algorithm. We also extend the proposed algorithm to build value functions of integer programs with negative elements in the constraint matrix.
  • Online Checkpointing with Improved Worst-Case Guarantees
    Item type: Journal Article
    Bringmann, Karl; Doerr, Benjamin; Sliacan, Jakub (2015)
    Informs Journal on Computing
Publications 1 - 5 of 5