Integer Programming

Mixed-Integer Bilevel Optimization with Nonconvex Quadratic Lower-Level Problems: Complexity and a Solution Method

  • Immanuel M. Bomze
  • Martin Schmidt
  • Horländer Andreas
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , ,

    We study bilevel problems with a convex quadratic mixed-integer upper-level, integer linking variables, and a nonconvex quadratic, purely continuous lower-level problem. We prove $\Sigma_p^2$-hardness of this class of problems, derive an iterative lower- and upper-bounding scheme, and show its finiteness and correctness in the sense that it computes globally optimal points or proves infeasibility of … Read more

    On parametric formulations for the Asymmetric Traveling Salesman Problem

  • Gustavo Angulo
  • Diego Moran Ramirez
    • Categories (Mixed) Integer Linear Programming, Linear Programming, Polyhedra

    The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ), Desrochers-Laporte (DL) and Single Commodity Flow (SCF) formulations. We argue that the choice of some parameters of these formulations is arbitrary and, therefore, there are families of formulations … Read more

    An Efficient Algorithm to the Integrated Shift and Task Scheduling Problem

  • G S R Murthy
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Scheduling Tags , , , , ,

    Abstract   This paper deals with operational models for integrated shift and task scheduling problem. Staff scheduling problem is a special case of this with staff requirements as given input to the problem. Both problems become hard to solve when the problems are considered with flexible shifts. Current literature on these problems leaves good scope … Read more

    Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data

  • Berkay Becu
  • Santanu S. Dey
  • Feng Qiu
  • Alinson S. Xavier
    • Categories (Mixed) Integer Linear Programming

    Many operations related optimization problems involve repeatedly solving similar mixed integer linear programming (MILP) instances with the same constraint matrix but differing objective coefficients and right-hand-side values. The goal of this paper is to generate good cutting-planes for such instances using historical data. Gomory mixed integer cuts (GMIC) for a general MILP can be parameterized … Read more

    Closest Assignment Constraints for Hub Disruption Problems

  • Saikat Mukherjee
  • Prasanna Ramamoorthy
    • Categories Integer Programming Tags , , ,

    Supply chains and logistics can be well represented with hub networks. Operations of these hubs can be disrupted due to unanticipated occurrences or attacks. This study includes Closest assignment Constraints related to hub disruption problems, which can be used in single-level reformulation of the bilevel model. In this study, We propose new sets of constraints … Read more

    A Branch-and-Price-and-Cut Algorithm for Discrete Network Design Problems Under Traffic Equilibrium

  • David
  • Michael Levin
    • Categories (Mixed) Integer Nonlinear Programming, Bilevel Optimization, Transportation Tags , , , ,

    This study addresses discrete network design problems under traffic equilibrium conditions or DNDPs. Given a network and a budget, DNDPs aim to model all-or-nothing decisions such as link addition to minimize network congestion effects. Congestion is measured using traffic equilibrium theory where link travel times are modeled as convex flow-dependent functions and where users make … Read more

    An analytical lower bound for a class of minimizing quadratic integer optimization problems

  • Christian Schmitt
  • Bismark Singh
    • Categories Combinatorial Optimization, Integer Programming, Quadratic Programming Tags , , ,

    Lower bounds on minimization problems are essential for convergence of both branching-based and iterative solution methods for optimization problems. They are also required for evaluating the quality of feasible solutions by providing conservative optimality gaps. We provide an analytical lower bound for a class of quadratic optimization problems with binary decision variables. In contrast to … Read more

    Accelerating Benders decomposition for solving a sequence of sample average approximation replications

  • Harshit Kothari
  • James R. Luedtke
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Stochastic Programming

    Sample average approximation (SAA) is a technique for obtaining approximate solutions to stochastic programs that uses the average from a random sample to approximate the expected value that is being optimized. Since the outcome from solving an SAA is random, statistical estimates on the optimal value of the true problem can be obtained by solving … Read more

    Sparse Principal Component Analysis with Non-Oblivious Adversarial Perturbations

  • Yuqing He
  • Guanyi Wang
  • Yu Yang
    • Categories (Mixed) Integer Nonlinear Programming Tags , ,

    Sparse Principal Component Analysis (sparse PCA) is a fundamental dimension-reduction tool that enhances interpretability in various high-dimensional settings. An important variant of sparse PCA studies the scenario when samples are adversarially perturbed. Notably, most existing statistical studies on this variant focus on recovering the ground truth and verifying the robustness of classical algorithms when the … Read more

    Single-Scenario Facet Preservation for Stochastic Mixed-Integer Programs

  • Aysenur Karagoz
    • Categories Integer Programming, Polyhedra, Stochastic Programming Tags , , ,

    We consider improving the polyhedral representation of the extensive form of a stochastic mixed-integer program (SMIP). Given a facet for a single-scenario version of an SMIP, our main result provides necessary and sufficient conditions under which this inequality remains facet-defining for the extensive form. We then present several implications, which show that common recourse structures … Read more