We study the generalization of split, k-branch split, and intersection cuts from Mixed Integer Linear Programming to the realm of Mixed Integer Nonlinear Programming. Constructing such cuts requires calculating the convex hull of the difference between a convex set and an open set with a simple geometric structure. We introduce two techniques to give precise … Read more
We consider two linear relaxations of the asymmetric traveling salesman problem (TSP), the Held-Karp relaxation of the TSP’s arc-based formulation, and a particular approximate linear programming (ALP) relaxation obtained by restricting the dual of the TSP’s shortest path formulation. We show that the two formulations produce equal lower bounds for the TSP’s optimal cost regardless … Read more
We present a quadratic outer approximation scheme for solving general convex integer programs, where suitable quadratic approximations are used to underestimate the objective function instead of classical linear approximations. As a resulting surrogate problem we consider the problem of minimizing a function given as the maximum of finitely many convex quadratic functions having the same … Read more
The classical single-band uncertainty model introduced by Bertsimas and Sim has represented a breakthrough in the development of tractable robust counterparts of Linear Programs. However, adopting a single deviation band may be too limitative in practice: in many real-world problems, observed deviations indeed present asymmetric distributions over asymmetric ranges, so that getting a higher modeling … Read more
We consider the augmented Lagrangian dual for integer programming, and provide a primal characterization of the resulting bound. As a corollary, we obtain proof that the augmented Lagrangian is a strong dual for integer programming. We are able to show that the penalty parameter applied to the augmented Lagrangian term may be placed at a … Read more
Financial institutions are currently required to meet more stringent capital requirements than they were before the recent financial crisis; in particular, the capital requirement for a large bank’s trading book under the Basel 2.5 Accord more than doubles that under the Basel II Accord. The significant increase in capital requirements renders it necessary for banks … Read more
We propose a branch-and-bound (BB) algorithm for biobjective mixed-integer linear programs (BOMILPs). Our approach makes no assumption on the type of problem and we prove that it returns all Pareto points of a BOMILP. We discuss two techniques upon which the BB is based: fathoming rules to eliminate those subproblems that are guaranteed not to … Read more
One main objective of research in the area of mixed-integer programming is developing cutting plane techniques to improve the solvability of mixed-integer programs (MIPs). Various cutting plane separators are typically available in MIP solvers. The large number of cutting planes generated by these separators, however, can pose a computational problem. Therefore, a sophisticated cut management … Read more
We report and analyze the results of our computational testing of branch-and-cut for the complementarity-constrained optimization problem (CCOP). Besides the MIP cuts commonly present in commercial optimization software, we used inequalities that explore complementarity constraints. To do so, we generalized two families of cuts proposed earlier by de Farias, Johnson, and Nemhauser that had never … Read more
We consider bounded integer knapsacks where the weights and variable upper bounds together form a superincreasing sequence. The elements of this superincreasing knapsack are exactly those vectors that are lexicographically smaller than the greedy solution to optimizing over this knapsack. We describe the convex hull of this n-dimensional set with O(n) facets. We also establish … Read more