Search

An algorithm to solve bi-objective quadratic fractional integer programming problems is presented in this paper. The algorithm uses -scalarization technique and a ranking approach of the integer feasible solution to find all nondominated points. In order to avoid solving non-linear integer programming problems during this ranking scheme, the existence of a linear or a linear fractional function is established, which acts as a lower bound on the values of first objective function of the bi-objective problem over the entire feasible set. Numerical examples are also presented in support of the theory.

To globally solve linear multiplicative programming problem (LMP), this paper presents a practicable branch-and-bound method based on the framework of branch-and-bound algorithm. In this method, a new linear relaxation technique is proposed firstly. Then, the branch-and-bound algorithm is developed for solving problem LMP. The proposed algorithm is proven that it is convergent to the global minimum by means of the subsequent solutions of a series of linear programming problems. Some experiments are reported to show the feasibility and efficiency of this algorithm.

This paper presents the convergence proof and complexity analysis of an interior-point framework that solves linear programming problems by dynamically selecting and adding relevant inequalities. First, we formulate a new primal–dual interior-point algorithm for solving linear programmes in non-standard form with equality and inequality constraints. The algorithm uses a primal–dual path-following predictor–corrector short-step interior-point method that starts with a reduced problem without any inequalities and selectively adds a given inequality only if it becomes active on the way to optimality. Second, we prove convergence of this algorithm to an optimal solution at which all inequalities are satisfied regardless of whether they have been added by the algorithm or not. We thus provide a theoretical foundation for similar schemes already used in practice. We also establish conditions under which the complexity of such algorithm is polynomial in the problem dimension and address remaining limitations without these conditions for possible further research.

In this paper, we describe three versions of a primal exterior point Simplex type algorithm for solving linear programming problems. Also, these algorithms are not affected mainly by scaling techniques. We compare their practical effectiveness versus the revised primal Simplex algorithm (our implementation) and the MATLAB’s implementations of Simplex and Interior Point Method. A computational study on randomly generated sparse linear programs is presented to establish the practical value of the proposed versions. The results are very encouraging and verify the superiority of the exterior point versions over the other algorithms either using scaling techniques or not.

The aim of this paper is to present an experimental investigation of a Primal–Dual Exterior Point Simplex Algorithm (PDEPSA) for Linear Programming problems (LPs). There was a huge gap between the theoretical worst-case complexity and practical performance of simplex type algorithms. PDEPSA traverses across the interior of the feasible region in an attempt to avoid combinatorial complexities of vertex following algorithms. In order to gain an insight into the practical behaviour of the proposed algorithm, we have performed some computational experiments. Our computational results demonstrate that PDEPSA is faster comparable with simplex algorithm and the primal exterior point algorithm. A clear advantage is obtained by PDEPSA in number of iterations and CPU time.

The problem of finding a deepest point (a ball centre) of a polyhedron is studied. A finite combinatorial interior point method is presented for this problem which yields an algorithm for linear programming. We conjecture that this is a strongly polynomial algorithm. Meanwhile developing the algorithm, several auxiliary results were found; among others, Gorokh and Werner’s algorithm for linear inequalities is slightly extended. Our numerical experiments with the problem detected bugs in a linear interior point solver used in MATLAB 6 Optimization Toolbox.

In this article, the standard primal and dual linear semi-infinite programming (DLSIP) problems are reformulated as linear programming (LP) problems over cones. Therefore, the dual formulation via the minimal cone approach, which results in zero duality gap for the primal–dual pair for LP problems over cones, can be applied to linear semi-infinite programming (LSIP) problems. Results on the geometry of the set of the feasible solutions for the primal LSIP problem and the optimality criteria for the DLSIP problem are also discussed.

This article studies linear programming problems in which all minors of maximal order of the coefficient matrix have the same sign. We analyse the relationship between a special structure of the non-degenerate dual feasible bases of a linear programming problem and the structure of its associated matrix. In the particular case in which the matrix has all minors of each order k with the same strict sign ϵ k , we provide a dual simplex revised method with good stability properties. In particular, this method can be applied to the totally positive linear programming problems, of great interest in many applications.

