Given n linear inequalities in three variables, we show how to construct a corresponding spherical subdivision using great circle arcs in time O( n log n ) and space O( n ). This subdivision in turn allows us to compu...
详细信息
Given n linear inequalities in three variables, we show how to construct a corresponding spherical subdivision using great circle arcs in time O( n log n ) and space O( n ). This subdivision in turn allows us to compute the point in space satisfying all inequalities and maximizing any desired linear objective function in time O (log n ).
Large linearprogramming models can suffer from inaccuracy due to the large number of calculations. These inaccuracies may create a solution which is optimal but non-feasible. A computer solution technique is suggeste...
详细信息
Large linearprogramming models can suffer from inaccuracy due to the large number of calculations. These inaccuracies may create a solution which is optimal but non-feasible. A computer solution technique is suggested which minimise errors and relies on the linearprogramming solution technique.
Control over decision variables in a multilevel programming environment is partitioned among ordered levels within a hierarchical structure. The greatest hurdle to the effective use of these concepts has been the lac...
详细信息
Control over decision variables in a multilevel programming environment is partitioned among ordered levels within a hierarchical structure. The greatest hurdle to the effective use of these concepts has been the lack of efficient algorithmic procedures to solve the resulting mathematical programming problems. Several techniques recently have been suggested as a solution to the linear bilevel programming problem (BLPP) through the bicriteria programming algorithm. However, no relationship exists between bilevel and bicriteria programming problems. Therefore, the bicriteria programming algorithm is not suitable for every BLPP when seeking optimal solutions. However, in a restricted case, BLPP can be solved by a bicriteria programming problem algorithm. Efforts to develop an effective algorithm for solving the linear BLPP should continue.
The general problem of the coefficient matrix being parameterized by a matrix of rank k is considered. It is shown that the parametric program so defined is equivalent to a problem in which only k coefficients depend ...
详细信息
The general problem of the coefficient matrix being parameterized by a matrix of rank k is considered. It is shown that the parametric program so defined is equivalent to a problem in which only k coefficients depend on the parameter. Thus, for the special case of k equals 1 the problem simplifies to solving a linear program in which only one coefficient depends on this parameter.
The bicriterion problem formulated as a 0–1 mixed integer linearprogramming problem is considered. The problem will be applied to a variety of applications, for example, process synthesis, process design, etc. By em...
详细信息
The bicriterion problem formulated as a 0–1 mixed integer linearprogramming problem is considered. The problem will be applied to a variety of applications, for example, process synthesis, process design, etc. By employment of the ϵ-constrained approach, the bicriterion problem is reformulated as a 0–1 parametric mixed integer linearprogramming problem. It is shown that a branch-and-bound algorithm for 0–1 parametric mixed integer linearprogramming developed previously by the present authors is successfully applied to obtain the complete set of Pareto optima for the bicriterion problem.
We improve the standard transformation of the symmetric, single-depot, multiple traveling salesman problem (MTSP) to one on a sparser edge configuration. The improvement tends to suppress, to a large extent, the degen...
详细信息
We improve the standard transformation of the symmetric, single-depot, multiple traveling salesman problem (MTSP) to one on a sparser edge configuration. The improvement tends to suppress, to a large extent, the degeneracy of the resulting symmetric traveling salesman problem (TSP). As a result, a 1-tree based TSP algorithm solves large MTSPs of the type we consider as easily as it solves standard TSPs. We demonstrate the improvement by presenting computational results that are currently the best available. [ABSTRACT FROM AUTHOR]
An experimental interactive system has been built that simplifies the development of linearprogramming models. The system eliminates the requirement of expressing the problem as a matrix, which eliminates a lot of t...
详细信息
An experimental interactive system has been built that simplifies the development of linearprogramming models. The system eliminates the requirement of expressing the problem as a matrix, which eliminates a lot of the effort normally required to solve linearprogramming problems. A nonprocedural language allows the model to be constructed in terminology that is natural to the problem. A data base can be maintained with system data and used to generate reports independently of the linearprogramming context. Ordinary algebraic expressions can be used to express the model by generic constraints which the system interprets in conjunction with the data base to generate a concrete model. The model has been used in agricultural applications. Appendices.
In recent years, many researchers have demonstrated that surrogate constraints can be employed to reduce the computational requirements of integer and mixed-integer programming problems. An algorithm is developed tha...
详细信息
In recent years, many researchers have demonstrated that surrogate constraints can be employed to reduce the computational requirements of integer and mixed-integer programming problems. An algorithm is developed that uses surrogate constraints to solve fixed-charge problems. The algorithm generates a candidate solution for the fixed-charge problem by solving a set covering problem. If the candidate solution is not feasible in the fixed-charge problem, a surrogate constraint is generated and added to the set covering problem to cut this solution from the feasible region. This process is repeated until a feasible solution to the fixed-charge problem is discovered. The solution is then used as an incumbent solution in a branch-and-bound procedure, which solves the problem to optimality. According to the results, this algorithm appears to perform better than existing branch-and-bound solution procedures.
A list of recently released linearprogramming (LP) software packages for microcomputers is provided. Four of the more powerful and advanced LP packages are compared comprehensively: 1. Lindo Systems Inc.'s LIND...
详细信息
A list of recently released linearprogramming (LP) software packages for microcomputers is provided. Four of the more powerful and advanced LP packages are compared comprehensively: 1. Lindo Systems Inc.'s LINDO/PC, 2. LP83 from Sunset Software, 3. LP88 Package (BLPX88 and MILP88) from Eastern Software Products Inc., and 4. Briggs Technologies Inc.'s MPS-PC. These packages are compared in terms of: 1. input, 2. data management, 3. user interface, and 4. technical features. The LP packages are aimed at advanced users, accept MPSX formatted input, include mixed-integer programming options, and use the 8087 math coprocessor for speed improvement. An attempt is made to solve 14 problems on the systems. LINDO was able to solve most of the problems; LP88 solved 8 of the problems; and LP83 and MPS-PC solved 7 of the test problems. Each package has unique features. For example, LINDO and LP83 are powerful in calculations, while MPS-PC offers a much better problem development entry system.
Although the bilevel programming problem has a significantly different structure than the bicriteria programming problem, a relationship does exist between the 2. However, solution techniques for bicriteria programmi...
详细信息
Although the bilevel programming problem has a significantly different structure than the bicriteria programming problem, a relationship does exist between the 2. However, solution techniques for bicriteria programming require less computational effort. The relationship between bilevel and bicriteria programming is used to develop an algorithm for linear bilevel programming through the adaptation of a bicriteria programming algorithm proposed previously. Computational results obtained for 4 types of randomly generated problems with different number of constraints and variables are summarized. The algorithm is coded in FORTRAN, and computations are performed on a VAX-11/730. The results suggest that the algorithm presented here performs better than the grid search algorithm, and that further reductions in central processing unit times are achieved. In order to examine the effect of problem structure on the computation time in regard to the relative sizes of the vectors x and y, further sample problems are solved.
暂无评论