A monotonic projective algorithm for fractional linear programming

We demonstrate that Karmarkar's projective algorithm is fundamentally an algorithm for fractional linear programming on the simplex. Convergence for the latter problem is established assuming only an initial lower bound on the optimal objective value. We also show that the algorithm can be easily modified so as to assure monotonicity of the true objective values, while retaining all global convergence properties. Finally, we show how the monotonic algorithm can be used to obtain an initial lower bound when none is otherwise available.     

The iterative step in the linear programming algorithm of N. Karmarkar

We simplify and strengthen the analysis of the improvement obtained in one step of Karmarkar's algorithm.     

An extension of Karmarkar's algorithm for linear programming using dual variables

We describe an extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates primal and dual solutions with objective values converging to the common optimal primal and dual value. We also describe an implementation for the dense case and show how extreme point solutions can be obtained naturally, with little extra computation.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS-15361.     

A projective method for linear programming with box-type constraints

A specialization of the projective method for linear programming to problems with lower and upper bounds on the variables is proposed.This work was done while the author was visiting New York University.     

A modification of karmarkar's linear programming algorithm

We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviatinga priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods.     

On combined phase 1-phase 2 projective methods for linear programming

We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.This research was partially supported by NSF Grant DMS-8904406 and by ONR Contract N00004-87-K0212. The computations were carried out in the Cornell Computational Optimization Laboratory with support from NSF Grant DMS-8706133.     

On partial updating in a potential reduction linear programming algorithm of Kojima,Mizuno, and Yoshise

We consider partial updating in Kojima, Mizuno, and Yoshise's primal-dual potential reduction algorithm for linear programming. We use a simple safeguard condition to control the number of updates incurred on combined primal-dual steps. Our analysis allows for unequal steplengths in the primal and dual variables, which appears to be a computationally significant factor for primal-dual methods. The safeguard we use is a primal-dual Goldstein-Armijo condition, modified to deal with the unequal primal and dual steplengths.This work was written while Kurt M. Anstreicher was a research fellow at the Center for Operations Research and Econometrics, Université Catholique de Louvain, Louvain-La-Neuve, Belgium.     

Search directions for interior linear-programming methods

Since Karmarkar published his algorithm for linear programming, several different interior directions have been proposed and much effort was spent on the problem transformations needed to apply these new techniques. This paper examines several search directions in a common framework that does not need any problem transformation. These directions prove to be combinations of two problem-dependent vectors, and can all be improved by a bidirectional search procedure.We conclude that there are essentially two polynomial algorithms: Karmarkar's method and the algorithm that follows a central trajectory, and they differ only in a choice of parameters (respectively lower bound and penalty multiplier).Research partly sponsored by CNPq-Brazilian National Council for Scientific and Technological Development, by National Science Foundation Grant ECS-8121149, Office of Naval Research Contract N00014-83-K-0602, AFOSR Grant 83-0361, State of California Microelectronics Innovation and Computer Research Opportunities Program, and General Electric.On leave from COPPE-Federal University of Rio de Janeiro, Cx. Postal 68511, 21941 Rio de Janeiro, RJ, Brasil.     

高效求解整数线性规划问题的分支算法

为了提高求解一般整数线性规划问题的效率,提出了一种基于目标函数超平面移动的分支算法。对于给定的目标函数整数值,首先利用线性规划松弛问题的最优单纯形表确定变量的上、下界,然后将变量的上、下界条件加入约束条件中对相应的目标函数超平面进行切割,最后应用分支定界算法中的分支方法来搜寻目标函数超平面上的可行解。通过对一些经典的数值例子的求解计算并与经典的分支定界算法进行比较,结果表明,该算法减少了分支数和单纯形迭代数,具有较大的实用价值。     

Homotopy techniques in linear programming

In this note, we consider the solution of a linear program, using suitably adapted homotopy techniques of nonlinear programming and equation solving that move through the interior of the polytope of feasible solutions. The homotopy is defined by means of a quadratic regularizing term in an appropriate metric. We also briefly discuss algorithmic implications and connections with the affine variant of Karmarkar's method.This is a revised version of a paper previously entitled Karmarkar's Method and Homotopies with Restarts.     

A linear programming algorithm for invariant polyhedral sets of discrete-time linear systems

In this paper we formulate necessary and sufficient conditions for an arbitrary polyhedral set to be a positively invariant set of a linear discrete-time system. Polyhedral cones and linear subspaces are included in the analysis. A linear programming algorithm is presented that enables practical application of the results stated in this paper.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

Taylor series approach to fuzzy multiobjective linear fractional programming

