发帖
雷达卡
摘要翻译：
本文提出了一种利用代数几何工具求解多目标整数线性规划的新方法。本文对右端可变的多目标规划族引入了部分Gr\'Obner基的概念，将单目标情形下的Gr\'Obner基的概念推广到多目标情形，即可行向量上的部分排序而不是全排序。这些基的主要性质是约束矩阵核中的整数元素被基的不同块部分约简为零。它允许我们证明这个新的构造是一个多目标程序族的测试族。本文提出了一种计算部分Gr-Obner基的算法“a la Buchberger”，并利用该算法导出了计算任意多目标整数线性问题(MOILP)的全套有效解的两种不同方法，举例说明了算法的应用，并对几类问题进行了计算实验。
---
英文标题：
《Partial Gr\"obner bases for multiobjective integer linear optimization》
---
作者：
Victor Blanco and Justo Puerto
---
最新提交年份：
2008
---
分类信息：
一级分类：Mathematics 数学
二级分类：Optimization and Control 优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--
一级分类：Mathematics 数学
二级分类：Algebraic Geometry 代数几何
分类描述：Algebraic varieties, stacks, sheaves, schemes, moduli spaces, complex geometry, quantum cohomology
代数簇，叠，束，格式，模空间，复几何，量子上同调
--
---
英文摘要：
In this paper we present a new methodology for solving multiobjective integer linear programs using tools from algebraic geometry. We introduce the concept of partial Gr\"obner basis for a family of multiobjective programs where the right-hand side varies. This new structure extends the notion of Gr\"obner basis for the single objective case, to the case of multiple objectives, i.e., a partial ordering instead of a total ordering over the feasible vectors. The main property of these bases is that the partial reduction of the integer elements in the kernel of the constraint matrix by the different blocks of the basis is zero. It allows us to prove that this new construction is a test family for a family of multiobjective programs. An algorithm '\`a la Buchberger' is developed to compute partial Gr\"obner bases and two different approaches are derived, using this methodology, for computing the entire set of efficient solutions of any multiobjective integer linear problem (MOILP). Some examples illustrate the application of the algorithms and computational experiments are reported on several families of problems.
---
PDF链接：
https://arxiv.org/pdf/0709.1660
京公网安备 11010802022788号
