Integer Programming

Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios

  • Matheus Jun Ota
  • Ricardo Fukasawa
    • Categories Combinatorial Optimization, Integer Programming, Stochastic Programming Tags , ,

    The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similarly to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all these set-partitioning-based approaches have strong assumptions … Read more

    Strategy Investments in Matrix Games

  • Raul Garcia
  • Seyedmohammadhossein Hosseinian
  • Mallesh Pai
  • Andrew J. Schaefer
    • Categories (Mixed) Integer Linear Programming, Game Theory Tags , ,

    We propose an extension of matrix games where the row player may select rows and remove columns, subject to a budget constraint. We present an exact mixed-integer linear programming (MILP) formulation for the problem, provide analytical results concerning its solution, and discuss applications in the security domain. Our computational experiments show heuristic approaches on average … Read more

    Exact and Heuristic Solution Approaches for Busy Time Minimization in Temporal Bin Packing

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Network Optimization Tags , , , ,

    Given a set of jobs (or items), each of which being characterized by its resource demand and its lifespan, and a sufficiently large number of identical servers (or bins), the busy time minimization problem (BTMP) requires to find a feasible schedule (i.e., a jobs-to-servers assignment) having minimum overall power-on time. Although being linked to the … Read more

    Learning Optimal Classification Trees Robust to Distribution Shifts

  • Nathan Justin
  • Sina Aghaei
  • Andrés Gómez
  • Phebe Vayanos
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    We consider the problem of learning classification trees that are robust to distribution shifts between training and testing/deployment data. This problem arises frequently in high stakes settings such as public health and social work where data is often collected using self-reported surveys which are highly sensitive to e.g., the framing of the questions, the time … Read more

    DC programming approach for solving a class of bilevel partial facility interdiction problems

  • Pham Thi Hoai
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags

    We propose a new approach based DC programming for fnding a solution of the partial facility interdiction problem that belongs to the class of bilevel programming. This model was frst considered in the work of Aksen et al. [1] with a heuristic algorithm named multi-start simplex search (MSS). However, because of the big number of … Read more

    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

    Column Generation in Column-and-Constraint Generation for Adjustable Robust Optimization with Interdiction-Type Linking Constraints

  • 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 Zeng and Zhao (2013). While it was empirically shown that the algorithm scales well if all second-stage decisions are continuous, … 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