This note shows how one can solve linear goal programming problems using a preemptive priority structure in a very efficient manner. In particular, the entire sequence of computational steps needed can easily be incor...
详细信息
This note shows how one can solve linear goal programming problems using a preemptive priority structure in a very efficient manner. In particular, the entire sequence of computational steps needed can easily be incorporated in MPSX/370E's control program. The procedure does not require the user to interface a FORTRAN program to the user's MPSX/370 program as previous studies have suggested.
Test computations using a proposed procedure for solving general multidimensional knapsack problems with a few contraints have positive results. The solution procedure assumes that the problem has a few resource cons...
详细信息
Test computations using a proposed procedure for solving general multidimensional knapsack problems with a few contraints have positive results. The solution procedure assumes that the problem has a few resource constraints and that the parameters are all positive integers. It uses a state generation scheme, but the generated state sets are revised regularly using the dominance principle rather than the strict principle of optimality. Nonpromising state vectors are pruned by considering the highest return that can be obtained with the remaining decision variables and resources. If the size of a state set exceeds a threshold value, the problem will be partitioned into subproblems, which are combined optimally at the last stage. The test results indicate that computation times are very good and that the preprocessing procedure of eliminating dominated variables is a cost-effective technique, especially for small dimensional problems with uncorrelated data.
In this paper, we first give a counterexample showing the falsehood of the convergence theorem of Choo and Kim. We then prove a convergence theorem for their algorithm.
In this paper, we first give a counterexample showing the falsehood of the convergence theorem of Choo and Kim. We then prove a convergence theorem for their algorithm.
In this paper, we discuss solution approaches to the important but difficult class of all-integer programming problems that are highly primal and dual-degenerate. In particular, we note our success with an “objective...
详细信息
In this paper, we discuss solution approaches to the important but difficult class of all-integer programming problems that are highly primal and dual-degenerate. In particular, we note our success with an “objective function cut” in this regard, and exhibit a computational comparison with other cutting plane techniques.
This note presents a simple and intuitive graphical method for finding the shortest route between two specified nodes in a network. The approach is similar to the Hungarian Method for solving assignment problems.E. A....
详细信息
This note presents a simple and intuitive graphical method for finding the shortest route between two specified nodes in a network. The approach is similar to the Hungarian Method for solving assignment problems.E. A. Silver
A software package has been developed for the Intergraph CAD/CAM system to illustrate three-dimensional linearprogramming models. The software, called LPVAX, allows a user to enter a linearprogramming model with thr...
详细信息
A software package has been developed for the Intergraph CAD/CAM system to illustrate three-dimensional linearprogramming models. The software, called LPVAX, allows a user to enter a linearprogramming model with three variables and receive a complete solution including sensitivity analysis. The use may then, by menu commands, enter the solution into a graphics file for the CAD/CAM system to convert into graphics displays. The user can display all of the constraints and the objective function in a three-dimensional graph. The solution solid can be viewed and rotated continuously, a key technique for user understanding of the feasible solution space. Constraints can be removed from or added to the display singly or in groups so that any number of the constraints may be displayed immediately. The system is menu-driven for ease of use.
This note studies a class of stochastic programs with scale parameters in the objective function and right-hand side. linear programs are an important special case of this class. The scale parameters are a pair of joi...
详细信息
This note studies a class of stochastic programs with scale parameters in the objective function and right-hand side. linear programs are an important special case of this class. The scale parameters are a pair of jointly distributed random variables. The basic issue addressed is the type of biases introduced by replacing the random variables by their expected values. As one would expect, the covariance between the random variables is of central importance. Depending upon the sign of the covariance, the objective value of the program, in which the random variables are replaced by their expected values, is greater or lesser than the expected objective function value of the stochastic program. [ABSTRACT FROM AUTHOR]
This paper gives computational results for an efficient implementation of a variant of dual projective algorithm for linearprogramming. The implementation uses the preconditioned conjugate gradient method for computi...
详细信息
This paper gives computational results for an efficient implementation of a variant of dual projective algorithm for linearprogramming. The implementation uses the preconditioned conjugate gradient method for computing projections. Our computational experience reported in this paper indicates that this algorithm has potential as an alternative for solving very large LPs in which the direct methods fail due to memory and CPU time requirements. The conjugate gradient algorithm was able to find very accurate directions even when the system was ill-conditioned. The paper also discusses a new mathematical technique called the reciprocal estimates for estimating the primal variables. We have conducted extensive computational experiments on problems representative of large classes of applications of current interest. We have also chosen instances of the problems of future potential interest, which could not be solved in the past due to the weakness of the prior solution methods, but which represent a large class of new applications. The hypergraph model is such an example. Comparison of our implementation with MINOS 5.1 shows that our implementation is orders of magnitude faster than MINOS 5.1 for these problems.
The author investigates a mathematical programming problem with constraints in the form of inequalities and methods for its solution, based on the use of a nondifferentiable penalty function. Special attention has bee...
详细信息
The author investigates a mathematical programming problem with constraints in the form of inequalities and methods for its solution, based on the use of a nondifferentiable penalty function. Special attention has been given to the problem of the selection of a finite penalty parameter, ensuring the non-local convergence to the solution. It is shown that, as far as convergence is concerned, the constructed algorithms coincide with the known locally convergent algorithms of the conditional optimization with a linear approximation of the constraints, such as first-order methods (linearization, successive linearization methods), Newton's method, and methods with accelerated convergence.
暂无评论