Mathematical Sciences: Investigations in Mixed Integer Programming

点击翻译按钮获取中文摘要

While recent years have seen remarkable progress in programming, both theoretically and practically, most of that progress has come in the solution of pure 0/1 problems. On the other hand, mixed problems, problems with both continuous and discrete variables-- usually 0/1 variables--dominate in practice; moreover, practitioners regularly produce instances of these models that cannot be solved using currently available codes. This combination of success in solving pure 0/1 problems and the existing demand for methods to solve difficult real-world mixed problems has received considerable attention in the research community. Nevertheless, general-purpose mixed-integer solvers remain primarily solvers, and while they often employ rather sophisticated ``heuristic'' devices, they still use few of the algorithmic ideas implicit in recent theoretical developments. This research will attempt to change that situation by developing a research code including both the standard methods that have been successful in practice, as well as incorporating ideas based upon recent theoretical developments. The focus will be on actually solving real-world instances that arise as general mixed integer programs but cannot currently be solved.