We investigate a mixed 0-1 conic quadratic optimization problem with indicator variables arising in mean-risk optimization. The indicator variables are often used to model non-convexities such as fixed charges or cardinality constraints. Observing that the problem reduces to a submodular function minimization for its binary restriction, we derive three classes of strong convex valid inequalities … Read more
This paper deals with a variant of the well-known Cluster Editing Problem (CEP), more precisely, the \textit{p}-CEP, in which a given input graph should be edited by adding and/or removing edges in such a way that \textit{p} vertex-disjoint cliques (clusters) are generated with the minimum number of editions. We introduce several valid inequalities where some … Read more
As the modern transmission control and relay technologies evolve, transmission line switching has become an important option in power system operators’ toolkits to reduce operational cost and improve system reliability. Most recent research has relied on the DC approximation of the power flow model in the optimal transmission switching problem. However, it is known that … Read more
In this article, six different mixed integer programming (MIP) formulations are proposed and analyzed. These formulations are based on the knowledge of four different paradigms for single machine scheduling problems (SMSP) with sequence dependent setup times and release dates. Each formulation reflects a specific concept on how the variables and parameters are defined, requiring particular … Read more
The planning of chemical production often involves the optimization of the size of the tasks to be performed subject to unit capacity constraints, as well as inventory constraints for intermediate materials. While several mixed-integer programming (MIP) models have been proposed that account for these features, the development of tightening methods for these formulations has received … Read more
In this paper we study valid inequalities for a fundamental set that involves a continuous vector variable x in [0,1]^n, its associated quadratic form x x’ and its binary indicators. This structure appears when deriving strong relaxations for mixed integer quadratic programs (MIQPs). We treat valid inequalities for this set as lifted from QPB, which … Read more
In this paper we deal with the critical node problem, where a given number of nodes has to be removed from an undirected graph in order to maximize the disconnections between the node pairs of the graph. We propose an integer linear programming model with a non-polynomial number of constraints but whose linear relaxation can … Read more
This paper surveys results on the NP-hard mixed-integer quadratically constrained programming problem. The focus is strong convex relaxations and valid inequalities, which can become the basis of efficient global techniques. In particular, we discuss relaxations and inequalities arising from the algebraic description of the problem as well as from dynamic procedures based on disjunctive programming. … Read more
In recent years there has been growing interest in generating valid inequalities for mixed-integer programs using sets with 2 or more constraints. In particular, Andersen et.al (2007) and Borozan and Cornue’jols (2007) study sets defined by equations that contain exactly one integer variable per row. The integer variables are not restricted in sign. Cutting planes … 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