Stronger Lower Bounds for the Quadratic Minimum Spanning Tree Problem with Adjacency Costs

We address a particular case of the quadratic minimum spanning tree problem in which interaction costs only apply for adjacent edges. Motivated by the fact that Gilmore-Lawler procedures in the literature underestimate the contribution of interaction costs to compute lower bounds, we introduce a reformulation that allows stronger linear programming bounds to be computed. An algorithm based on dynamic column and row generation is presented for evaluating these bounds. Our computational experiments indicate that the reformulation introduced here is indeed much stronger than those in the literature.     

Matrix pencils completion problems

In this paper we give a partial solution to the challenge problem posed by Loiseau et al. in [J. Loiseau, S. Mondié, I. Zaballa, P. Zagalak, Assigning the Kronecker invariants of a matrix pencil by row or column completion, Linear Algebra Appl. 278 (1998) 327-336], i.e. we assign the Kronecker invariants of a matrix pencil obtained by row or column completion. We have solved this problem over arbitrary fields.     

A NUMERICALLY STABLE BLOCK MODIFIED GRAM-SCHMIDT ALGORITHM FOR SOLVING STIFF WEIGHTED LEAST SQUARES PROBLEMS

Recently, Wei in proved that perturbed stiff weighted pseudoinverses and stiff weighted least squares problems are stable, if and only if the original and perturbed coefficient matrices A and A^- satisfy several row rank preservation conditions. According to these conditions, in this paper we show that in general, ordinary modified Gram-Schmidt with column pivoting is not numerically stable for solving the stiff weighted least squares problem. We then propose a row block modified Gram-Schmidt algorithm with column pivoting, and show that with appropriately chosen tolerance, this algorithm can correctly determine the numerical ranks of these row partitioned sub-matrices, and the computed QR factor R^- contains small roundoff error which is row stable. Several numerical experiments are also provided to compare the results of the ordinary Modified Gram-Schmidt algorithm with column pivoting and the row block Modified Gram-Schmidt algorithm with column pivoting.     

QR factorization for row or column symmetric matrix

The problem of fast computing the QR factorization of row or column symmetric matrix is considered. We address two new algorithms based on a correspondence of Q and R matrices between the row or column symmetric matrix and its mother matrix. Theoretical analysis and numerical evidence show that, for a class of row or column symmetric matrices, the QR factorization using the mother matrix rather than the row or column symmetric matrix per se can save dramatically the CPU time and memory without loss of any numerical precision.     

On some methods for entropy maximization and matrix scaling

We describe and survey in this paper iterative algorithms for solving the discrete maximum entropy problem with linear equality constraints. This problem has applications e.g. in image reconstruction from projections, transportation planning, and matrix scaling. In particular we study local convergence and asymptotic rate of convergence as a function of the iteration parameter. For the trip distribution problem in transportation planning and the equivalent problem of scaling a positive matrix to achieve a priori given row and column sums, it is shown how the iteration parameters can be chosen in an optimal way. We also consider the related problem of finding a matrix X, diagonally similar to a given matrix, such that corresponding row and column norms in X are all equal. Reports of some numerical tests are given.     

A shortest path-based approach to the multileaf collimator sequencing problem

The multileaf collimator sequencing problem is an important component in effective cancer treatment delivery. The problem can be formulated as finding a decomposition of an integer matrix into a weighted sequence of binary matrices whose rows satisfy a consecutive ones property. Minimising the cardinality of the decomposition is an important objective and has been shown to be strongly NP-hard, even for a matrix restricted to a single column or row. We show that in this latter case it can be solved efficiently as a shortest path problem, giving a simple proof that the one-row problem is fixed-parameter tractable in the maximum intensity. We develop new linear and constraint programming models exploiting this result. Our approaches significantly improve the best known for the problem, bringing real-world sized problem instances within reach of exact algorithms.     

Transportation matrices with staircase patterns and majorization

We consider some questions concerning transportation matrices with a certain nonzero pattern. For a given staircase pattern we characterize those row sum vectors R and column sum vectors S such that the corresponding class of transportation matrices with the given row and column sums and the given pattern is nonempty. Two versions of this problem are considered. Algorithms for finding matrices in these matrix classes are introduced and, finally, a connection to the notion of majorization is discussed.     

