0-1 Programming

Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs

  • Manish Bansal
  • Kuo-Ling Huang
  • Sanjay Mehrotra
    • Categories 0-1 Programming, Robust Optimization, Stochastic Programming

    In this paper, we introduce and study a two-stage distributionally robust mixed binary problem (TSDR-MBP) where the random parameters follow the worst-case distribution belonging to an uncertainty set of probability distributions. We present a decomposition algorithm, which utilizes distribution separation procedure and parametric cuts within Benders’ algorithm or L-shaped method, to solve TSDR-MBPs with binary … Read more

    Polytopes Associated with Symmetry Handling

  • Christopher Hojny
  • Marc E. Pfetsch
    • Categories 0-1 Programming Tags , , ,

    This paper investigates a polyhedral approach to handle symmetries in mixed-binary programs. We study symretopes, i.e., the convex hulls of all binary vectors that are lexicographically maximal in their orbit with respect to the symmetry group. These polytopes turn out to be quite complex. For practical use, we therefore develop an integer programming formulation with … Read more

    New Constraints and Features for the University Course Timetabling Problem

  • Sam Applebee
  • Paul Alexandru Bucur
  • Philipp Hungerländer
  • Markus Aschinger
  • Harry Edmonds
  • Kerstin Maier
    • Categories 0-1 Programming, Scheduling

    The university course timetabling problem deals with the task of scheduling lectures of a set of university courses into a given number of rooms and time periods, taking into account various hard and soft constraints. The goal of the International Timetabling Competitions ITC2002 and ITC2007 was to establish models for comparison that cover the most … Read more

    Ambiguous Chance-Constrained Binary Programs under Mean-Covariance Information

  • Ruiwei Jiang
  • Siqian Shen
  • Yiling Zhang
    • Categories 0-1 Programming, Second-Order Cone Programming, Stochastic Programming

    We consider chance-constrained binary programs, where each row of the inequalities that involve uncertainty needs to be satis ed probabilistically. Only the information of the mean and covariance matrix is available, and we solve distributionally robust chance-constrained binary programs (DCBP). Using two different ambiguity sets, we equivalently reformulate the DCBPs as 0-1 second-order cone (SOC) programs. … Read more

    Improving the Randomization Step in Feasibility Pump

  • Santanu S. Dey
  • Andres Iroume
  • Marco Molinaro
  • Domenico Salvagnin
    • Categories 0-1 Programming, Stochastic Programming Tags , , ,

    Feasibility pump (FP) is a successful primal heuristic for mixed-integer linear programs (MILP). The algorithm consists of three main components: rounding fractional solution to a mixed-integer one, projection of infeasible solutions to the LP relaxation, and a randomization step used when the algorithm stalls. While many generalizations and improvements to the original Feasibility Pump have … Read more

    Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators

  • Yu Hin (Gary) Au
  • Levent Tunçel
    • Categories 0-1 Programming, Convex Optimization, Semi-definite Programming Tags , , , , , ,

    We consider operators acting on convex subsets of the unit hypercube. These operators are used in constructing convex relaxations of combinatorial optimization problems presented as a 0,1 integer programming problem or a 0,1 polynomial optimization problem. Our focus is mostly on operators that, when expressed as a lift-and-project operator, involve the use of semidefiniteness constraints … Read more

    On the Existence of Ideal Solutions in Multi-objective 0-1 Integer Programs

  • Natashia Boland
  • Hadi Charkhgard
  • Martin Savelsbergh
    • Categories 0-1 Programming, Multi-Criteria Optimization Tags , , ,

    We study conditions under which the objective functions of a multi-objective 0-1 integer linear program guarantee the existence of an ideal point, meaning the existence of a feasible solution that simultaneously minimizes all objectives. In addition, we study the complexity of recognizing whether a set of objective functions satisfies these conditions: we show that it … Read more

    Exact Approaches for the Knapsack Problem with Setups

  • Fabio Furini
  • Michele Monaci
  • Emiliano Traversi
    • Categories 0-1 Programming, Integer Programming Tags , , , ,

    We consider a generalization of the knapsack problem in which items are partitioned into classes, each characterized by a fixed cost and capacity. We study three alternative Integer Linear Programming formulations. For each formulation, we design an efficient algorithm to compute the linear programming relaxation (one of which is based on Column Generation techniques). We … Read more

    Improved dynamic programming and approximation results for the knapsack problem with setups

  • Ulrich Pferschy
  • Rosario Scatamacchia
    • Categories 0-1 Programming, Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We consider the 0-1 Knapsack Problem with Setups (KPS). Items are grouped into families and if any items of a family are packed, this induces a setup cost as well as a setup resource consumption. We introduce a new dynamic programming algorithm which performs much better than a previous dynamic program and turns out to … Read more

    Tight cycle relaxations for the cut polytope

  • Carla Michini
    • Categories 0-1 Programming, Combinatorial Optimization, Polyhedra Tags , , , , ,

    We study the problem of optimizing an arbitrary weight function w’z over the metric polytope of a graph G=(V,E), a well-known relaxation of the cut polytope. We define the signed graph (G, E^-), where E^- consists of the edges of G having negative weight. We characterize the sign patterns of the weight vector w such … Read more