TITLE

A regularized simplex method

AUTHOR(S)
Fábián, Csaba; Eretnek, Krisztián; Papp, Olga
PUB. DATE
December 2015
SOURCE
Central European Journal of Operations Research;Dec2015, Vol. 23 Issue 4, p877
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
In case of a special problem class, the simplex method can be implemented as a cutting-plane method that approximates a polyhedral convex objective function. In this paper we consider a regularized version of this cutting-plane method, and interpret the resulting procedure as a regularized simplex method. (Regularization is performed in the dual space and only affects the process through the pricing mechanism. Hence the resulting method moves among basic solutions.) We present algorithmic details of this regularized simplex method, and favorable test results with our implementation. For general linear programming problems, we propose a Newton-type approach which requires the solution of a sequence of special problems.
ACCESSION #
110674094

 

Related Articles

  • A FPTAS for a class of linear multiplicative problems. Depetrini, Daniele; Locatelli, Marco // Computational Optimization & Applications;Nov2009, Vol. 44 Issue 2, p275 

    In this paper we consider the problem of minimizing the product of two affine functions over a polyhedral set. An approximation algorithm is proposed and it is proved that it is a Fully Polynomial Time Approximation Scheme. We will also present and computationally investigate an exact version of...

  • A SUPERLINEARLY CONVERGENT ALGORITHM FOR ONE-DIMENSIONAL CONSTRAINED MINIMIZATION PROBLEMS WITH CONVEX FUNCTIONS. Mifflin, Robert // Mathematics of Operations Research;May83, Vol. 8 Issue 2, p185 

    This paper presents a globally and superlinearly convergent algorithm for solving one-dimensional constrained minimization problems involving (not necessarily smooth) convex functions. The constraint is handled by what can be interpreted as a new type of penalty method. The algorithm does not...

  • On degeneracy in linear programming and related problems. George, Karen; Osborae, M. R. // Annals of Operations Research;1993, Vol. 46/47 Issue 1-4, p343 

    Methods related to Wolfe's recursive method for the resolution of degeneracy in linear programming are discussed, and a nonrecursive variant which works with probability one suggested. Numerical results for both nondegenerate problems and problems constructed to have degenerate optima are...

  • Disjunctive programming and relaxations of polyhedra. Conforti, Michele; Del Pia, Alberto // Mathematical Programming;Apr2014, Vol. 144 Issue 1/2, p307 

    Given a polyhedron $$L$$ with $$h$$ facets, whose interior contains no integral points, and a polyhedron $$P$$, recent work in integer programming has focused on characterizing the convex hull of $$P$$ minus the interior of $$L$$. We show that to obtain such a characterization it suffices to...

  • A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Oberdieck, Richard; Wittmann-Hohlbein, Martina; Pistikopoulos, Efstratios // Journal of Global Optimization;Jul2014, Vol. 59 Issue 2/3, p527 

    In this paper, we present a novel algorithm for the solution of multiparametric mixed integer linear programming (mp-MILP) problems that exhibit uncertain objective function coefficients and uncertain entries in the right-hand side constraint vector. The algorithmic procedure employs a branch...

  • DCA based algorithms for multiple sequence alignment (MSA). Le Thi, Hoai; Pham Dinh, Tao; Belghiti, Moulay // Central European Journal of Operations Research;Sep2014, Vol. 22 Issue 3, p501 

    In the last years many techniques in bioinformatics have been developed for the central and complex problem of optimally aligning biological sequences. In this paper we propose a new optimization approach based on DC (Difference of Convex functions) programming and DC Algorithm (DCA) for the...

  • Relaxed Viscosity Approximation Methods with Regularization for Constrained Minimization Problems. Lu-Chuan Ceng; Hong-Kun Xu; Ching-Feng Wen // Journal of Applied Mathematics;2013, p1 

    We introduce a new relaxed viscosity approximation method with regularization and prove the strong convergence of the method to a common fixed point of finitely many nonexpansive mappings and a strict pseudocontraction that also solves a convex minimization problem and a suitable equilibrium...

  • On Polyhedral Projection and Parametric Programming. Jones, C. N.; Kerrigan, E. C.; Maciejowski, J. M. // Journal of Optimization Theory & Applications;Aug2008, Vol. 138 Issue 2, p207 

    This paper brings together two fundamental topics: polyhedral projection and parametric linear programming. First, it is shown that, given a parametric linear program (PLP), a polyhedron exists whose projection provides the solution to the PLP. Second, the converse is tackled and it is shown how...

  • Tight polyhedral approximation for mixed-integer linear programming unit commitment formulations. Jabr, R. A. // IET Generation, Transmission & Distribution;Nov2012, Vol. 6 Issue 11, p1104 

    The perspective reformulation has been recently proposed for constructing tight relaxations of the unit commitment (UC) problem with quadratic cost functions. In this case, it has been shown that the perspective reformulation can be cast as a second-order cone program. Conic quadratic...

Share

Read the Article

Courtesy of THE LIBRARY OF VIRGINIA

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics