Integer Programming

Mean–variance portfolio optimization with shrinkage estimation for recommender systems

  • Yuichi Takano
    • Categories Integer Programming, Optimization in Data Science Tags , , , ,

    This paper is concerned with a mean-variance portfolio optimization model with cardinality constraint for generating high-quality lists of recommendations. It is usually difficult to accurately estimate the rating covariance matrix required for mean-variance portfolio optimization because of a shortage of observed user ratings. To improve the accuracy of covariance matrix estimation, we apply shrinkage estimation … Read more

    Solving the Traveling Telescope Problem with Mixed Integer Linear Programming

  • Velibor Mišić
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Integer Programming

    The size and complexity of modern astronomical surveys has grown to the point where, in many cases, traditional human scheduling of observations is tedious at best and impractical at worst. Automated scheduling algorithms present an opportunity to save human effort and increase scientific productivity. A common scheduling challenge involves determining the optimal ordering of a … Read more

    An enhanced mathematical model for optimal simultaneous preventive maintenance scheduling and workshop planning

  • Gabrijela Obradović
  • Ann-Brith Strömberg
    • Categories (Mixed) Integer Linear Programming, Multi-Criteria Optimization, Scheduling

    For a system to stay operational, maintenance of its components is required and to maximize the operational readiness of a system, preventive maintenance planning is essential. There are two stakeholders—a system operator and a maintenance workshop—and a contract regulating their joint activities. Each contract leads to a bi-objective optimization problem. Components that require maintenance are … Read more

    Using Column Generation in Column-and-Constraint Generation for Adjustable Robust Optimization

  • Henri Lefebvre
  • Martin Schmidt
  • Johannes Thürauf
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    Adjustable robust optimization (ARO) is a powerful tool to model problems that have uncertain data and that feature a two-stage decision making process. Computationally, they are often addressed using the column-and-constraint generation (CCG) algorithm introduced by Zhao and Zeng in 2012. While it was empirically shown that the algorithm scales well if all second-stage decisions … Read more

    On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity Constraints

  • Immanuel M. Bomze
  • Bo Peng
  • Yuzhou Qiu
  • E. Alper Yildirim
    • Categories (Mixed) Integer Nonlinear Programming, Quadratic Programming, Semi-definite Programming Tags , , , ,

    Standard quadratic optimization problems (StQPs) provide a versatile modelling tool in various applications. In this paper, we consider StQPs with a hard sparsity constraint, referred to as sparse StQPs. We focus on various tractable convex relaxations of sparse StQPs arising from a mixed-binary quadratic formulation, namely, the linear optimization relaxation given by the reformulation-linearization technique, … Read more

    Strengthened MIP Formulations for the Liver Region Redesign Models of Akshat et al.

  • Aysenur Karagoz
  • Ruofeng Liu
  • Hamidreza Validi
  • Andrew J. Schaefer
    • Categories Integer Programming

    Liver transplantation has been a critical issue in the U.S. healthcare system for decades, and the region redesign aims to ameliorate this issue. This paper revisits two mixed integer programming (MIP) formulations of the liver region redesign problem proposed by Akshat et al. We study their first formulation considering two different modeling approaches: one compact … Read more

    A Computational Study for Piecewise Linear Relaxations of Mixed-Integer Nonlinear Programs

  • Kristin Braun
  • Robert Burlacu
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    Solving mixed-integer nonlinear problems by means of piecewise linear relaxations can be a reasonable alternative to the commonly used spatial branch-and-bound. These relaxations have been modeled by various mixed-integer models in recent decades. The idea is to exploit the availability of mature solvers for mixed-integer problems. In this work, we compare different reformulations in terms … Read more

    Solving Hard Bi-objective Knapsack Problems Using Deep Reinforcement Learning

  • Sasan Mahmoudinazlou
  • Hadi Charkhgard
  • Ali Eshragh
    • Categories Approximation Algorithms, Integer Programming Tags , , ,

    We study a class of bi-objective integer programs known as bi-objective knapsack problems (BOKPs). Our research focuses on the development of innovative exact and approximate solution methods for BOKPs by synergizing algorithmic concepts from two distinct domains: multi-objective integer programming and (deep) reinforcement learning. While novel reinforcement learning techniques have been applied successfully to single-objective … Read more

    A novel Pareto-optimal cut selection strategy for Benders Decomposition

  • Lukas Glomb
  • Frauke Liers
  • Florian Rösel
    • Categories (Mixed) Integer Linear Programming Tags ,

    Decomposition approaches can be used to generate practically efficient solution algorithms for a wide class of optimization problems. For instance, scenario-expanded two-stage stochastic optimization problems can be solved efficiently in practice using Benders Decomposition. The performance of the approach can be influenced by the choice of the cuts that are added during the course of … Read more

    An Integer Programming Approach To Subspace Clustering With Missing Data

  • Akhilesh Soni
  • Jeff Linderoth
  • James R. Luedtke
  • Daniel Pimentel-Alarcon
    • Categories Data Science Algorithms, Integer Programming Tags , ,

    In the Subspace Clustering with Missing Data (SCMD) problem, we are given a collection of n partially observed d-dimensional vectors. The data points are assumed to be concentrated near a union of low-dimensional subspaces. The goal of SCMD is to cluster the vectors according to their subspace membership and recover the underlying basis, which can … Read more