0-1 Programming

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

    Numerically safe lower bounds for the Capacitated Vehicle Routing Problem

  • Ricardo Fukasawa
  • Laurent Poirrier
    • Categories 0-1 Programming Tags , ,

    The resolution of integer programming problems is typically performed via branch-and-bound. Nodes of the branch-and-bound tree are pruned whenever the corresponding subproblem is proven not to contain a solution better than the best solution found so far. This is a key ingredient for achieving reasonable solution times. However, since subproblems are solved in floating-point arithmetic, … Read more

    Exact Algorithms for the Chance-Constrained Vehicle Routing Problem

  • Thai Dinh
  • Ricardo Fukasawa
  • James R. Luedtke
    • Categories 0-1 Programming, Stochastic Programming, Transportation Tags , ,

    We study the chance-constrained vehicle routing problem (CCVRP), a version of the vehicle routing problem (VRP) with stochastic demands, where a limit is imposed on the probability that each vehicle’s capacity is exceeded. A distinguishing feature of our proposed methodologies is that they allow correlation between random demands, whereas nearly all existing exact methods for … Read more

    Integrating cut-and-solve and semi-Lagrangean based dual ascent for the single-source capacitated facility location problem

  • Sune Lauth Gadegaard
    • Categories 0-1 Programming

    This paper describes how the cut-and-solve framework and semi-Lagrangean based dual ascent algorithms can be integrated in two natural ways in order to solve the single source capacitated facility location problem. The first uses the cut-and-solve framework both as a heuristic and as an exact solver for the semi-Lagrangean subproblems. The other uses a semi-Lagrangean … Read more