We propose a very simple preconditioning method for integer programming feasibility problems: replacing the problem b’ ≤ Ax ≤ b, x ∈ Zn with b’ ≤ (AU)y ≤ b, y ∈ Zn, where U is a unimodular matrix computed via basis reduction, to make the … Read more
This paper aims at proposing tractable algorithms to find effectively good solutions to large size chance-constrained combinatorial problems. A new robust model is introduced to deal with uncertainty in mixed-integer linear problems. It is shown to be strongly related to chance-constrained programming when considering pure 0-1 problems. Furthermore, its tractability is highlighted. Then, an optimization … Read more
A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These … Read more
We describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based on only the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation. CitationAppeared in Operations Research Letters. … Read more
The flow set with partial order is a mixed-integer set described by a budget on total flow and a partial order on the arcs that may carry positive flow. This set is a common substructure of resource allocation and scheduling problems with precedence constraints and robust network flow problems under demand/capacity uncertainty. We give a … Read more
We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the … Read more
Lot-sizing problems with inventory bounds and fixed charges have not received much attention in the literature, even though there are many emerging applications in which highly specialized storage is the main activity of interest. The traditional infinite capacity and variable cost assumptions on inventory that have been prevalent in the literature are inappropriate in situations … Read more
A new algorithm for the computation of a piecewise linear function separating two finite point sets in $n$-dimensional space is developed and the algorithm is applied to solve supervised data classification problems. The algorithm computes hyperplanes incrementally and it finds as many hyperplanes as necessary to separate two sets with respect to some tolerance. An … Read more
In one-machine scheduling, MIP time-indexed formulations are often used to provide very good lower bounds through Lagrangian relaxations. In order to get an improved lower bound, we add valid cuts to a time-indexed formulation and show we still have a Lagrangian relaxation that can be solved as a shortest path in a graph. Two branch-and-bound … Read more
Let $S =\{x\in \re^n:\, g_1(x)\geq 0, \cdots, g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is convex, compact and has nonempty interior. Let $S_i =\{x\in \re^n:\, g_i(x)\geq 0\}$, and $\bdS$ (resp. $\bdS_i$) be the boundary of $S$ (resp. $S_i$). This paper, as does the subject of semidefinite programming (SDP), concerns … Read more