We prove several inequalities on the determinants of sublattices in LLL-reduced bases. They generalize the fundamental inequalities of Lenstra, Lenstra, and Lovasz on the length of the shortest vector, and show that LLL-reduction finds not only a short vector, but also sublattices with small determinants. We also prove new inequalities on the product of the … Read more
Given a finite ground set N and a value vector a in R^N, we consider optimization problems involving maximization of a submodular set utility function of the form h(S)= f (sum_{i in S} a_i), S subseteq N, where f is a strictly concave, increasing, differentiable function. This function appears frequently in combinatorial optimization problems when … Read more
The value function of a mixed-integer linear program (MILP) is a function that returns the optimal solution value as a function of the right-hand side. In this paper, we analyze the structure of the value function of a MILP with a single constraint. We show that the value function is uniquely determined by a finite … Read more
The Single Row Facility Layout Problem (SRFLP) is the problem of arranging facilities of given lengths on a line, while minimizing a weighted sum of the distances between all pairs of facilities. The SRFLP is strongly NP-hard and includes the well-known linear arrangement problem as a special case. We perform the first ever polyhedral study … Read more
We propose a solution method for a water-network optimization problem using a nonconvex continuous NLP (nonlinear programming) relaxation and a MINLP (mixed integer nonlinear programming) search. Our approach employs a relatively simple and accurate model that pays some attention to the requirements of the solvers that we employ. Our view is that in doing so, … Read more
This paper addresses the problem of generating strong convex relaxations of Mixed Integer Quadratically Constrained Programming (MIQCP) problems. MIQCP problems are very difficult because they combine two kinds of non-convexities: integer variables and non-convex quadratic constraints. To produce strong relaxations of MIQCP problems, we use techniques from disjunctive programming and the lift-and-project methodology. In particular, … Read more
This paper introduces disjunctive decomposition for two-stage mixed 0-1 stochastic integer programs (SIPs) with random recourse. Disjunctive decomposition allows for cutting planes based on disjunctive programming to be generated for each scenario subproblem under a temporal decomposition setting of the SIP problem. A new class of valid inequalities for mixed 0-1 SIP with random recourse … Read more
Given a 0-1 integer programming problem, several authors have introduced sequential relaxation techniques — based on linear and/or semidefinite programming — that generate the convex hull of integer points in at most $n$ steps. In this paper, we introduce a sequential relaxation technique, which is based on $p$-order cone programming ($1 \le p \le \infty$). … Read more
In this work, we consider a classification problem where the objects to be classified are bags of instances which are vectors measuring d different attributes. The classification rule is defined in terms of a ball, whose center and radius are the parameters to be computed. Given a bag, it is assigned to the positive class … Read more
Systems of polynomial equations over an algebraically-closed field K can be used to concisely model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable, hamiltonian, etc.) if and only if a related system of polynomial equations has a solution over K. In this paper, we investigate an algorithm … Read more