Weakly redundant constraints and their impact on postoptimal analyses in LP

Suppose that in a mathematical programming problem with a smooth objective function the constraints set is formed by linear inequalities. Then, as is well known, it is possible to determine redundant constraints before the optimization procedure starts. If some of the vertices of the convex polyhedron defined by the linear constraints are degenerate, the known redundancy-determining procedures may fail. Based on the recently developed theory of degeneracy graphs (DG's for short) a procedure is suggested how to proceed in degenerate cases. Weakly redundant constraints which cause degeneracy do have some impact on sensitivity analyses with respect oo the RHS or objective function coefficients. Using again the theory of DG's this impact is analysed. Also procedures are suggested how to perform sensitivity analyses when the degeneracy of the optimal vertex is not caused only by weakly redundant constraints. Small numerical examples are used for illustration.     

Resolving degeneracy in combinatorial linear programs: Steepest edge,steepest ascent,and parametric ascent

While variants of the steepest edge pivot rule are commonly used in linear programming codes they are not known to have the theoretically attractive property of avoiding an infinite sequence of pivots at points of degeneracy. An example is presented demonstrating that the steepest edge pivot rule can fail to terminate finitely. It is then shown that a natural extension of the steepest edge pivot rule based on steepest ascent is guaranteed to determine a direction of ascent or a proof that no such direction exists after a finite number of pivots, although without modification the extension may not terminate with an ascent direction corresponding to an edge. Finally, it is demonstrated that a computationally more efficient pivot rule proposed by Magnanti and Orlin has similar theoretical properties to steepest ascent with probability 1independent of the linear program being solved. Unlike alternative methods such as primal lexicographic rules and Bland's rule, the algorithms described here have the advantage that they choose the pivot element without explicit knowledge of the set of all active constraints at a point of degeneracy, thus making them attractive in combinatorial settings where the linear program is represented implicitly.This work was sponsored in part by the National Science Foundation and the Office of Naval Research under NSF grant number DDM-9101578. The author gratefully acknowledges the support of IMSL, Inc.     

Degeneracy graphs: theory and application an updated survey

A survey of various aspects of the theory and application of degeneracy graphs (DGs for short) is given. The notion and some basic properties of DGs are introduced, cycling of the simplex method is discussed, the neighborhood problem is tackled, and the application of the so-called optimum DGs to particular problems which are connected with optimal degenerate solutions of a linear programming problem is presented. The impact of weakly redundant constraints on various postoptimal analyses under degeneracy is briefly described.     

On some properties of o-degeneracy graphs

Degenerate optima in linear programming problems lead in a canonical way to so-called o-degeneracy graphs as subgraphs of degeneracy graphs induced by the set of optimal bases. Fundamental questions about the structure of o-degeneracy graphs suggest the closer inspection of some properties of these graphs, such as, for example, the connectivity and the complexity. Finally, some open questions are pointed out.     

On degeneracy and collapsing in the construction of the set of objective values in a multiple objective linear program

In this paper an algorithm is developed to generate all nondominated extreme points and edges of the set of objective values of a multiple objective linear program. The approach uses simplex tableaux but avoids generating unnecessary extreme points or bases of extreme points. The procedure is based on, and improves, an algorithm Dauer and Liu developed for this problem. Essential to this approach is the work of Gal and Kruse on the neighborhood problem of determining all extreme points of a convex polytope that are adjacent to a given (degenerate) extreme point of the set. The algorithm will incorporate Gal's degeneracy graph approach to the neighborhood problem with Dauer's objective space analysis of multiple objective linear programs.     

线性时滞微分方程的点态退化(英文)

本文讨论了线性时滞微分方程的点态退化问题.借助于矩阵的有关知识,我们给出了判定n阶时滞微分方程点态退化的充分必要条件及代数判据.     

An Algorithm for Solving the Minimum-Norm Point Problem over the Intersection of a Polytope and an Affine Set

In this paper, we propose an efficient algorithm for finding the minimum-norm point in the intersection of a polytope and an affine set in an n-dimensional Euclidean space, where the polytope is expressed as the convex hull of finitely many points and the affine set is expressed as the intersection of k hyperplanes, k1. Our algorithm solves the problem by using directly the original points and the hyperplanes, rather than treating the problem as a special case of the general quadratic programming problem. One of the advantages of our approach is that our algorithm works as well for a class of problems with a large number (possibly exponential or factorial in n) of given points if every linear optimization problem over the convex hull of the given points is solved efficiently. The problem considered here is highly degenerate, and we take care of the degeneracy by solving a subproblem that is a conical version of the minimum-norm point problem, where points are replaced by rays. When the number k of hyperplanes expressing the affine set is equal to one, we can easily avoid degeneracy, but this is not the case for k2. We give a subprocedure for treating the degenerate case. The subprocedure is interesting in its own right. We also show the practical efficiency of our algorithm by computational experiments.     

Quenching of solutions to a class of semilinear parabolic equations with boundary degeneracy

This paper concerns the quenching phenomenon of solutions to a class of semilinear parabolic equations with boundary degeneracy. In the case that the degeneracy is not strong, it is shown that there exists a critical length, which is positive, such that the solution exists globally in time if the length of the spatial interval is less than it, while quenches in a finite time if the length of the spatial interval is greater than it. Whereas in the case that the degeneracy is strong enough, the solution must be quenching in a finite time no matter how long the spatial interval is. Furthermore, for each quenching solution, the set of quenching points is determined and it is proved that its derivative with respect to the time must blow up at the quenching time.     

Stabilized dynamic constraint aggregation for solving set partitioning problems

Dynamic constraint aggregation (DCA) and dual variable stabilization (DVS) are two methods that can reduce the negative impact of degeneracy when solving linear programs. The first uses a projection to reduce the primal space whereas the second acts in the dual space. In this paper, we develop a new method, called stabilized dynamic constraint aggregation (SDCA), that combines DCA and DVS for solving set partitioning problems. It allows to fight degeneracy from both primal and dual perspectives simultaneously. To assess the effectiveness of SDCA, we report computational results obtained for highly degenerate multi-depot vehicle scheduling problem instances solved by column generation. These results indicate that SDCA can reduce the average computational time of the master problem by a factor of up to 7 with respect to the best of the two combined methods. Furthermore, they show that its performance is robust with regard to increasing levels of degeneracy in test problems.     

An improved N-tree algorithm for the enumeration of all neighbors of a degenerate vertex

Based on the concept of degeneracy graphs, theoretical and algorithmic aspects of the neighborhood-problem are dealt with. It is shown that any subgraph of a positive degeneracy graph which is induced by a set of nodes feasible with respect to an arbitrary lexicographic pivot selection will supply sufficient information. A special lexicographic pivot selection strategy is presented which leads to an improved version of the N-tree method. The increase in efficiency is illustrated by test results.     

Degeneracy: Demystifying and destigmatizing a core concept in systems biology

Often relegated to the methods section of genetic research articles, the term “degeneracy” is regularly misunderstood and its theoretical significance widely understated. Degeneracy describes the ability of different structures to be conditionally interchangeable in their contribution to system functions. Frequently mislabeled redundancy, degeneracy refers to structural variation whereas redundancy refers to structural duplication. Sources of degeneracy include, but are not limited to, (1) duplicate structures that differentiate yet remain isofunctional, (2) unrelated isofunctional structures that are dispersed endogenously or exogenously, (3) variable arrangements of interacting structures that achieve the same output through multiple pathways, and (4) parcellation of a structure into subunits that can still variably perform the same initial function. The ability to perform the same function by drawing upon an array of dissimilar structures contributes advantageously to the integrity of a system. Drawing attention to the heterogeneous construction of living systems by highlighting the concept of degeneracy valuably enhances the ways scientists think about self‐organization, robustness, and complexity. Labels in science, however, can sometimes be misleading. In scientific nomenclature, the word “degeneracy” has calamitous proximity to the word “degeneration” used by pathologists and the shunned theory of degeneration once promoted by eugenicists. This article disentangles the concept of degeneracy from its close etymological siblings and offers a brief overview of the historical and contemporary understandings of degeneracy in science. Distinguishing the importance of degeneracy will hopefully allow systems theorists to more strategically operationally conceptualize the distributed intersecting networks that comprise complex living systems. © 2014 Wiley Periodicals, Inc. Complexity 20: 12–21, 2015     

On a double degenerate fourth-order parabolic equation

The existence of solutions to a fourth-order p-Laplacian equation with boundary degeneracy is studied. For the purpose of solving the corresponding non-degenerate (with respect to the coefficient of fourth-order term) regularized problem, a fourth-order semi-discrete elliptic problem with homogeneous boundary conditions is established and its existence and uniqueness are obtained by the functional minimization method. It follows that the approximate solutions of the non-degenerate parabolic problem are constructed and the corresponding existence and uniqueness are discovered by a limit procedure from the energy estimation method and a compactness argument. Finally, the existence and regularity of solutions for the problem with boundary degeneracy is obtained by using a regularization parameter vanishing limit.     

Asymptotic Behavior of Solutions to a Class of Semilinear Parabolic Equations with Boundary Degeneracy

This paper concerns the asymptotic behavior of solutions to one-dimensional semilinear parabolic equations with boundary degeneracy both in bounded and unbounded intervals. For the problem in a bounded interval, it is shown that there exist both nontrivial global solutions for small initial data and blowing-up solutions for large one if the degeneracy is not strong. Whereas in the case that the degeneracy is strong enough, the nontrivial solution must blow up in a finite time. For the problem in an unbounded interval, blowing-up theorems of Fujita type are established. It is shown that the critical Fujita exponent depends on the degeneracy of the equation and the asymptotic behavior of the diffusion coefficient at infinity, and it may be equal to one or infinity. Furthermore, the critical case is proved to belong to the blowing-up case.     

A degeneracy theorem for meromorphic mappings with truncated multiplicities

In this article, we prove a degeneracy theorem for three linearly non-degenerate meromorphic mappings from C n into P N (C), sharing 2N + 2 hyperplanes in general position, counted with multiplicities truncated by 2.     

Global classical solutions to a kind of quasilinear hyperbolic systems in several space variables

For a kind of quasilinear hyperbolic systems in several space variables whose coefficient matrices commute each other, by means of normalized coordinates, formulas of wave decomposition and pointwise decay estimates, the global existence of classical solution to the Cauchy problem for small and decaying initial data is obtained, under hypotheses of weak linear degeneracy and weakly strict hyperbolicity.     

A strictly improving linear programming Phase I algorithm

Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called basic) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs.When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.     

