Applications – Science and Engineering

Locally Ideal Formulations for Piecewise Linear Functions with Indicator Variables

  • Jeff Linderoth
  • James R. Luedtke
  • Srikrishna Sridhar
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering

    In this paper, we consider mixed integer linear programming (MIP) formulations for piecewise linear functions (PLFs) that are evaluated when an indicator variable is turned on. We describe modifications to standard MIP formulations for PLFs with desirable theoretical properties and superior computational performance in this context. Citation Technical Report #1788, Computer Sciences Department, University of … Read more

    Maxwell-Boltzmann and Bose-Einstein Distributions for the SAT Problem

  • Claudio Angione
  • Giuseppe Nicosia
  • Annalisa Occhipinti
    • Categories Applications - Science and Engineering, Combinatorial Optimization Tags , , ,

    Recent studies in theoretical computer science have exploited new algorithms and methodologies based on statistical physics for investigating the structure and the properties of the Satisfiability problem. We propose a characterization of the SAT problem as a physical system, using both quantum and classical statistical-physical models. We associate a graph to a SAT instance and … Read more

    Trace-Penalty Minimization for Large-scale Eigenspace Computation

  • Xin Liu
  • Zaiwen Wen
  • Yin Zhang
  • Chao Yang
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Parallel Algorithms Tags , ,

    The Rayleigh-Ritz (RR) procedure, including orthogonalization, constitutes a major bottleneck in computing relatively high dimensional eigenspaces of large sparse matrices. Although operations involved in RR steps can be parallelized to a certain level, their parallel scalability, which is limited by some inherent sequential steps, is lower than dense matrix-matrix multiplications. The primary motivation of this … Read more

    Optimal Power Grid Protection through A Defender-Attacker-Defender Model

  • Wei Yuan
  • Bo Zeng
  • Long Zhao
    • Categories Applications - Science and Engineering, Game Theory

    Power grid vulnerability is a major concern of modern society, and its protection problem is often formulated as a tri-level defender-attacker-defender model. However, this tri-level problem is compu- tationally challenging. In this paper, we design and implement a Column-and-Constraint Generation algorithm to derive its optimal solutions. Numerical results on an IEEE system show that: (i) … Read more

    Principle of optimal accuracy classification for metrological purposes

  • David Kisets
    • Categories Applications - Science and Engineering, Other Topics

    The conceptions of optimizing a quantitative classification hierarchy and the criterion of informational optimality have been used for modeling universal accuracy classification scale. Proposed model is based on test uncertainty ratios determined in conformity with optimal levels of confidence in evaluating measurement uncertainty, as well as on the optimal classification structure. The author believes that … Read more

    Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization

  • Nicolas Gillis
  • Robert Luce
    • Categories Data-Mining, Linear Programming Tags , , , , ,

    Nonnegative matrix factorization (NMF) has been shown recently to be tractable under the separability assumption, under which all the columns of the input data matrix belong to the convex cone generated by only a few of these columns. Bittorf, Recht, R\’e and Tropp (`Factoring nonnegative matrices with linear programs’, NIPS 2012) proposed a linear programming … Read more

    Gamma-Robust Facility Relocation Problem

  • Gino J. Lim
  • Ayse Sonmez
    • Categories Facility Planning and Design, Network Optimization, Robust Optimization Tags , ,

    In this paper, we consider relocating facilities, where we have demand changes in the network. Relocations are performed by closing some of the existing facilities from low demand areas and opening new ones in newly emerging areas. However, the actual changes of demand are not known in advance. Therefore, di erent scenarios with known probabilities are … Read more

    Public Facility Location Using Dispersion, Population, and Equity Criteria

  • Rajan Batta
  • Miguel A. Lejeune
  • Srinivas Prasad
    • Categories Facility Planning and Design, Production and Logistics Tags , ,

    Administrators/Decision Makers (DMs) responsible for making locational decisions for public facilities have many other overriding factors to consider that dominate traditional OR/MS objectives that relate to response time. We propose that an appropriate role for the OR/MS analyst is to help the DMs identify a good set of solutions rather than an optimal solution that … Read more

    Incremental Network Design with Shortest Paths

  • Matthew Baxter
  • Andreas T. Ernst
  • Thomas Kalinowski
  • Martin Savelsbergh
  • Tarek Elgindy
    • Categories Approximation Algorithms, Multidisciplinary Design Optimization, Network Optimization Tags , , ,

    We introduce a class of incremental network design problems focused on investigating the optimal choice and timing of network expansions. We concentrate on an incremental network design problem with shortest paths. We investigate structural properties of optimal solutions, we show that the simplest variant is NP-hard, we analyze the worst-case performance of natural greedy heuristics, … Read more

    ALGORITHM & DOCUMENTATION: MINRES-QLP for Singular Symmetric and Hermitian Linear Equations and Least-Squares Problems

  • Sou-Cheng Choi
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Optimization Software and Modeling Systems Tags , , , , , , , , ,

    We describe algorithm MINRES-QLP and its FORTRAN 90 implementation for solving symmetric or Hermitian linear systems or least-squares problems. If the system is singular, MINRES-QLP computes the unique minimum-length solution (also known as the pseudoinverse solution), which generally eludes MINRES. In all cases, it overcomes a potential instability in the original MINRES algorithm. A positive-definite … Read more