Integer Programming and Network Flows.

Journal of the Operational Research Society -     

Integer Programming Duality in Multiple Objective Programming

The weighted sums approach for linear and convex multiple criteria optimization is well studied. The weights determine a linear function of the criteria approximating a decision makers overall utility. Any efficient solution may be found in this way. This is not the case for multiple criteria integer programming. However, in this case one may apply the more general e-constraint approach, resulting in particular single-criteria integer programming problems to generate efficient solutions. We show how this approach implies a more general, composite utility function of the criteria yielding a unified treatment of multiple criteria optimization with and without integrality constraints. Moreover, any efficient solution can be found using appropriate composite functions. The functions may be generated by the classical solution methods such as cutting plane and branch and bound algorithms.     

一个基于离散填充函数的整数线性规划方法

本文提出了一个有效的解决整数线性规划的新算法.如果离散化的局部搜索过程陷入局部最优解,则构造相应的离散填充函数,引导搜索过程跳出局部最优解并得到更好的解.该方法是在离散空间中进行优化的,无需增加新的约束,且一直保持整数可行性,收敛的速度非常快.该方法也为一般整数规划提出了一种新的途径.数值实例表明,与现有的方法相比,该算法能够较快的找到最优解.     

Hypergeometric Polynomials and Integer Programming

We examine connections between A-hypergeometric differential equations and the theory of integer programming. In the first part, we develop a hypergeometric sensitivity analysis for small variations of constraint constants with creation operators and b-functions. In the second part, we study the indicial polynomial (b-function) along the hyperplane xi=0 via a correspondence between the optimal value of an integer programming problem and the roots of the indicial polynomial. Gröbner bases are used to prove theorems and give counter examples.     

整数规划中的正则分解

In this paper, we study the problem of regular decomposition in integer programming. We apply the radical of binomial ideal and universal Gr¨obner bases to get the regular decomposition forms of a finite integer lattice point set. We indicate the relationship between state polytope and regular decompositions, i.e., an edge of state polytope corresponds to a binomial which decides one of regular decomposition forms of a finite integer lattice point set.     

Towards Strong Duality in Integer Programming

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.     

Duality Gaps in Stochastic Integer Programming

In this note, we explore the implications of a result that suggests that the duality gap caused by a Lagrangian relaxation of the nonanticipativity constraints in a stochastic mixed integer (binary) program diminishes as the number of scenarios increases. By way of an example, we illustrate that this is not the case. In general, the duality gap remains bounded away from zero.     

Finiteness Theorems in Stochastic Integer Programming

We study Graver test sets for families of linear multistage stochastic integer programs with a varying number of scenarios. We show that these test sets can be decomposed into finitely many "building blocks," independent of the number of scenarios, and we give an effective procedure to compute them. The paper includes an introduction to Nash-Williams' theory of better-quasi-orderings, which is used to show termination of our algorithm. We also apply this theory to finiteness results for Hilbert functions.     

Decomposition and Dynamic Cut Generation in Integer Linear Programming

Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen an initial linear programming relaxation. Recently, a number of authors have proposed methods for integrating dynamic cut generation with various decomposition methods to yield further improvement in computed bounds. In this paper, we describe a framework within which most of these methods can be viewed from a common theoretical perspective. We then discuss how the framework can be extended to obtain a decomposition-based separation technique we call decompose and cut. As a by-product, we describe how these methods can take advantage of the fact that solutions with known structure, such as those to a given relaxation, can frequently be separated much more easily than arbitrary real vectors.     

Incremental and encoding formulations for Mixed Integer Programming

The standard way to represent a choice between n$n$ alternatives in Mixed Integer Programming is through n$n$ binary variables that add up to one. Unfortunately, this approach commonly leads to unbalanced branch-and-bound trees and diminished solver performance. In this paper, we present an encoding formulation framework that encompasses and expands existing approaches to mitigate this behavior. Through this framework, we generalize the incremental formulation for piecewise linear functions to any finite union of polyhedra with identical recession cones.     

整数规划中割平面法的研究

割平面法是求解整数规划问题常用方法之一.用割平面法求解整数规划的基本思路是:先用单纯形表格方法去求解不考虑整数约束条件的松弛问题的最优解,如果获得的最优解的值都是整数,即为所求,运算停止.如果所得最优解不完全是整数,即松弛问题最优解中存在某个基变量为非整数值时,就从最优表中提取出关于这个基变量的约束等式,再从这个约束式出发构造一个割平面方程加入最优表中,再求出新的最优解,这样不断重复的构造割平面方程,直到找到整数解为止.主要研究以下四个关键点:一是研究从最优表中提取出的、关于基变量的约束等式出发,通过将式中的系数进行整数和非负真分数的分解,从而得到一个小于等于0的另外一个不等式的推导过程;二是总结出从小于等于0的那个约束不等式出发构造割平面方程的四种方法;三是分析构造割平面方程的这四种方法相互之间的区别和联系;四是探讨割平面法的几何意义.通过对这四个方面的分析和研究,对割平面法进行透彻的剖析,使读者能够全面把握割平面法.     

Encoding Binary Arithmetic Operations in Integer Programming Formulations

This paper presents the encoding of binary arithmetic operations within Integer Programming (IP) formulations, specifically the encoding of binary multiplication and addition/subtraction. This allows the direct manipulation of integer quantities represented as binary strings of arbitrary size. Many articles published in the past within the Chemical Engineering community have used this representation of integer quantities within Mixed-Integer formulations for Process Optimization and Design. Applications such as these can benefit from the formulations derived in this work. As a demonstrative application we consider the simple number factorization problem, according to which given an odd number C factors A and B are to be found such that C equals their product. If any such factors are found the number is factorable, else it is proven to be prime. An IP formulation is derived involving upper and lower bounding logical constraints to encode for the value of the binary string digits. The formulation involves \({\cal O}(\log C)\) binary variables, \({\cal O}((\log C)^{2})\) continuous variables, and \({\cal O}((\log C)^{2})\) constraints to describe the problem. Computational results demonstrate the validity of this approach, highlighting also the fact that such formulations are not very tight thus resulting in large numbers of iterations of the Branch and Bound algorithm used. It is also observed that the formulations become significantly tighter if logical upper bounding constraints forcing continuous variables involved to be zero are included.     

一般整数规划中有效不等式的同步升维

有效不等式在整数规划的定界研究中具有重要的意义.研究了一般整数规划问题的有效不等式的升维方法,引入超加性函数给出同步升维的条件,并给出有效不等式的同步升维的具体方法,算例表明本文提出的方法是有效的.     

A Note on Degeneracy in Integer Linear Programming Problem

A set of three batches of 1000 randomly produced integer linear programming problems of different sizes was solved using a partial enumeration algorithm. That particular algorithm involves the initial ordering of the variables according to their attractiveness when considered individually. The results reveal that, as might have been expected, the most attractive variables appear very much more frequently than do the less attractive. Perhaps less expected is the fact that the average number of variables appearing in the optimum solution is considerably less than might have been anticipated. Thus, for example, the average number of variables which appear in a set of problems featuring 20 variables and 10 constraints is only 4.14, as against the 10 one would have been expecting in continuous LP problems of that size. It is argued that it is this inherent characteristic which results in truncation solution procedures being as effective as they are.     

On the Merits and Demerits of Integer Goal Programming

In a recent paper, it was suggested that the use of integer goal programming is questionable. No mathematical proof was provided to substantiate such a serious and far-reaching claim; instead, several ‘counterexamples’ were presented in support of the allegations. In this paper, we present a refutation of these allegations, and examine the reasons why such erroneous conclusions might have been reached.