Inspired by its occurrence as a substructure in a stochastic railway timetabling model, we study in this work a special case of the bipartite boolean quadric polytope. It models conditional relations across three sets of binary variables, where selections within two “if” sets imply a choice in a corresponding “then” set. We call this polytope … Read more
Semi-continuous decision variables arise naturally in many real-world applications. They are defined to take either value zero or any value within a specified range, and occur mainly to prevent small nonzero values in the solution. One particular challenge that can come with semi-continuous variables in practical models is that their upper bound may be large … Read more
We study the value function of an integer program (IP) by characterizing how its optimal value changes as the right-hand side varies. We show that the IP value function can be approximated to any desired degree of accuracy using machine learning (ML) techniques. Since an IP value function is a Chvátal-Gomory (CG) function, we first … Read more
A traditional stochastic program under a finite population typically seeks to optimize efficiency by maximizing the expected profits or minimizing the expected costs, subject to a set of constraints. However, implementing such optimization-based decisions can have varying impacts on individuals, and when assessed using the individuals’ utility functions, these impacts may differ substantially across demographic … Read more
The moment-sum of squares hierarchy by Lasserre has become an established technique for solving polynomial optimization problems. It provides a monotonically increasing series of tight bounds, but has well-known scalability limitations. For structured optimization problems, the term-sparsity SOS (TSSOS) approach scales much better due to block-diagonal matrices, obtained by completing the connected components of adjacency … Read more
Consider the task of dividing a state into k contiguous political districts whose populations must not differ by more than one person, following current practice for congressional districting in the USA. A widely held belief among districting experts is that this task requires at least k-1 county splits. This statement has appeared in expert testimony, … Read more
We propose two new classes of valid inequalities (VIs) for the binary knapsack polytope, based on non-minimal covers. We also show that these VIs can be obtained through neither sequential nor simultaneous lifting of well-known cover inequalities. We further provide conditions under which they are facet-defining. The usefulness of these VIs is demonstrated using computational … Read more
In this paper, we consider a theoretical framework for comparing branch-and-bound with classical lift-and-project hierarchies. We simplify our analysis of streamlining the definition of branch-and-bound. We introduce “skewed $k$-trees” which give a hierarchy of relaxations that is incomparable to that of Sherali-Adams, and we show that it is much better for some instances. We also … Read more
In the Subspace Clustering with Missing Data (SCMD) problem, we are given a collection of n partially observed d-dimensional vectors. The data points are assumed to be concentrated near a union of low-dimensional subspaces. The goal of SCMD is to cluster the vectors according to their subspace membership and recover the underlying basis, which can … Read more
\(\) We consider linear combinatorial optimization problems under uncertain disruptions that increase the cost coefficients of the objective function. A decision-maker, or planner, can invest resources to probe the components (i.e., the coefficients) in order to learn their disruption status. In the proposed probing optimization problem, the planner, knowing just the disruptions’ probabilities, selects which … Read more