Going Off the Grid: Iterative Model Selection for Biclustered Matrix Completion

We consider the problem of performing matrix completion with side information on row-by-row and column-by-column similarities. We build upon recent proposals for matrix estimation with smoothness constraints with respect to row and column graphs. We present a novel iterative procedure for directly minimizing an information criterion to select an appropriate amount of row and column smoothing, namely, to perform model selection. We also discuss how to exploit the special structure of the problem to scale up the estimation and model selection procedure via the Hutchinson estimator, combined with a stochastic Quasi-Newton approach. Supplementary material for this article is available online.     

On local w-uniqueness of solutions to linear complementarity problem

We introduce the classes of column (row) competent matrices and prove that the local w-uniqueness of solutions to linear complementarity problem can be completely characterized by column competent matrices.     

Exact methods for large-scale multi-period financial planning problems

A relevant financial planning problem is the periodical rebalance of a portfolio of assets such that the portfolio’s total value exhibits certain characteristics. This problem can be modelled using a transition graph G to represent the future state space evolution of the corresponding economy and mathematically formulated as a linear programming problem. We present two different mathematical formulations of the problem. The first considers explicitly the set of the possible scenarios (scenario-based approach), while the second considers implicitly the whole set of scenarios provided by the graph G (graph-based approach). Unfortunately, for both the formulations the size of the corresponding linear programs can be huge even for simple financial problems. However, the graph-based approach seems to be a more powerful model, since it allows to consider a huge number of scenarios in a very compact formulation. The purpose of this paper is to present both heuristic and exact methods for the solution of large-scale multi-period financial planning problems using the graph-based model. In particular, in this paper we propose lower and upper bounds and three exact methods based on column, row and column/row generation, respectively. Since the methods based on column/row generation exploits simultaneously both the primal and the dual structure of the problem we call it Criss-Cross generation method. Computational results are given to prove the effectiveness of the proposed methods.      

On the convergence of the block principal pivotal algorithm for the LCP

We show that the block principal pivot algorithm (BPPA) for the linear complementarity problem (LCP) solves the problem for a special class of matrices in at most n block principal pivot steps. We provide cycling examples for the BPPA in which the matrix is positive definite or symmetric positive definite. For LCP of order three, we prove that strict column (row) diagonal dominance is a sufficient condition to avoid cycling.     

Integer matrices with constraints on leading partial row and column sums

Consider the problem of finding an integer matrix that satisfies given constraints on its leading partial row and column sums. For the case in which the specified constraints are merely bounds on each such sum, an integer linear programming formulation is shown to have a totally unimodular constraint matrix. This proves the polynomial-time solvability of this case. In another version of the problem, one seeks a zero-one matrix with prescribed row and column sums, subject to certain near-equality constraints, namely, that all leading partial row (respectively, column) sums up through a given column (respectively, row) are within unity of each other. This case admits a polynomial reduction to the preceding case, and an equivalent reformulation as a maximum-flow problem. The results are developed in a context that relates these two problems to consistent matrix rounding.     

A new infinite family of minimally nonideal matrices

Minimally nonideal matrices are a key to understanding when the set covering problem can be solved using linear programming. The complete classification of minimally nonideal matrices is an open problem. One of the most important results on these matrices comes from a theorem of Lehman, which gives a property of the core of a minimally nonideal matrix. Cornuéjols and Novick gave a conjecture on the possible cores of minimally nonideal matrices. This paper disproves their conjecture by constructing a new infinite family of square minimally nonideal matrices. In particular, we show that there exists a minimally nonideal matrix with r ones in each row and column for any r?3.     

On the row merge tree for sparse LU factorization with partial pivoting

