We investigate a multi-stage version of the selection problem where the variation between solutions in consecutive stages is either penalized in the objective function or bounded by hard constraints. While the former problem turns out to be tractable, the complexity of the latter problem depends on the type of bounds imposed: When bounding the number … Read more
The recent interest in contextual optimization problems, where randomness is associated with side information, has led to two primary strategies for formulation and solution. The first, estimate-then-optimize, separates the estimation of the problem’s parameters from the optimization process. The second, decision-focused optimization, integrates the optimization problem’s structure directly into the prediction procedure. In this work, … Read more
We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lovász–Schrijver SDP operator \( \text{LS}_+ \) applied to the fractional stable set polytope. In particular, we show that for every positive integer \( \ell \), the smallest possible graph with \( \text{LS}_+ \)-rank \( \ell \) contains \( 3\ell … Read more
Given a simple graph G = (V, E) with vertex set V and edge set E, the minimum biclique cover problem seeks to cover all edges of the graph with a minimum number of bicliques (i.e., complete bipartite subgraphs). This paper proposes two compact mixed integer programming (MIP) formulations for solving the minimum biclique cover … Read more
This paper presents a generic reformulation framework for binary integer programs (BIPs) that does not impose additional specifications on the objective function or constraints. To enable this generality, we introduce a set system approximation theory designed to identify the tightest inner and outer approximations for any binary solution space using special types of set systems. … Read more
We consider the problem of identifying the induced star with the largest cardinality open neighborhood in a graph. This problem, also known as the star degree centrality (SDC) problem, has been shown to be 𝒩𝒫-complete. In this work, we first propose a new integer programming (IP) formulation, which has a fewer number of constraints and … Read more
Abstract: We present new valid inequalities for 0-1 programming problems that work in similar ways to well known cover inequalities. Discussion and analysis of these cuts is followed by their revision and use in integer programming as a new generation of cuts that excludes not only portions of polyhedra containing noninteger points, also parts with … Read more
We present new valid inequalities that work in similar ways to well known cover inequalities.The differences exist in three aspects. First difference is in the generation of the inequalities. The method used in generation of the new cuts is more practical in contrast to classical cover inequalities. Second difference is the more general applicability, i.e., … Read more
The basic principle of the cutting plane techniques is to chop away the portions of the solution space of the linear programming relaxation of an integer program that contain no integer solutions. this is true for both Gomory’s cutting planes, and other more recent cuts based on valid inequalities. Obtaining a partial or full description … Read more