Airline recovery presents very large and difficult problems requiring high quality solutions within very short time limits. To improve computational performance, the complete airline recovery problem is generally formulated as a series of sequential stages. While the sequential approach greatly simplifies the complete recovery problem, there is no guarantee of global optimality or solution quality. … Read more
Many optimal decision problems in scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the quality of the final design or plan. These decision problems lead to mixed-integer nonlinear programming (MINLP) problems that combine the combinatorial difficulty of optimizing over discrete variable sets with the challenges of handling … Read more
In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements … Read more
The industrial treatment of waste paper in order to regain valuable fibers from which recovered paper can be produced, involves several steps of preparation. One important step is the separation of stickies that are normally attached to the paper. If not properly separated, remaining stickies reduce the quality of the recovered paper or even disrupt … Read more
We propose improvements to some of the best heuristic algorithms for optimal product pricing problem originally designed by Dobson and Kalish in the late 1980’s and in the early 1990’s. Our improvements are based on a detailed study of a fundamental decoupling structure of the underlying mixed integer programming (MIP) problem and on incorporating more … Read more
Split cuts are among the most important and well-understood cuts for general mixed-integer programs. In this paper we consider some recent generalizations of split cuts and compare their relative strength. More precisely, we compare the elementary closures of {split}, {cross}, {crooked cross} and general {multi-branch split cuts} as well as cuts obtained from multi-row and … Read more
The open-pit mine production scheduling problem has received a great deal of attention in recent years, both in the academic literature, and in the mining industry. Optimization approaches to strategic planning for mine exploitation have become the industry standard. However most of these approaches focus on extraction sequencing, and don’t consider the material flow after … Read more
Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using … Read more
The past decade has seen advances in general methods for symmetry breaking in mixed-integer linear programming. These methods are advantageous for general problems with general symmetry groups. Some important classes of MILP problems, such as bin packing and graph coloring, contain highly structured symmetry groups. This observation has motivated the development of problem-specific techniques. In … Read more
We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem. Article Download View Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. II. The Unimodular Two-Dimensional Case