Lattice-finite Rings

We study a one-dimensional analogue of representation-finite rings. For a left Noetherian semilocal ring R, we define an R-lattice to be a finitely generated R-module with zero socle. We call R lattice-finite if the number of isomorphism classes of indecomposable R-lattices is finite. Under this assumption, we give several equivalent criteria for the existence of Auslander–Reiten sequences in the category of R-lattices. A necessary condition is that the maximal left quotient ring of R is semisimple, and the main sufficient criterion states that R admits a semiperfect semiprime Asano left overorder. Presented by I. Reiten Mathematics Subject Classifications (2000) Primary: 16G70, 16G30; secondary: 16G60.     

τ-Categories III: Auslander Orders and Auslander–Reiten Quivers

We study the relationship between representation theoretic properties and homological properties of orders. We show that there is a close relationship among Auslander orders, τ-categories and Auslander regular rings. As an application, we give a combinatorial characterization of finite Auslander–Reiten quivers of orders. Presented by K. Roggenkamp Mathematics Subject Classifications (2000) Primary: 16G30; secondary: 16E65, 16G70, 18E05. Current address: Department of Mathematics, University of Hyogo, Himeji, 671-2201, Japan. e-mail: iyama@sci.u-hyogo.ac.jp     

τ-Categories I: Ladders

In this series of papers, we introduce τ-categories, which are additive categories with some kind of Auslander–Reiten sequences. We apply them to study the category of lattices over orders. In this first paper, we study minimal projective resolutions in functor categories over τ-categories. Then we give a structure theorem of completely graded τ-categories using mesh categories. Presented by K. Roggenkamp Mathematics Subject Classifications (2000) primary 16G30; secondary 16E65, 16G70, 18E05. Osamu Iyama: Current address: Department of Mathematics, University of Hyogo, Himeji, 671-2201, Japan. e-mail: iyama@sci.u-hyogo.ac.jp.     

The Gabriel–Roiter Measure for Right Pure Semisimple Rings

We show how the Gabriel–Roiter measure, introduced by Ringel in (Bull Sci Math 129:726–748, 2005 and Contemp Math 406:105–135, 2006), applies to indecomposable modules of finite length over right pure semisimple rings, and in particular to the study of the open problem whether any right pure semisimple ring is of finite representation type. Dedicated to the memory of Andrey Vladimirovich Roiter. Professor A. V. Roiter has died on 26 July 2006 in Riga, Latvia. He was born in 1937.     

Embeddings of Non-semiregular Translation Quivers in Quivers of Type $\mathbb{Z}\Delta$

In this work we show that a directed translation quiver such that every path from a injective vertex to a projective vertex that has at most two hooks and in case two, they are consecutives, can be embedded in a quiver . This generalizes a result by (Li, Comm. Algebra, 28(10),4635–4645, 2000). Dedicated to Raymundo Bautista on his 60th Birthday.     

The Auslander–Reiten Quiver of a Poincaré Duality Space

In a previous paper, Auslander–Reiten triangles and quivers were introduced into algebraic topology. This paper shows that over a Poincaré duality space, each component of the Auslander–Reiten quiver is isomorphic to . Presented by Yuri Drozd     

Some categorical properties of the functors O τ and O R of weakly additive functionals

In the paper, the spaces of weakly additive τ-smooth and Radon functionals are investigated. It is proved that the functors of weakly additive τ-smooth and Radon functionals weakly preserve the density of Tychonoff spaces, and the functor of weakly additive τ-smooth functionals forms a monad in the category of Tychonoff spaces and their continuous mappings. Examples and remarks are given showing that these functors fail to satisfy certain Shchepin normality conditions. Problems having positive solutions for normal functors are presented.     

Nonlinear programming without a penalty function

In this paper the solution of nonlinear programming problems by a Sequential Quadratic Programming (SQP) trust-region algorithm is considered. The aim of the present work is to promote global convergence without the need to use a penalty function. Instead, a new concept of a “filter” is introduced which allows a step to be accepted if it reduces either the objective function or the constraint violation function. Numerical tests on a wide range of test problems are very encouraging and the new algorithm compares favourably with LANCELOT and an implementation of Sl₁QP. Received: October 17, 1997 / Accepted: August 17, 2000?Published online September 3, 2001     

Optimization via enumeration: a new algorithm for the Max Cut Problem

We present a polynomial time algorithm to find the maximum weight of an edge-cut in graphs embeddable on an arbitrary orientable surface, with integral weights bounded in the absolute value by a polynomial of the size of the graph.</ The algorithm has been implemented for toroidal grids using modular arithmetics and the generalized nested dissection method. The applications in statistical physics are discussed. Received: June 1999 / Accepted: December 2000?Published online March 22, 2001     

The mathematics of playing golf, or: a new class of difficult non-linear mixed integer programs

We consider a class of non-linear mixed integer programs with n integer variables and k continuous variables. Solving instances from this class to optimality is an NP-hard problem. We show that for the cases with k=1 and k=2, every optimal solution is integral. In contrast to this, for every k≥3 there exist instances where every optimal solution takes non-integral values. Received: August 2001 / Accepted: January 2002?Published online March 27, 2002     

Global convergence of a class of non-interior point algorithms using Chen-Harker-Kanzow-Smale functions for nonlinear complementarity problems

