期刊
COMPUTERS & OPERATIONS RESEARCH
卷 69, 期 -, 页码 25-39出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2015.11.013
关键词
Mixed integer programming; Network flow problems; Total unimodularity; Optimal product pricing; Algorithms
类别
资金
- Tutte Scholarship
- NSERC
- University of Waterloo
We propose improvements to some of the best heuristic algorithms for optimal product pricing problem originally designed by Dobson and Kalish in the late 1980s and in the early 1990s. 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 recent ideas, some from the theoretical computer science literature, for closely related problems. We provide very efficient implementations of the algorithms of Dobson and Kalish as well as our new algorithms. We show that our improvements lead to algorithms which generate solutions with better objective values and that are more robust in overall performance. Our computational experiments indicate that our implementation of Dobson-Kalish heuristics and our new algorithms can provide good solutions for the underlying MIP problems where the typical LP relaxations would have more than a trillion variables and more than three trillion constraints. (C) 2015 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据