Boundary value problem for a class of degenerate quasilinear parabolic equations with singularity

This paper is concerned with a class of quasilinear parabolic equations with singularity and arbitrary degeneracy. The existence and uniqueness of generalized solutions to a kind of boundary value problem is established.     

On Localization of Solutions of Elliptic Equations with Nonhomogeneous Anisotropic Degeneracy

The work deals with the Dirichlet problem for elliptic equations with nonhomogeneous anisotropic degeneracy in a possibly unbounded domain of multidimensional Euclidean space. The existence of weak solutions is proved. Some conditions are established connecting the character of nonlinearity of the equation and the geometric characteristics of the domain which guarantee the one-dimensional localization (vanishing) of weak solutions. The equation with anisotropic degeneracy is shown to admit localized solutions even in the absence of absorption.     

三维光滑复射影簇上全纯曲线的退化性

讨论三维光滑复射影簇X上全纯曲线f:C→X的退化性.设D_1…,D_r为X上处于一般位置的相异的不可约有效除子.假定D_1…,D_r均为nef除子,而且存在正整数n_1…,n_r,c,使得n_in_jn_k(D_i.D_j.D_k)=c对所有i,j,k均成立.如果f的像取不到D_1…,D_r上的点,那么只要r≥11,f必定代数退化,即它的像包含于X的某个代数真子集中.     

Degeneracy in interior point methods for linear programming: a survey

The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming.We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.Partially supported by a research fund of SHELL.On leave from the Eötvös University, Budapest, and partially supported by OTKA No. 2116.