We propose a class of non-interior point algorithms for solving the complementarity problems(CP): Find a nonnegative pair (x,y)∈ℝ ²ⁿ satisfying y=f(x) and x _i y _i =0 for every i∈{1,2,...,n}, where f is a continuous mapping from ℝ ⁿ to ℝ ⁿ . The algorithms are based on the Chen-Harker-Kanzow-Smale smoothing functions for the CP, and have the following features; (a) it traces a trajectory in ℝ ³ⁿ which consists of solutions of a family of systems of equations with a parameter, (b) it can be started from an arbitrary (not necessarily positive) point in ℝ ²ⁿ in contrast to most of interior-point methods, and (c) its global convergence is ensured for a class of problems including (not strongly) monotone complementarity problems having a feasible interior point. To construct the algorithms, we give a homotopy and show the existence of a trajectory leading to a solution under a relatively mild condition, and propose a class of algorithms involving suitable neighborhoods of the trajectory. We also give a sufficient condition on the neighborhoods for global convergence and two examples satisfying it. Received April 9, 1997 / Revised version received September 2, 1998? Published online May 28, 1999     

The spectrum of partitions of a Boolean algebra

The main notion dealt with in this article is

The 0-1 Knapsack problem with a single continuous variable

Specifically we investigate the polyhedral structure of the knapsack problem with a single continuous variable, called the mixed 0-1 knapsack problem. First different classes of facet-defining inequalities are derived based on restriction and lifting. The order of lifting, particularly of the continuous variable, plays an important role. Secondly we show that the flow cover inequalities derived for the single node flow set, consisting of arc flows into and out of a single node with binary variable lower and upper bounds on each arc, can be obtained from valid inequalities for the mixed 0-1 knapsack problem. Thus the separation heuristic we derive for mixed knapsack sets can also be used to derive cuts for more general mixed 0-1 constraints. Initial computational results on a variety of problems are presented. Received May 22, 1997 / Revised version received December 22, 1997 Published online November 24, 1998     

Solving a class of semidefinite programs via nonlinear programming

In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of SDP relaxations of combinatorial optimization problems with binary variables as well as other important SDP problems. We also derive gradient formulas for the objective function of the resulting nonlinear optimization problem and show that both function and gradient evaluations have affordable complexities that effectively exploit the sparsity of the problem data. This transformation, together with the efficient gradient formulas, enables the solution of very large-scale SDP problems by gradient-based nonlinear optimization techniques. In particular, we propose a first-order log-barrier method designed for solving a class of large-scale linear SDP problems. This algorithm operates entirely within the space of the transformed problem while still maintaining close ties with both the primal and the dual of the original SDP problem. Global convergence of the algorithm is established under mild and reasonable assumptions. Received: January 5, 2000 / Accepted: October 2001?Published online February 14, 2002     

The many facets of linear programming

We examine the history of linear programming from computational, geometric, and complexity points of view, looking at simplex, ellipsoid, interior-point, and other methods. Received: June 22, 2000 / Accepted: April 4, 2001?Published online October 2, 2001     

The role of linear objective functions in barrier methods

Received December 10, 1994 / Revised version received April 29, 1998 Published online October 21, 1998     

The global linear convergence of an infeasible non-interior path-following algorithm for complementarity problems with uniform P-functions

We propose an infeasible non-interior path-following method for nonlinear complementarity problems with uniform P-functions. This method is based on the smoothing techniques introduced by Kanzow. A key to our analysis is the introduction of a new notion of neighborhood for the central path which is suitable for infeasible non-interior path-following methods. By restricting the iterates in the neighborhood of the central path, we provide a systematic procedure to update the smoothing parameter and establish the global linear convergence of this method. Some preliminary computational results are reported. Received: March 13, 1997 / Accepted: December 17, 1999?Published online February 23, 2000     

Self-injective rings and linear (weak) inverses of linear finite automata over rings

LetR be a finite commutative ring with identity and τ be a nonnegative integer. In studying linear finite automata, one of the basic problems is how to characterize the class of rings which have the property that every (weakly) invertible linear finite automaton ℳ with delay τ over R has a linear finite automaton ℳ′ over R which is a (weak) inverse with delay τ of ℳ. The rings and linear finite automata are studied by means of modules and it is proved that *-rings are equivalent to self-injective rings, and the unsolved problem (for τ=0) is solved. Moreover, a further problem of how to characterize the class of rings which have the property that every invertible with delay τ linear finite automaton ℳ overR has a linear finite automaton ℳ′ over R which is an inverse with delay τ′ for some τ′⩾τ is studied and solved. Project supported by the National Natural Science Foundation of China(Grant No. 69773015).     

Random Linkage: a family of acceptance/rejection algorithms for global optimisation

Received July 24, 1997 / Revised version received August 9, 1998 Published online January 20, 1999     

The volume algorithm: producing primal solutions with a subgradient method

We present an extension to the subgradient algorithm to produce primal as well as dual solutions. It can be seen as a fast way to carry out an approximation of Dantzig-Wolfe decomposition. This gives a fast method for producing approximations for large scale linear programs. It is based on a new theorem in linear programming duality. We present successful experience with linear programs coming from set partitioning, set covering, max-cut and plant location. Received: June 15, 1998 / Accepted: November 15, 1999?Published online March 15, 2000