In this paper, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to … Read more
Extending the concept of time-space networks, layered graphs associate information about one or multiple resource state values with nodes and arcs. While integer programming formulations based on them allow to model complex problems comparably easy, their large size makes them hard to solve for non-trivial instances. We detail and classify layered graph modeling techniques that … Read more
We consider generalizations of parity polytopes whose variables, in addition to a parity constraint, satisfy certain ordering constraints. More precisely, the variable domain is partitioned into k contiguous groups, and within each group, we require the variables to be sorted nonincreasingly. Such constraints are used to break symmetry after replacing an integer variable by a … Read more
The application of decision diagrams in combinatorial optimization has proliferated in the last decade. In recent years, authors have begun to investigate how to utilize not one, but a set of diagrams, to model constraints and objective function terms. Optimizing over a collection of decision diagrams, the problem we refer to as the consistent path … Read more
The fast-growing carsharing and ride-hailing businesses are generating economic benefits and societal impacts in the modern society. However, both have limitation to cover demand from diverse populations, e.g., travelers in low-income, underserved communities. In this paper, we consider two types of travelers: Type~1 who rent shared cars and Type~2 who need shared rides. We propose … Read more
We investigate the NP-hard problem of computing the spark of a matrix (i.e., the smallest number of linearly dependent columns), a key parameter in compressed sensing and sparse signal recovery. To that end, we identify polynomially solvable special cases, gather upper and lower bounding procedures, and propose several exact (mixed-)integer programming models and linear programming … Read more
We investigate new convex relaxations for the pooling problem, a classic nonconvex production planning problem in which input materials are mixed in intermediate pools, with the outputs of these pools further mixed to make output products meeting given attribute percentage requirements. Our relaxations are derived by considering a set which arises from the formulation by … Read more
As an alternative to traditional integer programming (IP), decision diagrams (DDs) provide a new solution technology for discrete problems based on their combinatorial structure and dynamic programming representation. While the literature mainly focuses on the competitive aspects of DDs as a stand-alone solver, we investigate their complementary role by studying IP techniques that can be … Read more
This paper studies the Hamiltonian p-median problem defined on a directed graph, which consists of finding p mutually disjoint circuits of minimum total cost, such that each node of the graph is included in one of the circuits. Earlier formulations are based on viewing the problem as one resulting from the intersection of two subproblems. … Read more
We investigate how the numerical properties of the LP relaxations evolve throughout the solution procedure in a solver employing the branch-and-cut algorithm. The long-term goal of this work is to determine whether the effect on the numerical conditioning of the LP relaxations resulting from the branching and cutting operations can be effectively predicted and whether … Read more