A note on degeneracy in linear programming

We show that the problem of exiting a degenerate vertex is as hard as the general linear programming problem. More precisely, every linear programming problem can easily be reduced to one where the second best vertex (which is highly degenerate) is already given. So, to solve the latter, it is sufficient to exit that vertex in a direction that improves the objective function value.     

Resolving degeneracy in quadratic programming

A technique for the resolution of degeneracy in an Active Set Method for Quadratic Programming is described. The approach generalises Fletcher's method [2] which applies to the LP case. The method is described in terms of an LCP tableau, which is seen to provide useful insights. It is shown that the degeneracy procedure only needs to operate when the degenerate constraints are linearly dependent on those in the active set. No significant overheads are incurred by the degeneracy procedure. It is readily implemented in a null space format, and no complications in the matrix algebra are introduced.The guarantees of termination provided by [2], extending in particular to the case where round-off error is present, are preserved in the QP case. It is argued that the technique gives stronger guarantees than are available with other popular methods such as Wolfe's method [11] or the method of Goldfarb and Idnani [7].Presented at the 14th International Symposium on Mathematical Programming, Amsterdam, August 5–9, 1991.     

A new reduction method in integer programming

The system of two equations in nonnegative integer unknowns x_j and expressed in the form ∑ⁿ_j=1 a_1jx_j=b₁, ∑ⁿ_j=1 a_2jx_j=b₂ has equivalent solutions to the single equation ∑ⁿ_j=1 (t₁a_ij+t₂a_2j)a_j= t₁b₁+t₂b₂, provided t₁ and t₂ are suitably chosen. Glover [2] has n inequalities for determining t₁ and t₂. Elimam and Elmaghraby [1] try to achieve a single inequality for t₁ and t₂. We show, however, that the inequality of [1] may give t₁ and t₂ values that do not produce equivalence. We present a new theorem which leads to a single inequality constraint giving t₁ and t₂ values that consistently produce equivalence.     

An integer programming approach to b-coloring

In the b-coloring problem, we aim to assign colors from a set $C$ to the vertices of a graph $G$ in such a way that adjacent vertices do not receive the same color, and for every $c\in C$ we have a $c$-colored vertex $v$ in $G$ such that every color in $C\setminus \left\{c\right\}$ is assigned to at least one of $v$’s neighbors. It has been shown that b-coloring is NP-complete, so we propose in this article an approach for the problem under integer programming techniques. To this end, we give an integer programming formulation and study the associated polytope. We provide several families of valid inequalities, and analyze facetness conditions for them. Finally, we show computational evidence suggesting that the given inequalities may be useful in a branch-and-cut environment.     

Experiments in integer programming

A hybrid algorithm to solve large scale zero–one integer programming problems has been developed. The algorithm combines branch-and-bound, enumeration and cutting plane techniques. Mixed-integer cuts are generated in the initial phase of the algorithm and added to the L.P. Benders cuts are derived and used implicitly but, except for the cut from the initial LP, are not stored. The algorithm has been implemented on an experimental basis in MPSX/370 using its Extended Control Language and Algorithmic Tools. A computational study based on five well-known difficult test problems and on three practical problems with up to 2000 zer–one variables shows that the hybrid code compares favorably with MIP/370 and with results published for other algorithms.     

A parallel integer linear programming algorithm

The solution of large scale integer linear programming models is generally dependent, in some way, upon the branch and bound technique, which can be quite time consuming. This paper describes a parallel branch and bound algorithm which achieves super linear efficiency in solving integer linear programming models on a multiprocessor computer. The algorithm is used to solve the Haldi and IBM test problems as well as a system design model.     

Generalized dynamic programming methods in integer programming

When regarded as a shortest route problem, an integer program can be seen to have a particularly simple structure. This allows the development of an algorithm for finding thek ^th best solution to an integer programming problem with max{O(kmn), O(k logk)} operations. Apart from its value in the parametric study of an optimal solution, the approach leads to a general integer programming algorithm consisting of (1) problem relaxation, (2) solution of the relaxed problem parametrically by dynamic programming, and (3) generation ofk ^th best solutions until a feasible solution is found. Elementary methods based on duality for reducingk for a given problem relaxation are then outlined, and some examples and computational aspects are discussed.     

A note on aggregating constraints in integer programming

To aggregate constraints is a technique for solving the integer programming problem. In this note we modify a result of Zionts (1974); without this modification, there is a counterexample for Zionts' result. Further, we give an elegant theorem which considers the aggregation of nonlinear constraints.This work was partially supported by the Chinese National Science Council.     

A separable integer programming problem equivalent to its continual version

