An unconstrained convex programming view of linear programming

The major interest of this paper is to show that, at least in theory, a pair of primal and dual -optimal solutions to a general linear program in Karmarkar's standard form can be obtained by solving an unconstrained convex program. Hence unconstrained convex optimization methods are suggested to be carefully reviewed for this purpose.     

An integer linear programming approach for bilinear integer programming

We introduce a new Integer Linear Programming (ILP) approach for solving Integer Programming (IP) problems with bilinear objectives and linear constraints. The approach relies on a series of ILP approximations of the bilinear IP. We compare this approach with standard linearization techniques on random instances and a set of real-world product bundling problems.     

An efficient algorithm for linear programming

A simple but efficient algorithm is presented for linear programming. The algorithm computes the projection matrix exactly once throughout the computation unlike that of Karmarkar’s algorithm where in the projection matrix is computed at each and every iteration. The algorithm is best suitable to be implemented on a parallel architecture. Complexity of the algorithm is being studied.     

An algorithm for bicriterion linear programming

An algorithm is presented here for bicriterion linear programs which generates either all efficient points or a subset of such efficient points corresponding to a decision-maker's specified space of objective weights. The computational requirements of the algorithm are quite low; in fact only a series of divisions and comparisons are needed for the determination of adjacent efficient extreme points. As a by-product, the range of objective weights corresponding to each efficient extreme point is also generated. This additional information is used to characterize the set of all efficient points as a union of maximal efficient faces.     

An infeasible-interior-point potential-reduction algorithm for linear programming

n . The method is based on Rockafellar’s proximal point algorithm and a cutting-plane technique. At each step, we use an approximate proximal point p^a(x_k) of x_k to define a v_k∈∂_εkf(p^a(x_k)) with ε_k≤α∥v_k∥, where α is a constant. The method monitors the reduction in the value of ∥v_k∥ to identify when a line search on f should be used. The quasi-Newton step is used to reduce the value of ∥v_k∥. Without the differentiability of f, the method converges globally and the rate of convergence is Q-linear. Superlinear convergence is also discussed to extend the characterization result of Dennis and Moré. Numerical results show the good performance of the method. Received October 3, 1995 / Revised version received August 20, 1998 Published online January 20, 1999     

An adaptation of Priam to multiobjective linear programming

In this paper we present an algorithm for multiobjective linear programming. In this algorithm the decision maker directs an interactive exploration of the feasible set relying on the ‘problem solving’ ideas which were developed in artificial intelligence. This method is an adaptation to linear programming of the discrete multi-attribute Priam algorithm     

An implementation of Karmarkar's algorithm for linear programming

This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.     

Solving stochastic dynamic programming problems by linear programming — An annotated bibliography

Summary As has been known for a long time, stochastic dynamic decision processes with finite state and action spaces can be handled by policy and value iteration, both typical dynamic programming techniques, as well as by linear programming. In the present paper, the most important results concerning the latter are reported and an outlook on more general settings is given.

---

Zusammenfassung Seit langem ist bekannt, daß zur Optimierung stochastischer dynamischer Entscheidungsprozesse im Falle endlicher Zustands- und Aktionenräume neben den für die dynamische Optimierung typischen Verfahren der Politik- und Wertiteration auch die lineare Programmierung herangezogen werden kann. In der vorliegenden Arbeit werden die wichtigsten diesbezüglichen Resultate referiert und ein Ausblick auf allgemeinere Ansätze gegeben.

     

An interior point algorithm for semi-infinite linear programming

We consider the generalization of a variant of Karmarkar's algorithm to semi-infinite programming. The extension of interior point methods to infinite-dimensional linear programming is discussed and an algorithm is derived. An implementation of the algorithm for a class of semi-infinite linear programs is described and the results of a number of test problems are given. We pay particular attention to the problem of Chebyshev approximation. Some further results are given for an implementation of the algorithm applied to a discretization of the semi-infinite linear program, and a convergence proof is given in this case.     

An entire space polynomial-time algorithm for linear programming

We propose an entire space polynomial-time algorithm for linear programming. First, we give a class of penalty functions on entire space for linear programming by which the dual of a linear program of standard form can be converted into an unconstrained optimization problem. The relevant properties on the unconstrained optimization problem such as the duality, the boundedness of the solution and the path-following lemma, etc, are proved. Second, a self-concordant function on entire space which can be used as penalty for linear programming is constructed. For this specific function, more results are obtained. In particular, we show that, by taking a parameter large enough, the optimal solution for the unconstrained optimization problem is located in the increasing interval of the self-concordant function, which ensures the feasibility of solutions. Then by means of the self-concordant penalty function on entire space, a path-following algorithm on entire space for linear programming is presented. The number of Newton steps of the algorithm is no more than $O(nL\log (nL/ {\varepsilon }))$ , and moreover, in short step, it is no more than $O(\sqrt{n}\log (nL/{\varepsilon }))$ .     

An improved general Phase-I method in linear programming

