A conjugate gradient algorithm for sparse linear inequalities

This paper presents a conjugate gradient method for solving systems of linear inequalities. The method is of dual optimization type and consists of two phases which can be implemented in a common framework. Phase 1 either finds the minimum-norm solution of the system or detects the inconsistency of the system. In the latter event, the method proceeds to Phase 2 in which an approximate least-squares solution to the system is obtained. The method is particularly suitable to large scale problems because it preserves the sparsity structure of the problem. Its efficiency is shown by computational comparisons with an SOR type method.     

A numerically stable least squares solution to the quadratic programming problem

The strictly convex quadratic programming problem is transformed to the least distance problem — finding the solution of minimum norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method, an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult problems.      

An LP-based heuristic for two-stage capacitated facility location problems

In this paper, a linear programming based heuristic is considered for a two-stage capacitated facility location problem with single source constraints. The problem is to find the optimal locations of depots from a set of possible depot sites in order to serve customers with a given demand, the optimal assignments of customers to depots and the optimal product flow from plants to depots. Good lower and upper bounds can be obtained for this problem in short computation times by adopting a linear programming approach. To this end, the LP formulation is iteratively refined using valid inequalities and facets which have been described in the literature for various relaxations of the problem. After each reoptimisation step, that is the recalculation of the LP solution after the addition of valid inequalities, feasible solutions are obtained from the current LP solution by applying simple heuristics. The results of extensive computational experiments are given.     

Computer-Algebra Implementation of the Least-Squares Method on the Nonnegative Orthant

Maple procedures for solving the so-called NNLS (Nonnegative Least Squares) problem are described. The NNLS problem is to minimize

Extensions of block-projections methods with relaxation parameters to inconsistent and rank-deficient least-squares problems

There exist many classes of block-projections algorithms for approximating solutions of linear least-squares problems. Generally, these methods generate sequences convergent to the minimal norm least-squares solution only for consistent problems. In the inconsistent case, which usually appears in practice because of some approximations or measurements, these sequences do no longer converge to a least-squares solution or they converge to the minimal norm solution of a “perturbed” problem. In the present paper, we overcome this difficulty by constructing extensions for almost all the above classes of block-projections methods. We prove that the sequences generated with these extensions always converge to a least-squares solution and, with a suitable initial approximation, to the minimal norm solution of the problem. Numerical experiments, described in the last section of the paper, confirm the theoretical results obtained.     

Creating Advanced Bases For Large Scale Linear Programs Exploiting Embedded Network Structure

In this paper, we investigate how an embedded pure network structure arising in many linear programming (LP) problems can be exploited to create improved sparse simplex solution algorithms. The original coefficient matrix is partitioned into network and non-network parts. For this partitioning, a decomposition technique can be applied. The embedded network flow problem can be solved to optimality using a fast network flow algorithm. We investigate two alternative decompositions namely, Lagrangean and Benders. In the Lagrangean approach, the optimal solution of a network flow problem and in Benders the combined solution of the master and the subproblem are used to compute good (near optimal and near feasible) solutions for a given LP problem. In both cases, we terminate the decomposition algorithms after a preset number of passes and active variables identified by this procedure are then used to create an advanced basis for the original LP problem. We present comparisons with unit basis and a well established crash procedure. We find that the computational results of applying these techniques to a selection of Netlib models are promising enough to encourage further research in this area.     

A revisit of numerical approach for solving linear fractional programming problem in a fuzzy environment

In the article, Veeramani and Sumathi [10] presented an interesting algorithm to solve a fully fuzzy linear fractional programming (FFLFP) problem with all parameters as well as decision variables as triangular fuzzy numbers. They transformed the FFLFP problem under consideration into a bi-objective linear programming (LP) problem, which is then converted into two crisp LP problems. In this paper, we show that they have used an inappropriate property for obtaining non-negative fuzzy optimal solution of the same problem which may lead to the erroneous results. Using a numerical example, we show that the optimal fuzzy solution derived from the existing model may not be non-negative. To overcome this shortcoming, a new constraint is added to the existing fuzzy model that ensures the fuzzy optimal solution of the same problem is a non-negative fuzzy number. Finally, the modified solution approach is extended for solving FFLFP problems with trapezoidal fuzzy parameters and illustrated with the help of a numerical example.     

Computing an interior point for inequalities using linear optimization

The problem of finding the middle of a feasible region defined by solutions to a set of linear inequalities is considered. The solution of this problem is formulated as a primal-dual pair of linear optimization problems whose solutions can be obtained using linear programming computations.     

Studying the stability of solutions to systems of linear inequalities and constructing separating hyperplanes

We consider the methods for matrix correction or correction of all parameters of systems of linear equations and inequalities. We show that the problem of matrix correction of an inconsistent system of linear inequalities with the nonnegativity condition is reduced to a linear programming problem. Some stability measure is defined for a given solution to a system of linear inequalities as the minimal possible variation of parameters under which this solution does not satisfy the system. The problem of finding the most stable solution to the system is considered. The results are applied to constructing an optimal separating hyperplane in the feature space that is the most stable to the changes of features of the objects.     

An Exact Solution to Linear Programming Using an Interior Point Method

This paper presents sufficient conditions for optimality of the Linear programming (LP) problem in the neighborhood of an optimal solution, and applies them to an interior point method for solving the LP problem. We show that after a finite number of iterations, an exact solution to the LP problem is obtained by solving a linear system of equations under the assumptions that the primal and dual problems are both nondegenerate, and that the minimum value is bounded. If necessary, the dual solution can also be found.     

