论文标题
在多源超平面位置问题到拟合点
On the multisource hyperplanes location problem to fitting set of points
论文作者
论文摘要
在本文中，我们研究了定位给定数量的超平面数量的问题，最大程度地限制了一组点的最距离的客观函数。我们为问题提出了一个一般框架，即通过有序中位功能汇总点和超平面之间的基于规范的距离。为问题提供了紧凑的混合整数线性（或非线性）编程公式，并得出了带有指数变量数量的扩展设置分区公式。我们开发了嵌入分支机构和价格算法中的列生成过程，用于通过充分执行其预处理，定价和分支来解决该问题。我们还通过几何分析问题的最佳解决方案，从而得出了被利用的特性，这些属性是为提出的算法生成初始溶液。最后，报告了广泛的计算经验的结果。还解决了可伸缩性问题，以通过汇总版本替换原始数据集在假定的错误上显示理论上限。
In this paper we study the problem of locating a given number of hyperplanes minimizing an objective function of the closest distances from a set of points. We propose a general framework for the problem in which norm-based distances between points and hyperplanes are aggregated by means of ordered median functions. A compact Mixed Integer Linear (or Non Linear) programming formulation is presented for the problem and also an extended set partitioning formulation with an exponential number of variables is derived. We develop a column generation procedure embedded within a branch-and-price algorithm for solving the problem by adequately performing its preprocessing, pricing and branching. We also analyze geometrically the optimal solutions of the problem, deriving properties which are exploited to generate initial solutions for the proposed algorithms. Finally, the results of an extensive computational experience are reported. The issue of scalability is also addressed showing theoretical upper bounds on the errors assumed by replacing the original datasets by aggregated versions.
