Convexification of classes of mixed-integer sets with L♮-convexity
ArticleDownload View PDF
polyhedral study
Mixed-Integer Programming Approaches to Generalized Submodular Optimization and its Applications
Submodularity is an important concept in integer and combinatorial optimization. A classical submodular set function models the utility of selecting homogenous items from a single ground set, and such selections can be represented by binary variables. In practice, many problem contexts involve choosing heterogenous items from more than one ground set or selecting multiple copies … Read more
The Hamiltonian p-median Problem: Polyhedral Results and Branch-and-Cut Algorithm
In this paper we study the Hamiltonian \(p\)-median problem, in which a weighted graph on \(n\) vertices is to be partitioned into \(p\) simple cycles of minimum total weight. We introduce two new families of valid inequalities for a formulation of the problem in the space of natural edge variables. Each one of the families … Read more
On Constrained Mixed-Integer DR-Submodular Minimization
DR-submodular functions encompass a broad class of functions which are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide … Read more
Strong Inequalities for Chance-Constrained Program
As an essential substructure underlying a large class of chance-constrained programming problems with finite discrete distributions, the mixing set with $0-1$ knapsack has received considerable attentions in recent literature. In this study, we present a family of strong inequalities that subsume existing ones for this set. We also find many other inequalities that can be … Read more