Yet another geometric programming dual algorithm

We describe an algorithm for the geometric programming dual problem which uses an adaptation of the generalized LP algorithm, proposed by Dantzig et al. twenty-five years ago for the chemical equilibrium problem, and show the slack primal constraints pose no numerical difficulties for this algorithm as they do for previous dual-based algorithms.     

A dual version of tardos's algorithm for linear programming

Recently, Eva Tardos developed an algorithm for solving the linear program min (cx:Ax = b, x ≥ 0 whose solution time is polynomial in the size of A, independent of the sizes of c and b. Her algorithm focuses on the dual LP and employs an approximation of the cost coefficients. Here we adopt what may be called a ‘dual approach’ in that if focuses on the primal LP. This dual approach has some significant differences from Tardo's approach which make the dual approach conceptually simpler.     

A primal—dual infeasible-interior-point algorithm for linear programming

As in many primal—dual interior-point algorithms, a primal—dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence.Part of this research was done when M. Kojima and S. Mizuno visited at the IBM Almaden Research Center. Partial support from the Office of Naval Research under Contract N00014-91-C-0026 is acknowledged.Supported by Grant-in-Aids for Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.Supported by Grant-in-Aids for Encouragement of Young Scientist (03740125) and Co-operative Research (03832017) of The Japan Ministry of Education, Science and Culture.     

A new dual problem for nondifferentiable convex programming

This paper gives a new dual problem for nondifferentiable convex programming and proves the properties of weak duality and strong duality and offers a necessary and sufficient condition of strong duality.     

A new polynomial-time algorithm for linear programming

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n ^3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n ^2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.     

A primal—dual affine-scaling potential-reduction algorithm for linear programming

We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

A contraction algorithm for the multiparametric integer linear programming problem

We designed and implemented an algorithm to solve the continuos right hand side multiparametric Integer Linear Programming (ILP) problem, that is to solve a family of ILP problems in which the problems are related by having identical objective and matrix coefficients. Our algorithm works by choosing an appropiate finite sequence of nonparametric Mixed Integer Linear Programming (MILP) problems in order to obtain a complete multiparametrical analysis. The algorithm may be implemented by using any software capable of solving MILP problems.     

A new linear programming approach and genetic algorithm for solving airline boarding problem

The airline industry is under intense competition to simultaneously increase efficiency and satisfaction for passengers and profitability and internal system benefit for itself. The boarding process is one way to achieve these objectives as it tends itself to adaptive changes. In order to increase the flying time of a plane, commercial airlines try to minimize the boarding time, which is one of the most lengthy parts of a plane’s turn time. To reduce boarding time, it is thus necessary to minimize the number of interferences between passengers by controlling the order in which they get onto the plane through a boarding policy. Here, we determine the passenger boarding problem and examine the different kinds of passenger boarding strategies and boarding interferences in a single aisle aircraft. We offer a new integer linear programming approach to reduce the passenger boarding time. A genetic algorithm is used to solve this problem. Numerical results show effectiveness of the proposed algorithm.     

A sequential dual simplex algorithm for the linear assignment problem

We present a sequential dual-simplex algorithm for the linear problem which has the same complexity as the algorithms of Balinski [3,4] and Goldfarb [8]: O(n²) pivots, O(n² log n + nm) time. Our algorithm works with the (dual) strongly feasible trees and can handle rectangular systems quite naturally.     

A dual approach to solve the fuzzy linear programming problem

A concept of fuzzy objective based on the Fuzzification Principle is presented. In accordance with this concept, the Fuzzy Linear Mathematical Programming problem is easily solved. A relationship of duality among fuzzy constraints and fuzzy objectives is given. The dual problem of a Fuzzy Linear Programming problem is also defined.     

On properties of the probabilistic constrained linear programming problem and its dual

In this paper, the two problems inf{inf{cx:x R ⁿ,A ₁ xy,A ₂ xb}:y suppF R ^m,F(y)p} and sup{inf{uy:y suppF R ^m,F(y)p}+vb:uA ₁+vA ₂=c, (u,v0} are investigated, whereA ₁,A ₂,b,c are given matrices and vectors of finite dimension,F is the joint probability distribution of the random variables ₁,..., _m, and 0<p<1. The first problem was introduced as the deterministic equivalent and the second problem was introduced as the dual of the probabilistic constrained linear programming problem inf{cx:P(A ₁ x)p,A ₂ xb}.b}. Properties of the sets and the functions involved in the two problems and regularity conditions of optimality are discussed.     

一个新的求解线性规划最小二乘算法

§1Introduction Currently,therearetwopopularapproachesinlinearprogramming:pivotalgorithm andinterior-pointalgorithm.Manyoftheirvariantsdevelopedbothintheoryand applicationsarestillinprogress.Thepivotmethodobtainstheoptimalsolutionviamoving consecutivelytoabettercorner-pointinthefeasibleregion,anditsmodificationstryto improvethespeedofattainingtheoptimality.Incontrast,theinterior-pointalgorithmis claimedasaninterior-pointapproach,whichgoesfromafeasiblepointtoafeasiblepoint throughtheinterioroft…     

A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation

In this paper, we investigate a new primal-dual long-step interior point algorithm for linear optimization. Based on the step size, interior point algorithms can be divided into two main groups, short-step, and long-step methods. In practice, long-step variants perform better, but usually, a better theoretical complexity can be achieved for the short-step methods. One of the exceptions is the large-update algorithm of Ai and Zhang. The new wide neighborhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique of Darvay to determine new modified search directions for our method. We show that the new long-step algorithm is convergent and has the best known iteration complexity of short-step variants. We present our numerical results and compare the performance of our algorithm with two previously introduced Ai-Zhang type interior point algorithms on a set of linear programming test problems from the Netlib library.

     

A new algorithm for solving the general quadratic programming problem

For the general quadratic programming problem (including an equivalent form of the linear complementarity problem) a new solution method of branch and bound type is proposed. The branching procedure uses a well-known simplicial subdivision and the bound estimation is performed by solving certain linear programs.     

A robust algorithm for generalized geometric programming

Most existing methods of global optimization for generalized geometric programming (GGP) actually compute an approximate optimal solution of a linear or convex relaxation of the original problem. However, these approaches may sometimes provide an infeasible solution, or far from the true optimum. To overcome these limitations, a robust solution algorithm is proposed for global optimization of (GGP) problem. This algorithm guarantees adequately to obtain a robust optimal solution, which is feasible and close to the actual optimal solution, and is also stable under small perturbations of the constraints.     

A feasible dual affine scaling steepest descent method for the linear semidefinite programming problem

The linear semidefinite programming problem is considered. The dual affine scaling method in which all current iterations belong to the feasible set is proposed for its solution. Moreover, the boundaries of the feasible set may be reached. This method is a generalization of a version of the affine scaling method that was earlier developed for linear programs to the case of semidefinite programming.     

Modified geometric programming problem and its applications

In this paper, we propose unconstrained and constrained posynomial Geometric Programming (GP) problem with negative or positive integral degree of difficulty. Conventional GP approach has been modified to solve some special typer of GP problems. In specific case, when the degree of difficulty is negative, the normality and the orthogonality conditions of the dual program give a system of linear equations. No general solution vector exists for this system of linear equations. But an approximate solution can be determined by the least square and also max-min method. Here, modified form of geometric programming method has been demonstrated and for that purpose necessary theorems have been derived. Finally, these are illustrated by numerical examples and applications.     

A new bound for the ratio between the 2-matching problem and its linear programming relaxation

Consider the 2-matching problem defined on the complete graph, with edge costs which satisfy the triangle inequality. We prove that the value of a minimum cost 2-matching is bounded above by 4/3 times the value of its linear programming relaxation, the fractional 2-matching problem. This lends credibility to a long-standing conjecture that the optimal value for the traveling salesman problem is bounded above by 4/3 times the value of its linear programming relaxation, the subtour elimination problem. Received August 26, 1996 / Revised version received July 6, 1999? Published online September 15, 1999