This paper presents the use of a Taylor series for fuzzy multiobjective linear fractional programming problems (FMOLFP). The Taylor series is a series expansion that a representation of a function. In the proposed approach, membership functions associated with each objective of fuzzy multiobjective linear fractional programming problem transformed by using a Taylor series are unified. Thus, the problem is reduced to a single objective. Practical applications and numerical examples are used in order to show the efficiency and superiority of the proposed approach.     

A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem

In this paper, the simultaneous order acceptance and scheduling problem is developed by considering the variety of customers’ requests. To that end, two agents with different scheduling criteria including the total weighted lateness for the first and the weighted number of tardy orders for the second agent are considered. The objective is to maximize the sum of the total profit of the first and the total revenue of the second agents’ orders when the weighted number of tardy orders of the second agent is bounded by an upper bound value. In this study, it is shown that this problem is NP-hard in the strong sense, and then to optimally solve it, an integer linear programming model is proposed based on the properties of optimal solution. This model is capable of solving problem instances up to 60 orders in size. Also, the LP-relaxation of this model was used to propose a hybrid meta-heuristic algorithm which was developed by employing genetic algorithm and linear programming. Computational results reveal that the proposed meta-heuristic can achieve near optimal solutions so efficiently that for the instances up to 60 orders in size, the average deviation of the model from the optimal solution is lower than 0.2% and for the instances up to 150 orders in size, the average deviation from the problem upper bound is lower than 1.5%.     

User friendly micro computer program for solving fractional and linear programming problems

Fractional Linear Programming (FLP) has many applications in management science as well as in engineering. We have developed a microcomputer program to solve linear and FLP problems. It is written in TURBO PASCAL which can be used on a wide variety of microcomputers. Because data entry constitutes a large proportion of the total computer solution time, careful attention has been placed on the human factors of human-computer interaction in that stage of program development. A test example is presented to demonstrate the usefulness of this program.     

A polynomial newton method for linear programming

An algorithm is presented for solving a set of linear equations on the nonnegative orthant. This problem can be made equivalent to the maximization of a simple concave function subject to a similar set of linear equations and bounds on the variables. A Newton method can then be used which enforces a uniform lower bound which increases geometrically with the number of iterations. The basic steps are a projection operation and a simple line search. It is shown that this procedure either proves in at mostO(n ² m ² L) operations that there is no solution or, else, computes an exact solution in at mostO(n ³ m ² L) operations.The linear programming problem is treated as a parametrized feasibility problem and solved in at mostO(n ³ m ² L) operations.     

A systolic algorithm for solving dense linear systems

For an arbitrary n × n matrix A and an n × 1 column vector b, we present a systolic algorithm to solve the dense linear equations Ax = b. An important consideration is that the pivot row can be changed during the execution of our systolic algorithm. The computational model consists of n linear systolic arrays. For 1 ≤ i ≤ n, the i^th linear array is responsible to eliminate the i^th unknown variable x_i of x. This algorithm requires 4n time steps to solve the linear system. The elapsed time unit within a time step is independent of the problem size n. Since the structure of a PE is simple and the same type PE executes the identical instructions, it is very suitable for VLSI implementation. The design process and correctness proof are considered in detail. Moreover, this algorithm can detect whether A is singular or not.     

基于线性规划和遗传–粒子群算法的烧结配料多目标综合优化方法

针对钢铁企业二次配料工艺,本文采用将硫含量折算为可比成本,兼顾节能减排目标和配料成本,建立了二次配料多目标优化模型;提出了一种基于线性规划和遗传–粒子群算法（GA–PSO）的钢铁烧结配料优化方法.首先采用线性规划算法进行求解,若线性规划方法无法求得最优解,则采用GA–PSO算法进行搜索.该方法应用于某钢铁企业360m2生产线的＂配料优化与决策支持系统＂中,实际运行结果表明,该算法在保证烧结矿质量的前提下,能够有效地减少二氧化硫排放,降低配料成本.     

A Hybrid approach for integer programming combining genetic algorithms, linear programming and ordinal optimization

Hybrid methods are promising tools in integer programming, as they combine the best features of different methods in a complementary fashion. This paper presents such a framework, integrating the notions of genetic algorithm, linear programming, and ordinal optimization in an effort to shorten computation times for large and/or difficult integer programming problems. Capitalizing on the central idea of ordinal optimization and on the learning capability of genetic algorithms to quickly generate good feasible solutions, and then using linear programming to solve the problem that results from fixing the integer part of the solution, one may be able to obtain solutions that are close to optimal. Indeed ordinal optimization guarantees the quality of the solutions found. Numerical testing on a real-life complex scheduling problem demonstrates the effectiveness and efficiency of this approach.