A vast number of causal inference studies use matching techniques, where treatment cases are matched with similar control cases. For observational data in particular, we claim there is a major source of uncertainty that is essentially ignored in these tests, which is the way the assignments of matched pairs are constructed. It is entirely possible, … Read more
It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. In fact, the USA Energy Policy Act of 2005 (Section 1223) states that the U.S. should “encourage, as appropriate, the deployment of advanced transmission technologies” including “optimized transmission line configurations”. As such, … Read more
In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we first focus on binary Steiner trees in which all node degrees are required to be at most three. We then present results for general degree-constrained Steiner trees. It is shown that finding a binary Steiner … Read more
We study the Lov\'{a}sz-Schrijver lift-and-project operator ($\LS_+$) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the $\LS_+$-operator generates the stable set polytope in one step has been open since 1990. We call these graphs … Read more
In this paper, we propose a generic branch-and -cut algorithm for a special class of bi-level combinatorial optimization problems. Namely, we study such problems that can be reformulated as bilinear min-max combinatorial optimization problems. We show that the reformulation can be efficiently solved by a branch-and-cut algorithm whose cuts represent the inner maximization feasibility set. … Read more
Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most once. If the costs induce negative cycles on G, the problem is NP-hard. In this … Read more
Motivated by concave cost combinatorial optimization problems, we study the following mixed integer nonlinear set: P = {(w,x) : w >= f(a’x), e’x
When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more
In this paper we present a mathematical programming approach to tighten a Big-$M$ formulation ($P_M$) of a Mixed Integer Problem with Logical Implications ($P$). If $M_0$ is a valid vector (the optimal solutions of $P$ belong to the feasible solutions set of $P_{M_0}$) our procedures find a valid vector $M$ such that $M \leq M_0$. … Read more
We propose a feasible active set method for convex quadratic programming problems with non-negativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara and Lodi to the presence … Read more