We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem. ArticleDownload View PDF
We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and … Read more
A polynomial-time algorithm for integer factorization, wherein integer factorization is reduced to solution of a convex polynomial-time integer maximization problem. ArticleDownload View PDF
In this paper we present algorithms to approximate the solution for the multiparametric 0-1-mixed integer linear programming problem relative to the objective function. We consider the uncertainty for the parameters that de fine the cost vector corresponding to a subset of 0-1-variables by assuming that each parameter belongs to a known interval. We suppose that we … Read more
We give an algorithm for testing the extremality of minimal valid functions for Gomory and Johnson’s infinite group problem, that are piecewise linear (possibly discontinuous) with rational breakpoints. This is the first set of necessary and sufficient conditions that can be tested algorithmically, for deciding extremality in this important class of minimal valid functions. ArticleDownload … Read more
We study the convex hull of the intersection of a convex set E and a linear disjunction. This intersection is at the core of solution techniques for Mixed Integer Conic Optimization. We prove that if there exists a cone K (resp., a cylinder C) that has the same intersection with the boundary of the disjunction … Read more
We consider a class of linear programs involving a set of covering constraints of which at most k are allowed to be violated. We show that this covering linear program with violation is strongly NP-hard. In order to improve the performance of mixed-integer programming (MIP) based schemes for these problems, we introduce and analyze a … Read more
We present a new method for solving bin packing problems, including two-constraint variants, based on an arc flow formulation with side constraints. Conventional formulations for bin packing problems are usually highly symmetric and provide very weak lower bounds. The arc flow formulation proposed provides a very strong lower bound, and is able to break symmetry … Read more
We study scheduling as a means to address the increasing energy concerns in manufacturing enterprises. In particular, we consider a flow shop scheduling problem with a restriction on peak power consumption, in addition to the traditional time-based objectives. We investigate both mathematical programming and combinatorial approaches to this scheduling problem, and test our approaches with … Read more
Given the steady increase in cores per CPU, it is only a matter of time until supercomputers will have a million or more cores. In this article, we investigate the opportunities and challenges that will arise when trying to utilize this vast computing power to solve a single integer linear optimization problem. We also raise … Read more