The separable integer programming problem with so called nested constraints is shown to be equivalent to its continual version obtained by piecewise linear continuation of the cost functions. A new approach to solution of the latter based on its successive reduction in size is suggested. When applied to the problem with piecewise linear convex functions it leads to two algorithms for its solution applicable also to the similar integer problem. These algorithms turn out more efficient than those obtained by dynamic programming approach.     

A nonlinear Lagrangian dual for integer programming

Nonlinear Lagrangian theory offers a success guarantee for the dual search via construction of a nonlinear support of the perturbation function at the optimal point. In this paper, a new nonlinear dual formulation of an exponential form is proposed for bounded integer programming. This new formulation possesses an asymptotic strong duality property and guarantees a success in identifying a primal optimum solution. No actual dual search is needed in the solution process when the parameter of the nonlinear Lagrangian formulation is set to be large enough.     

Enumerative inequalities in integer programming

For a linear integer programming problem, thelocal information contained at an optimal solution of the continuous linear programming extension stems from the theory of L.P. solutions. This paper proposes the use ofenvironmental information (of a global nature but pertaining to the discrete vicinity of ), in order to isolate the set of integer solutions which may be considered as true candidates for the optimum. The concept ofenumerative inequalities is introduced and it is shown how it can be obtained in the context of the convex outer-domain theory of Balas, Young, et al.Generally speaking, enumerative inequalities can be made arbitrarily strong (deep), but at the cost of an increasing amount of work (i.e. enumeration) for their construction. In particular cases, however, very little global information can produce enumerative inequalities stronger than anyvalid cut.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.     

整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.     

Subadditive approaches in integer programming

Linear programming duality is well understood and the reduced cost of a column is frequently used in various algorithms. On the other hand, for integer programs it is not clear how to define a dual function even though the subadditive dual theory has been developed a long time ago. In this work we propose a family of computationally tractable subadditive dual functions for integer programs. We develop a solution methodology that computes an optimal primal solution and an optimal subadditive dual function. We present computational experiments, which show that the new algorithm is tractable.     

Fourier-Motzkin elimination extension to integer programming problems

This paper describes how the Fourier-Motzkin Elimination Method, which can be used for solving Linear Programming Problems, can be extended to deal with Integer Programming Problems. The extension derives from a known decision procedure for the formal theory of a fragment of arithmetic which excludes multiplication.     

Least-index resolution of degeneracy in quadratic programming

In this study, we combine least-index pivot selection rules with Keller's algorithm for quadratic programming to obtain a finite method for processing degenerate problems.Research and reproduction of this report were partially supported by National Science Foundation Grant MCS76-81259; and the Office of Naval Research Contract N00014-75-C-0267.     

A linear algorithm for integer programming in the plane

We show that a 2-variable integer program, defined by m constraints involving coefficients with at most bits, can be solved with O(m+) arithmetic operations on rational numbers of size O().     

A linear integer programming bound for maximum-entropy sampling

 We introduce a new upper bound for the maximum-entropy sampling problem. Our bound is described as the solution of a linear integer program. The bound depends on a partition of the underlying set of random variables. For the case in which each block of the partition has bounded cardinality, we describe an efficient dynamic-programming algorithm to calculate the bound. For the very special case in which the blocks have no more than two elements, we describe an efficient algorithm for calculating the bound based on maximum-weight matching. This latter formulation has particular value for local-search procedures that seek to find a good partition. We relate our bound to recent bounds of Hoffman, Lee and Williams. Finally, we report on the results of some computational experiments. Received: September 27, 2000 / Accepted: July 26, 2001 Published online: September 5, 2002 Key words. experimental design – design of experiments – entropy – maximum-entropy sampling – matching – integer program – spectral bound – Fischer's inequality – branch-and-bound – dynamic programming Mathematics Subject Classification (2000): 52B12, 90C10 Send offprint requests to: Jon Lee Correspondence to: Jon Lee     

Developments in linear and integer programming

In this review we describe recent developments in linear and integer (linear) programming. For over 50 years Operational Research practitioners have made use of linear optimisation models to aid decision making and over this period the size of problems that can be solved has increased dramatically, the time required to solve problems has decreased substantially and the flexibility of modelling and solving systems has increased steadily. Large models are no longer confined to large computers, and the flexibility of optimisation systems embedded in other decision support tools has made on-line decision making using linear programming a reality (and using integer programming a possibility). The review focuses on recent developments in algorithms, software and applications and investigates some connections between linear optimisation and other technologies.     

A note on rank functions and integer programming

An attempt is made, with only partial success, to obtain integer analogues of some linear-programming results that are useful in combinatorics.