We consider the problem of structure prediction for sparse LU factorization with partial pivoting. In this context, it is well known that the column elimination tree plays an important role for matrices satisfying an irreducibility condition, called the strong Hall property. Our primary goal in this paper is to address the structure prediction problem for matrices satisfying a weaker assumption, which is the Hall property. For this we consider the row merge matrix, an upper bound that contains the nonzeros in L and U for all possible row permutations that can be performed during the numerical factorization with partial pivoting. We discuss the row merge tree, a structure that represents information obtained from the row merge matrix; that is, information on the dependencies among the columns in Gaussian elimination with partial pivoting and on structural upper bounds of the factors L and U. We present new theoretical results that show that the nonzero structure of the row merge matrix can be described in terms of branches and subtrees of the row merge tree. These results lead to an efficient algorithm for the computation of the row merge tree, that uses as input the structure of A, and has a time complexity almost linear in the number of nonzeros in A. We also investigate experimentally the usage of the row merge tree for structure prediction purposes on a set of matrices that satisfy only the Hall property. We analyze in particular the size of upper bounds of the structure of L and U, the reordering of the matrix based on a postorder traversal and its impact on the factorization runtime. We show experimentally that for some matrices, the row merge tree is a preferred alternative to the column elimination tree. AMS subject classification (2000)  65F50, 65F05, 68R10     

A capacity scaling heuristic for the multicommodity capacitated network design problem

In this paper, we propose a capacity scaling heuristic using a column generation and row generation technique to address the multicommodity capacitated network design problem. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs. By combining a column and row generation technique and a strong formulation including forcing constraints, this heuristic derives high quality results, and computational effort can be reduced considerably. The capacity scaling heuristic offers one of the best current results among approximate solution algorithms designed to address the multicommodity capacitated network design problem.     

A unifying model for matrix-based pairing situations

We present a unifying framework for transferable utility coalitional games that are derived from a non-negative matrix in which every entry represents the value obtained by combining the corresponding row and column. We assume that every row and every column is associated with a player, and that every player is associated with at most one row and at most one column. The instances arising from this framework are called pairing games, and they encompass assignment games and permutation games as two polar cases. We show that the core of a pairing game is always non-empty by proving that the set of pairing games coincides with the set of permutation games. Then we exploit the wide range of situations comprised in our framework to investigate the relationship between pairing games that have different player sets, but are defined by the same underlying matrix. We show that the core and the set of extreme core allocations are immune to the merging of a row player with a column player. Moreover, the core is also immune to the reverse manipulation, i.e., to the splitting of a player into a row player and a column player. Other common solution concepts fail to be either merging-proof or splitting-proof in general.     

Global s-type error bound for the extended linear complementarity problem and applications

For the extended linear complementarity problem over an affine subspace, we first study some characterizations of (strong) column/row monotonicity and (strong) R ₀-property. We then establish global s-type error bound for this problem with the column monotonicity or R ₀-property, especially for the one with the nondegeneracy and column monotonicity, and give several equivalent formulations of such error bound without the square root term for monotone affine variational inequality. Finally, we use this error bound to derive some properties of the iterative sequence produced by smoothing methods for solving such a problem under suitable assumptions. Received: May 2, 1999 / Accepted: February 21, 2000?Published online July 20, 2000     

Generalized fuzzy matrices

We give a systematic development of fuzzy matrix theory. Many of our results generalize to matrices over the two element Boolean algebra, over the nonnegative real numbers, over the nonnegative integers, and over the semirings, and we present these generalizations. Our first main result is that while spaces of fuzzy vectors do not have a unique basis in general they have a unique standard basis, and the cardinality of any two bases are equal. Thus concepts of row and column basis, row and column rank can be defined for fuzzy matrices. Then we study Green's equivalence classes of fuzzy matrices. New we give criteria for a fuzzy matrix to be regular and prove that the row and column rank of any regular fuzzy matrix are equal. Various inverses are also studied. In the next section, we obtain bounds for the index and period of a fuzzy matrix.     

Using graphs for some discrete tomography problems

Given a rectangular array whose entries represent the pixels of a digitalized image, we consider the problem of reconstructing an image from the number of occurrences of each color in every column and in every row. The complexity of this problem is still open when there are just three colors in the image. We study some special cases where the number of occurrences of each color is limited to small values. Formulations in terms of edge coloring in graphs and as timetabling problems are used; complexity results are derived from the model.     

An Improvement to Goyal's Modified VAM for the Unbalanced Transportation Problem

This note points out how Goyal's modification of Vogel's approximation method for the unbalanced transportation problem can be improved by subtracting or adding suitable constants to the rows and columns of the cost matrix. We subtract column minima before applying Goyal's technique, and then subtract row/column minima before the application of VAM.