A degeneracy exploiting LU factorization for the simplex method

For general sparse linear programs two of the most efficient implementations of the LU factorization with Bartels—Golub updating are due to Reid and Saunders. This paper presents an alternative approach which achieves fast execution times for degenerate simplex method iterations, especially when used with multiple pricing. The method should have wide applicability since the simplex method performs a high proportion of degenerate iterations on most practical problems. A key feature of Saunders' method is combined with the updating strategy of Reid so as to make the scheme suitable for implementation out of core. Its efficiency is confirmed by experimental results.     

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.     

Selected bibliography on degeneracy

A selected bibliography on degeneracy problems organized according to the appearance of the respective references in various fields of operations research is given.     

Degenerate Linear Multicriteria Sensitivity

Sensitivity to perturbations of the vector objective function and/or the constraints is studied for the efficient (or weakly) set associated to a linear multicriteria program whose the feasible polyhedron is not necessarily assumed to be nondegenerate. Namely, the efficient set in the linear case being a connected union of some faces of the polyhedron, then we establish firstly second order necessary and sufficient conditions for the feasibility of a degenerate vertex under small perturbations, and finally, we give necessary and sufficient conditions of Simplex type, for a such vertex, or incident face to it, to be efficient and mostly to preserve this quality after the perturbations.     

Balinski—Tucker simplex tableaus: Dimensions, degeneracy degrees, and interior points of optimal faces

This paper shows the relationship between degeneracy degrees and multiple solutions in linear programming (LP) models. The usual definition of degeneracy is restricted to vertices of a polyhedron. We introduce degeneracy for nonempty subsets of polyhedra and show that for LP-models for which the feasible region contains at least one vertex it holds that the dimension of the optimal face is equal to the degeneracy degree of the optimal face of the corresponding dual model. This result is obtained by means of the so-called Balinski—Tucker (B—T) Simplex Tableaus. Furthermore, we give a strong polynomial algorithm for constructing such a B—T Simplex Tableau when a solution in the relative interior of the optimal face is known. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

An implementation of the simplex method for linear programming problems with variable upper bounds

Special methods for dealing with constraints of the formx _j x _k , called variable upper bounds, were introduced by Schrage. Here we describe a method that circumvents the massive degeneracy inherent in these constraints and show how it can be implemented using triangular basis factorizations.This research was partially supported by National Science Foundation Grant ECS-7921279 and by a Guggenheim fellowship.     

A construction method in parametric programming

We consider a linear programming problem, with two parameters in the objective function, and present an algorithm for finding the decomposition of the parameter space into maximal polyhedral areas in which particular basic solutions are optimal. Special attention is paid to fill up areas of degenerate solutions.     

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.     

Dealing with degeneracy in reduced gradient algorithms

Many algorithms for linearly constrained optimization problems proceed by solving a sequence of subproblems. In these subproblems, the number of variables is implicitly reduced by using the linear constraints to express certain ‘basic’ variables in terms of other variables. Difficulties may arise, however, if degeneracy is present; that is, if one or more basic variables are at lower or upper bounds. In this situation, arbitrarily small movements along a feasible search direction in the reduced problem may result in infeasibilities for basic variables in the original problem. For such cases, the search direction is typically discarded, a new reduced problem is formed and a new search direction is computed. Such a process may be extremely costly, particularly in large-scale optimization where degeneracy is likely and good search directions can be expensive to compute. This paper is concerned with a practical method for ensuring that directions that are computed in the reduced space are actually feasible in the original problem. It is based on a generalization of the ‘maximal basis’ result first introduced by Dembo and Klincewicz for large nonlinear network optimization problems. Research supported in part by NSF Grant ECS-8119513 and DOT Research Grant CT-06-0011.     

Preventing redundant solutions in partial enumeration algorithms

