English

运筹学学报

• 运筹学 • 上一篇    下一篇

一类特殊多项式整数规划问题的最优化算法

 田静, 吴至友,  J. Ugon   

  1. 1.
    2. University of Ballarat, Australia
    3. 重庆师范大学数学学院
  • 收稿日期:2011-01-26 修回日期:2011-11-02 出版日期:2011-12-15 发布日期:2011-12-19
  • 通讯作者: 吴至友 E-mail:zhiyouwu@263.net

Optimization Methods for a Class of Integer Polynomial Programming Problems

 TIAN  Jing, WU  Zhi-You,   J. Ugon   

  • Received:2011-01-26 Revised:2011-11-02 Online:2011-12-15 Published:2011-12-19
  • Contact: Zhiyou WU E-mail:zhiyouwu@263.net

PDF

1783

被引次数

11

摘要： 本文考虑了一类特殊的多项式整数规划问题。此类问题有很广泛的实际应用，并且是NP难问题。对于这类问题，最优性必要条件和最优性充分条件已经给出。我们在本文中将要利用这些最优性条件设计最优化算法。首 先，利用最优性必要条件，我们给出了一种新的局部优化算法。进而我们结合最优性充分条件、新的局部优化算法和辅助函数，设计了新的全局最优化算法。本文给出的算例展示出我们的算法是有效的和可靠的。

关键词: 多项式整数规划, 局部最优化算法, 全局最优化算法

Abstract: In this paper, a class of integer polynomial programming problems is considered. This class of integer polynomial programming problems has a wide range of practical applications and is NP hard. For these problems, necessary global optimality conditions and sufficient global optimality conditions have been presented recently. We will design some optimization methods to this class of integer polynomial programming problems by using these global optimality conditions. Firstly, a local optimization method is designed according to the necessary global optimality conditions for these integer polynomial programming problems. Moreover, a new global optimization method for this class of integer polynomial programming problems is presented by combining the sufficient global optimality conditions, the local optimization method and an auxiliary function. Some numerical examples are presented to illustrate the efficiency and reliability of these optimization methods.

Key words: Polynomial integer programming problem, local optimization method, global optimization method