Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms
Light on the infinite group relaxation II: sufficient conditions for extremality, sequences, and algorithms
复制标题
浅谈无限群弛豫 II：极值、序列和算法的充分条件
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
M. Köppe
中科院分区：
文献类型：
--
作者：
A. Basu;R. Hildebrand;M. Köppe
这是关于无限群问题的综述的第二部分，无限群问题是整数线性优化问题的无限维松弛，由Ralph Gomory和Ellis Johnson在他们的开创性论文《与角多面体I，II相关的一些连续函数》(Math Program 3：23-85,1972a；Math Program 3：359-389,1972b)中引入。这篇综述介绍了在割母函数的现代背景下的无限群问题。它集中于最近的发展，如测试算法和对一般k≥1Documentclass[12pt]{Minimum}usepackage{amsath}usepackage{amssym}usepackage{amsfonts}usepackage{amssymb}usepackage{amsbsy}usepackage{mathsfs}usepackage{upgreek}setlong{oddsidemarin}{-69pt}，例如{Document}$$kge 1$$end{Document}扩展了以前关于单行和两行问题的工作。该调查还包括一些以前未发表的结果；除其他外，它还公布了具有四个以上不同斜率的分段线性极值函数。在开源计算机代数包Sage中实现的一个交互伴随程序，提供了已知极值函数的最新概要。
This is the second part of a survey on the infinite group problem, an infinite-dimensional relaxation of integer linear optimization problems introduced by Ralph Gomory and Ellis Johnson in their groundbreaking papers titled Some continuous functions related to corner polyhedra I, II (Math Program 3:23–85, 1972a; Math Program 3:359–389, 1972b). The survey presents the infinite group problem in the modern context of cut generating functions. It focuses on the recent developments, such as algorithms for testing extremality and breakthroughs for the k-row problem for general k≥1documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$$kge 1$$end{document} that extend previous work on the single-row and two-row problems. The survey also includes some previously unpublished results; among other things, it unveils piecewise linear extreme functions with more than four different slopes. An interactive companion program, implemented in the open-source computer algebra package Sage, provides an updated compendium of known extreme functions.