Many algorithms for discrete problems use a variation of the tree-search enumeration technique as a basis for the algorithm. If a solution is the assignment of an attribute from a set ofm attributes to every variable in a set ofn variables, then redundant solutions can be generated if either the attributes or the variables contain some indistinguishable elements. A series of necessary and sufficient techniques are developed to eliminate the production of redundant solutions during enumeration. These techniques can be used to form the foundation of any partial enumeration algorithm where redundant solutions can be produced.     

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 theory of degeneracy graphs

Using some results of the theory of finite sets, a characterization of ×n-degeneracy graphs is developed. This result can be used to derive various structural properties of degeneracy graphs.     

A dual approach to primal degeneracy

The Revised Primal Simplex algorithm, in its simplest form, has no defence against degeneracy. Various forms of the perturbation method are usually effective, but most offer no guarantee of avoiding all degeneracy, and can lead to numerical difficulties. This paper presents a method that avoids cycling and circling by taking a dual approach.The degenerate subproblem consists of all the original variables, but only the degenerate transformed constraints. The current primal objective, which may be mixed, is used. This subproblem may be solved using the dual simplex algorithm, starting from the current dual infeasible solution, and with a zero dual objective. If the dual algorithm terminates optimally then the whole problem is optimal (subject to primal feasibility). Otherwise the final solution provides a non-basic direction which improves the value of the mixed primal objective and moves away from the degenerate vertex. A purification algorithm then renders the solution basic and further improves the mixed objective.     

An efficient algorithm for enumeration of triangulations

We consider the problem of enumerating triangulations of n points in the plane in general position. We introduce a tree of triangulations and present an algorithm for enumerating triangulations in O(loglogn) time per triangulation. It improves the previous bound by almost linear factor.     

Binary functions,degeneracy, and alternating dimaps

This paper continues the study of combinatorial properties of binary functions — that is, functions $f:2^E\to ?$ such that $f(0?)=1$, where $E$ is a finite set. Binary functions have previously been shown to admit families of transforms that generalise duality, including a trinity transform, and families of associated minor operations that generalise deletion and contraction, with both these families parameterised by the complex numbers. Binary function representations exist for graphs (via the indicator functions of their cutset spaces) and indeed arbitrary matroids (as shown by the author previously). In this paper, we characterise degenerate elements – analogues of loops and coloops – in binary functions, with respect to any set of minor operations from our complex-parameterised family. We then apply this to study the relationship between binary functions and Tutte’s alternating dimaps, which also support a trinity transform and three associated minor operations. It is shown that only the simplest alternating dimaps have binary representations of the form we consider, which seems to be the most direct type of representation. The question of whether there exist other, more sophisticated types of binary function representations for alternating dimaps is left open.     

Properties, isomorphisms and enumeration of 2-Quasi-Magic Sudoku grids

A Sudoku grid is a 9×9 Latin square further constrained to have nine non-overlapping 3×3 mini-grids each of which contains the values 1–9. In Δ-Quasi-Magic Sudoku a further constraint is imposed such that every row, column and diagonal in each mini-grid sums to an integer in the interval [15−Δ,15+Δ]. The problem of proving certain (computationally known) results for Δ=2 concerning mini-grids and bands (rows of mini-grids) was posed at the British Combinatorial Conference in 2007. These proofs are presented and extensions of these provide a full combinatorial enumeration for the total number of completed 2-Quasi-Magic Sudoku grids. It is also shown that there are 40 isomorphism classes of completed 2-Quasi-Magic Sudoku grids.     

Maximization of submodular functions: Theory and enumeration algorithms

Submodular functions are powerful tools to model and solve either to optimality or approximately many operational research problems including problems defined on graphs. After reviewing some long-standing theoretical results about the structure of local and global maxima of submodular functions, Cherenin’s selection rules and his Dichotomy Algorithm, we revise the above mentioned theory and show that our revision is useful for creating new non-binary branching algorithms and finding either approximation solutions with guaranteed accuracy or exact ones.     

An algorithm for the enumeration of spanning trees

Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n ²). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.