Projection methods for the linear split feasibility problems

Some optimization problems can be reduced to finding a solution of a system of linear inequalities which belongs to a closed convex subset. In some optimization methods such a solution (or at least a better approximation of such a solution than the current one) should be found in each iteration. In the article, we present various projection methods to solve this problem. Furthermore, we show the relationship between these methods. We show that all presented methods can be reduced to the surrogate constraints method.     

Polynomial-time identification of robust network flows under uncertain arc failures

We propose Linear Programming (LP)-based solution methods for network flow problems subject to multiple uncertain arc failures, which allow finding robust optimal solutions in polynomial time under certain conditions. We justify this fact by proving that for the considered class of problems under uncertainty with linear loss functions, the number of entities in the corresponding LP formulations is polynomial with respect to the number of arcs in the network. The proposed formulation is efficient for sparse networks, as well as for time-critical networked systems, where quick and robust decisions play a crucial role.     

Convex optimization problems with arbitrary right-hand side perturbations

The problem of finding a solution to a system of mixed variational inequalities, which can be interpreted as a generalization of a primal–dual formulation of an optimization problem under arbitrary right-hand side perturbations, is considered. A number of various equilibrium type problems are particular cases of this problem. We suggest the problem to be reduced to a class of variational inequalities and propose a general descent type method to find its solution. If the primal cost function does not possess strengthened convexity properties, this descent method can be combined with a partial regularization method.     

Uniform saturation in linear inequality systems

Redundant constraints in linear inequality systems can be characterized as those inequalities that can be removed from an arbitrary linear optimization problem posed on its solution set without modifying its value and its optimal set. A constraint is saturated in a given linear optimization problem when it is binding at the optimal set. Saturation is a property related with the preservation of the value and the optimal set under the elimination of the given constraint, phenomena which can be seen as weaker forms of excess information in linear optimization problems. We say that an inequality of a given linear inequality system is uniformly saturated when it is saturated for any solvable linear optimization problem posed on its solution set. This paper characterizes the uniform saturated inequalities and other related classes of inequalities. This work was supported by the MCYT of Spain and FEDER of UE, Grant BFM2002-04114-C02-01.     

Ramsey theory and integrality gap for the independent set problem

We discuss the effectiveness of integer programming for solving large instances of the independent set problem. Typical LP formulations, even strengthened by clique inequalities, yield poor bounds for this problem. We show that a strong bound can be obtained by the use of the so-called rank inequalities, which generalize the clique inequalities. For some problems the clique inequalities imply the rank inequalities, and then a strong bound is guaranteed already by the simpler formulation.     

Analyzing linear systems containing strict inequalities via evenly convex hulls

The evenly convex hull of a given set is the intersection of all the open halfspaces which contain such set (hence the convex hull is contained in the evenly convex hull). This paper deals with finite dimensional linear systems containing strict inequalities and (possibly) weak inequalities as well as equalities. The number of inequalities and equalities in these systems is arbitrary (possibly infinite). For such kind of systems a consistency theorem is provided and those strict inequalities (weak inequalities, equalities) which are satisfied for every solution of a given system are characterized. Such results are formulated in terms of the evenly convex hull of certain sets which depend on the coefficients of the system.     

Polyhedral results for the edge capacity polytope

Network loading problems occur in the design of telecommunication networks, in many different settings. For instance, bifurcated or non-bifurcated routing (also called splittable and unsplittable) can be considered. In most settings, the same polyhedral structures return. A better understanding of these structures therefore can have a major impact on the tractability of polyhedral-guided solution methods. In this paper, we investigate the polytopes of the problem restricted to one arc/edge of the network (the undirected/directed edge capacity problem) for the non-bifurcated routing case.?As an example, one of the basic variants of network loading is described, including an integer linear programming formulation. As the edge capacity problems are relaxations of this network loading problem, their polytopes are intimately related. We give conditions under which the inequalities of the edge capacity polytopes define facets of the network loading polytope. We describe classes of strong valid inequalities for the edge capacity polytopes, and we derive conditions under which these constraints define facets. For the diverse classes the complexity of lifting projected variables is stated.?The derived inequalities are tested on (i) the edge capacity problem itself and (ii) the described variant of the network loading problem. The results show that the inequalities substantially reduce the number of nodes needed in a branch-and-cut approach. Moreover, they show the importance of the edge subproblem for solving network loading problems. Received: September 2000 / Accepted: October 2001?Published online March 27, 2002     

A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem

We present a factor 2 approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut. This class of problems includes, among others, the generalized Steiner network problem, which is also known as the survivable network design problem. Our algorithm first solves the linear relaxation of this problem, and then iteratively rounds off the solution. The key idea in rounding off is that in a basic solution of the LP relaxation, at least one edge gets included at least to the extent of half. We include this edge into our integral solution and solve the residual problem. Received March 6, 1998     

On the Gap Functions of Prevariational Inequalities

Gap functions play a crucial role in transforming a variational inequality problem into an optimization problem. Then, methods solving an optimization problem can be exploited for finding a solution of a variational inequality problem. It is known that the so-called prevariational inequality is closely related to some generalized convex functions, such as linear fractional functions. In this paper, gap functions for several kinds of prevariational inequalities are investigated. More specifically, prevariational inequalities, extended prevariational inequalities, and extended weak vector prevariational inequalities are considered. Furthermore, a class of gap functions for inequality constrained prevariational inequalities is investigated via a nonlinear Lagrangian.