In a recent paper on general Phase-I methods in linear programming a procedure was suggested that minimizes the amount of infeasibility allowing the number of infeasibilities to increase. Though the procedure improves the overall performance of the Phase-I Simplex method by reducing the number of pivot steps, its main drawback is the extra computational effort required. In this paper it will be shown theoretically and computationally that in most cases this computational effort can be reduced significantly.     

A linear programming approach for linear multi-level programming problems

In an earlier paper, we proposed a modified fuzzy programming method to handle higher level multi-level decentralized programming problems (ML(D)PPs). Here we present a simple and practical method to solve the same. This method overcomes the subjectivity inherent in choosing the tolerance values and the membership functions. We consider a linear ML(D)PP and apply linear programming (LP) for the optimization of the system in a supervised search procedure, supervised by the higher level decision maker (DM). The higher level DM provides the preferred values of the decision variables under his control to enable the lower level DM to search for his optimum in a narrower feasible space. The basic idea is to reduce the feasible space of a decision variable at each level until a satisfactory point is sought at the last level.     

Understanding linear semi-infinite programming via linear programming over cones

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.     

An effective linear approximation method for separable programming problems

Among the numerous applications of piecewise linearization methods include data fitting, network analysis, logistics, and statistics. In the early 1950s, a concave function was found to be able to be linearized by introducing 0-1 variables. Most textbooks in Operations Research offer such methods for expressing linear approximations. Various methods of linearization have also been developed in recent literature. Nevertheless, the transformed linear scheme has a severe shortcoming: most standard procedures for linearizing typically involve a large increase in the number of binary variables. Consequently, the gains to be derived from dealing with linear functions are quite likely to be nullified by the increase in the size of the problem.Conventional methods for linearizing a concave function with m break points require m-1 binary variables. However, when m becomes large, the computation will be very time-consuming and may cause a heavy computational burden.This study proposes an effective approach in which only ⌈log₂(m-1)⌉ binary variables are used. The proposed method has the following features: (i) it offers more convenient and efficient means of expressing a piecewise linear function; (ii) fewer 0-1 variables are used; (iii) the computational results show that the proposed method is much more efficient and faster than the conventional one, especially when the number of break points becomes large.     

An integer linear programming approach for approximate string comparison

We introduce a problem called maximum common characters in blocks (MCCB), which arises in applications of approximate string comparison, particularly in the unification of possibly erroneous textual data coming from different sources. We show that this problem is NP-complete, but can nevertheless be solved satisfactorily using integer linear programming for instances of practical interest. Two integer linear formulations are proposed and compared in terms of their linear relaxations. We also compare the results of the approximate matching with other known measures such as the Levenshtein (edit) distance.     

An efficient linear programming solver for optimal filter synthesis

We consider the problem of l_∞ optimal deconvolution arising in high data‐rate communication between integrated circuits. The optimal deconvolver can be found by solving a linear program for which we use Mehrotra's interior‐point approach. The critical step is solving the linear system for the normal equations in each iteration. We show that this linear system has a special block structure that can be exploited to obtain a fast solution technique whose overall computational cost depends mostly on the number of design variables, and only linearly on the number of constraints. Numerical experiments validate our findings and illustrate the merits of our approach. Copyright © 2007 John Wiley & Sons, Ltd.     

An MC2 linear programming approach to combined forecasting

Combined forecasting is a well-known forecasting technique of handling multiple forecasting methods. However, the previous combined forecasting approaches lack of incorporating the various possible opinions from several experts on an given forecasting problem. This paper proposes an MC² linear programming approach to determining weighted coefficients of combined forecasting that involves multiple experts. The numerical example of the paper shows that the proposed approach likely outperforms the current techniques of combined forecasting in dealing with the case of multiple experts.     

An interior-point piecewise linear penalty method for nonlinear programming

We present an interior-point penalty method for nonlinear programming (NLP), where the merit function consists of a piecewise linear penalty function and an ? ₂-penalty function. The piecewise linear penalty function is defined by a set of break points that correspond to pairs of values of the barrier function and the infeasibility measure at a subset of previous iterates and this set is updated at every iteration. The ? ₂-penalty function is a traditional penalty function defined by a single penalty parameter. At every iteration the step direction is computed from a regularized Newton system of the first-order equations of the barrier problem proposed in Chen and Goldfarb (Math Program 108:1?C36, 2006). Iterates are updated using a line search. In particular, a trial point is accepted if it provides a sufficient reduction in either of the penalty functions. We show that the proposed method has the same strong global convergence properties as those established in Chen and Goldfarb (Math Program 108:1?C36, 2006). Moreover, our method enjoys fast local convergence. Specifically, for each fixed small barrier parameter???, iterates in a small neighborhood (roughly within o(??)) of the minimizer of the barrier problem converge Q-quadratically to the minimizer. The overall convergence rate of the iterates to the solution of the nonlinear program is Q-superlinear.     

An efficient method for solving linear goal programming problems

This note proposes a solution algorithm for linear goal programming problems. The proposed method simplifies the traditional solution methods. Also, the proposed method is computationally efficient.     

An inexact approach to solving linear semi-infinite programming problems

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