Motivated by the successful application of mathematical programming techniques to difficult machine learning problems, we seek solutions of concave minimization problems over polyhedral sets with minimum number of nonzero components. We that if such problems have a solution, they have a vertex solution with a minimal number of zeros. This includes linear programs and general linear complementarity problems. A smooth concave exponential approximation to a step function solves the minimumsupport problem exactly for a finite value of the smoothing parameter. A fast finite linear-programming-based iterative method terminates at a stationary point, which for many important real world problems provides very useful answers. Utilizing the complementarity property of linear programs and linear complementarity problems, an upper bound on the number of nonzeros can be obtained by solving a single convex minimization problem on a polyhedral set

This note is aimed to correct the strong duality theorem of previous paper regarding the continuous-time linear programming problems. The argument presented in the previous paper can only be used to prove the case of piecewise continuous functions in which the discontinuities are the left-continuities.

The partially-linear models can be successfully applied in economics and technology, which increases the interest in them. Every continuous partially-linear function with a finite number of linear parts can be presented by means of linear functions and maximum of the functions. We considear graph interpretation of this optimization problem. Partially-linear problems are commonly not only nondifferentiable but nonconvex, which makes their solution by standard optimization methods difficult. In this work we give the necessary and sufficient conditions for local optimality. An algorithm for solving such problems, based on the constructive optimization methods is suggested

In this paper a method for solving perfect systems of linear inequalities is presented. It is based on selecting and removing inessential constraints. This method is a strongly polynomial one for the class of systems of inequalities with a constant difference between the number of constraints and the number of variables.

An algorithm for addressing multiple objective linear programming (MOLP) problems is presented. The algorithm modifies the path-following primal-dual algorithm to MOLP problems by using the single objective algorithm to generate interior search directions and later combine them to derive a single direction along which to step to the next iterate. Combining the different interior search directions is done by interacting with a Decision Maker (DM) to obtain locally-relevant preference information for the value vectors along these directions. This preference information is then used to derive an approximation to the gradient of an implicity-known utility function, and using a projection of this gradient provides a direction gradient of an implicitly-known utility function, and using a projection of this gradient provides a direction vector along which we step to the next iterate. At each iteration the algorithm also generates boundary points that aid in deriving the combined search direction. We refer to the...

In this paper, we propose an “inexact solution” approach to deal with linear semi-infinite programming problems with finitely many variables and infinitely many constraints over a compact metric space. A general convergence proof with some numerical examples are given and the advantages of using this approach are discussed

In this paper, we study a general path-following model for linear programming. Generalized barrier functions for linear programming are defined to create an ideal interior trajectory for path-following. The key components required for a generic algorithm, including the moving directions and criterion of closeness are discussed. A generic path-following algorithm is proposed and sufficient conditions for convergence and polynomality proofs are derived.

We present in this paper a new multiobjective linear programming (MOLP) algorithm. The algorithm is based on modifying a variant of Karmarkar's algorithm known as the affine-scaling primal algorithm to multiobjective linear programming problems. This modification is accomplished by combining approximate gradients of the multiple objective functions together with what we refer to as anchoring points that allow us to generate a search direction and move toward the solution through the interior of the constraints polytope. In contrast, current multiobjective linear programming algorithms are using the simplex algorithm to generate a sequence of steps that follow the exterior of the constraints polytope toward the optimal solution. As MOLP problems grow in size, following an exterior trajectory may become prohibitively costly in terms of the number of iterations and the required interaction cycles with the Decision Maker. Following an interior trajectory may prove less sensitive to problem size as vertex info...

The bicriteria bottleneck linear programming problem is studied in this paper. The two criteria considered are concave bottleneck functions, and the feasible region is a non-empty convex polyhedron. It has been established that all the efficient pairs of values of the objective function can be attained at the extreme points of the feasible region. Based upon some related bottleneck linear programming problems and linear programming problems, a convergent algorithm to generate all the efficient pairs is proposed

This paper completes the treatment of the conical approach to linear programming, introducing a conical primal algorithm of linear programming. After some recalls and improvements of a previous paper dealing with such an approach, the algorithm is defined. A first convergence result is then proved, which, along with a series of lemmata, allows to prove that the algorithm terminates in a finite number of steps

