We address the solution of Mixed Integer Linear Programming (MILP) models with strong relaxations that are derived from Dantzig-Wolfe decompositions and allow a pseudo-polynomial pricing algorithm. We exploit their network-flow characterization and provide a framework based on column generation, reduced-cost variable-fixing, and a highly asymmetric branching scheme that allows us to take advantage of the potential of the current MILP solvers. We apply our framework to a variety of cutting and packing problems from the literature. The efficiency of the framework is proved by extensive computational experiments, in which a significant number of open instances could be solved to proven optimality for the first time.


翻译:我们处理混合整形线性规划模型(MILP)的解决方案,这些模型来自丹兹格-沃尔菲分解法,具有很强的放松作用,并允许假球定价算法。 我们利用这些模型的网络流量特征,并提供一个基于柱子生成、降低成本的可变固定和高度不对称的分支计划的框架,使我们能够利用目前的MILP解答器的潜力。 我们将我们的框架应用于文献中的各种切割和包装问题。 框架的效率通过广泛的计算实验得到了证明,其中大量公开的事例可以首次被证明是最佳的。

0
下载
关闭预览

相关内容

iOS 8 提供的应用间和应用跟系统的功能交互特性。
  • Today (iOS and OS X): widgets for the Today view of Notification Center
  • Share (iOS and OS X): post content to web services or share content with others
  • Actions (iOS and OS X): app extensions to view or manipulate inside another app
  • Photo Editing (iOS): edit a photo or video in Apple's Photos app with extensions from a third-party apps
  • Finder Sync (OS X): remote file storage in the Finder with support for Finder content annotation
  • Storage Provider (iOS): an interface between files inside an app and other apps on a user's device
  • Custom Keyboard (iOS): system-wide alternative keyboards

Source: iOS 8 Extensions: Apple’s Plan for a Powerful App Ecosystem
【经典书】线性代数元素,197页pdf
专知会员服务
55+阅读 · 2021年3月4日
专知会员服务
78+阅读 · 2020年12月22日
Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
73+阅读 · 2020年5月5日
【经典书】统计学习导论,434页pdf,斯坦福大学
专知会员服务
234+阅读 · 2020年4月29日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
已删除
将门创投
3+阅读 · 2019年9月4日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年7月19日
SepNE: Bringing Separability to Network Embedding
Arxiv
3+阅读 · 2019年2月26日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
已删除
将门创投
3+阅读 · 2019年9月4日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员