期刊
INFORMS JOURNAL ON COMPUTING
卷 22, 期 1, 页码 108-119出版社
INFORMS
DOI: 10.1287/ijoc.1090.0329
关键词
mixed-integer programming; constraint programming; dominance procedure; nogoods
资金
- University of Padova [CPDA051592]
- Future and Emerging Technologies unit of the EC (IST priority) [FP6-021235-2]
The concept of dominance among nodes of a branch-and-bound tree, although known for a long time, is typically not exploited by general-purpose mixed-integer linear programming (MILP) codes. The starting point of our work was the general-purpose dominance procedure proposed in the 1980s by Fischetti and Toth, where the dominance test at a given node of the branch-and-bound tree consists of the (possibly heuristic) solution of a restricted MILP only involving the fixed variables. Both theoretical and practical issues concerning this procedure are analyzed, and important improvements are proposed. In particular, we use the dominance test not only to fathom the current node of the tree, but also to derive variable configurations called nogoods and, more generally, improving moves. These latter configurations, which we rename pruning moves so as to stress their use in a node-fathoming context, are used during the enumeration to fathom large sets of dominated solutions in a computationally effective way. Computational results on a testbed of MILP instances whose structure is amenable to dominance are reported, showing that the proposed method can lead to a considerable speedup when embedded in a commercial MILP solver.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据