An algorithm based on linear programming is proposed, which finds for an inconsistent system minimal corrections of the matrix and RHS vector among those providing its consistency

In a working paper Chang has introduced a simple method for the linear complementarity problem involving a nonnegative definite matrix, based on principal pivoting and the least-index rule of Bland. This method has two important special cases, namely the Criss-Cross methods for linear programming and for convex quadratic programming, invented later independently by Terlaky and Klafszky. The proof of Chang is very complicated. Terlaky and Klafszky provide much simpler proofs for the Criss-Cross method. We propose another simple proof for the Criss-Cross method for quadratic programming. It appears from an example by Roos that the number of pivots required by the Criss-Cross method may grow exponentially with the number of the constraints of the problem. We use two additional examples, due essentially to Fathi and Murty, to analyse the worst-case behaviour of the method.

In this paper so-called e-approximations for the efficiency set of vector minimization problems are defined. A general generating algorithm for such E-approximations is given which will be modified for linear continuous problems by means of the Dual Simplex Method.

In this paper we consider different classes of noneonvex quadratic problems that can be solved in polynomial time. We present an algorithm for the problem of minimizing the product of two linear functions over a polyhedron P in R n The complexity of the algorithm depends on the number of vertices of the projection of P onto the R 2 space. In the worst-case this algorithm requires an exponential number of steps but its expected computational time complexity is polynomial. In addition, we give a characterization for the number of isolated local minimum areas for problems on this form. Furthermore, we consider indefinite quadratic problems with variables restricted to be nonnegative. These problems can be solved in polynomial time if the number of negative eigenvalues of the associated symmetric matrix is fixed.

A NP-hard problem (P) of mixed-discrete linear programming is considered which consists in the minimization of a linear objective function subject to a special non-connected subset of an unbounded polymatroid. For this problem we describe three polynomial approximate algorithms including a greedy algorithm and a fully polynomial approximation scheme solving a special subproblem of (P).

For the solution of mixed integer convex programming problems with integer objective function an algorithm is established, which combines Kelley's cutting-plane provedure and Gomory's second algorithm. Under the assumptions to be made for these procedures a convergent algorithm results by introducing an additional cut. In this algorithm the number of constraints in the linear subproblems is bounded. In case of pure integer problems the algorithm becomes finite.

Our paper presents two new algorithms for solving linear programming problems. These algorithms are based on the convergent criss-cross method and on the idea of the “Hungarian Method”. Similarly to the primal-dual algorithm of Dantzig-Ford-Fulkerson, our algorithms improve a feasible (may be not basic) solution step by step, but we use Terlaky's convergent criss-cross method for solving the subproblems. Our algorithms solve linear programming problems in a finite number of steps (i.e. cycling cannot occur). We show that the primal and dual Simplex methods are special cases of our algorithms. In these Simplex methods we use Bland's pivoting rule only if the basic transformations are degenerate. By this we show how can one derive the primal or dual simplex method from Terlaky's criss-cross method.

The one constraint: general (non zero-one) integer progrmming problem is solvad by an algorithm "chat is a composition of a dynamic programming procedure and a branch and-bound algorithm: The procedura way be used for solving this type of problems (for example the renewal problem) or for calculating bounds in a beaach-aed-bound algorithre for several must probably the algorithm can be extended for other type of problems, for example for the several constraint linear integer programming problem, as it is suggested in paragraph 5.

Using a new bilinear programming formulation of the linear complementarity problem, we simplify Mangasabian's necessary and sufficient conditions under which these problems can be solved as linear programs. Our conditions are used to derive new special cases of linear complementarity problems that are solvable as linear programs. Finally, we indicate how they can be used to characterize matrix classes in complementarity theory.

An implementation of Karmarkar's algorithm is described which can be characterized by two features. On the one hand only approximate projections are used in determining directions of search and, secondly, variables which are likely to be non-basic are successively eliminated. We demonstrate by examples that the resulting algorithm lies favorable properties with regard to speed and stability.

It is shown, that the by Khacian in 1979 published Ellipsoid-algorithm for the solution of linear optimization problems is also polynomial on the set of operation { +, −, ∗, /