Current mixed-integer linear programming solvers are based on linear programming routines that use floating point arithmetic. Occasionally, this leads to wrong solutions, even for problems where all coefficients and all solution components are small integers. It is shown how, using directed rounding and interval arithmetic, cheap pre- and postprocessing of the linear programs arising in … Read more
A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous … Read more
The `Progressive Party Problem’ [smith1995] has long been considered a problem intractable for branch-and-bound mixed integer solvers. Quite impressive results have been reported with constraint programming systems for this problem. As a result the problem has become a standard example in texts on constraint programming. Fortunately, there has been progress in the mixed integer programming … Read more
Attempts at reducing the externalities of freight transport in Europe are generally focused on the incorporation of a more significant use of rail into freight itineraries. One new scenario for increasing the share of rail in intermodal transport involves the development of a dedicated subnetwork of freight rail lines. Within this European Union project, the … Read more
We develop a method for generating valid convex polynomial inequalities for mixed 0-1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities. ArticleDownload View PDF
We present a nontrivial family of facet-defining inequalities for the p-median polytope. We incorporate the inequalities in a branch-and-cut scheme, and we report computational results that demonstrate their effectiveness. CitationDepartment of Industrial Engineering, State University of New York at Buffalo, submittedArticleDownload View PDF
We present a polyhedral study of the complementarity knapsack problem, in which no auxiliary binary variables are introduced, but rather the inequalities are derived in the space of the continuous variables. CitationSchool of Industrial and Systems Engineering, GA Tech, under reviewArticleDownload View PDF
We study the use of binary variables in reformulating general mixed-integer linear programs. We show that binary reformulations result in problems for which almost all the binary variables replacing a general integer variable need to be explored during branching. We also give computational results on the performance of such reformulations in solving the mixed-integer programs, … Read more