We investigate the problem of optimizing a linear objective function over the set of all binary vectors of length n with bounded variation, where the latter is defined as the number of pairs of consecutive entries with different value. This problem arises naturally in many applications, e.g., in unit commitment problems or when discretizing binary … Read more
The establishment of kidney exchange programs has dramatically improved rates for kidney transplants by matching donors to compatible patients who would otherwise fail to receive a kidney for transplant. Rather than simply swapping kidneys between two patient-donor pairs, having multiple patient-donors pairs simultaneously donate kidneys in a cyclic manner enables all participants to receive a … Read more
One of the most fundamental ingredients in mixed-integer nonlinear programming solvers is the well- known McCormick relaxation for a product of two variables x and y over a box-constrained domain. The starting point of this paper is the fact that the convex hull of the graph of xy can be much tighter when computed over … Read more
We derive a closed form description of the convex hull of mixed-integer bilinear covering set with bounds on the integer variables. This convex hull description is determined by considering some orthogonal disjunctive sets defined in a certain way. This description does not introduce any new variables, but consists of exponentially many inequalities. An extended formulation … Read more
Optimization problems face random constraint violations when uncertainty arises in constraint parameters. Effective ways of controlling such violations include risk constraints, e.g., chance constraints and conditional Value-at-Risk (CVaR) constraints. This paper studies these two types of risk constraints when the probability distribution of the uncertain parameters is ambiguous. In particular, we assume that the distributional … Read more
Recently, Buchheim and Klein suggested to study polynomial-time solvable optimisation problems with linear objective functions combined with exactly one additional quadratic monomial. They concentrated on special quadratic spanning tree or forest problems. We extend their results to general matroid optimisation problems with a set of nested monomials in the objective function. The monomials are linearised … Read more
We show that the main results of the expected utility and dual utility theories can be derived in a unified way from two fundamental mathematical ideas: the separation principle of convex analysis, and integral representations of continuous linear functionals from functional analysis. Our analysis reveals the dual character of utility functions. We also derive new … Read more
In recent years, branch-and-cut algorithms have become firmly established as the most effective method for solving generic mixed integer linear programs (MILPs). Methods for automatically generating inequalities valid for the convex hull of solutions to such MILPs are a critical element of branch-and-cut. This paper examines the nature of the so-called separation problem, which is … Read more
Under the deregulated energy market environment, plus the integration of renewable energy generation, both the supply and demand of a power grid system are volatile and under uncertainty. Accordingly, a large amount of spinning reserve is required at each bus to maintain the reliability of the power grid system in the traditional approach. In this … Read more
Let P be a pointed, polyhedral cone in R_n. In this paper, we study the cone C = cone{xx^T: x \in P} of quadratic forms. Understanding the structure of C is important for globally solving NP-hard quadratic programs over P. We establish key characteristics of C and construct a separation algorithm for C provided one … Read more