binary integer programming

Structural Insights and an IP-based Solution Method for Patient-to-room Assignment Under Consideration of Single Room Entitlements

  • Tabea Brandt
  • Christina Büsing
  • Felix Engelhardt
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Combinatorial Optimization Tags , , ,

    Patient-to-room assignment (PRA) is a scheduling problem in decision support for large hospitals. This work proposes Integer Programming (IP) formulations for dynamic PRA, where either full, limited or uncertain information on incoming patients is available. The applicability is verified through a computational study. Results indicate that large, real world instances can be solved to a … Read more

    An Efficient Linear Programming Based Method for the Influence Maximization Problem in Social Networks

  • Evren Güney
    • Categories 0-1 Programming, Approximation Algorithms, Network Optimization Tags , , ,

    The influence maximization problem (IMP) aims to determine the most influential individuals within a social network. In this study first we develop a binary integer program that approximates the original problem by Monte Carlo sampling. Next, to solve IMP efficiently, we propose a linear programming relaxation based method with a provable worst case bound that … Read more

    Approximating the Stability Region for Binary Mixed-Integer Programs

  • Shabbir Ahmed
  • Fatma Kılınç-Karzan
  • George L. Nemhauser
  • Martin Savelsbergh
  • Alejandro Toriello
    • Categories 0-1 Programming Tags , ,

    We consider optimization problems with some binary variables, where the objective function is linear in these variables. The stability region of a given solution of such a problem is the polyhedral set of objective coefficients for which the solution is optimal. A priori knowledge of this set provides valuable information for sensitivity analysis and re-optimization … Read more