The paper discusses the properties of a bilinearprogramming problem and develops a convergent cutting plane algorithm. The cuts involve only a subset of the variables and preserve the special structure of the constra...
详细信息
The paper discusses the properties of a bilinearprogramming problem and develops a convergent cutting plane algorithm. The cuts involve only a subset of the variables and preserve the special structure of the constraints involving the remaining variables. The cuts are deeper than other similar cuts.
This paper presents an exact algorithm for a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian circuit through n clusters of nodes, in the case where the distanc...
详细信息
This paper presents an exact algorithm for a generalized version of the Travelling Salesman Problem which consists of finding the shortest Hamiltonian circuit through n clusters of nodes, in the case where the distance matrix is asymmetrical. The problem is formulated as an integer linear program. The program is then relaxed and solved by a branch and bound algorithm. computational results are reported for problems involving up to 100 nodes and 8 clusters.
The standard simplex algorithm for the solution of the linearprogramming problem with upper bounds of variables is based on a procedure taking into account the upper bounds and operating with a basis reduced as a res...
详细信息
The standard simplex algorithm for the solution of the linearprogramming problem with upper bounds of variables is based on a procedure taking into account the upper bounds and operating with a basis reduced as a result. This modification of the general simplex method produces a saving of memory and reduces calculations at each iteration, but the total number of iterations in the solution of a problem remains substantial. The author examines a simplex method where the standard transformation of the basis is combined with a more efficient transformation of the nonbasis portion of the plan (affecting all components simultaneously). This method is a refinement of an original version of X-matrix simplex method, which did not make use of the concept of basis variables.
We show how algebraic linear optimization models can be mapped to the relational model of data. We then introduce SQLMP, a new language for model description and manipulation. SQLMP (SQL for mathematical programming) ...
详细信息
We show how algebraic linear optimization models can be mapped to the relational model of data. We then introduce SQLMP, a new language for model description and manipulation. SQLMP (SQL for mathematical programming) is the result of endowing the Structured Query Language (SQL) with additional constructs for the definition of the objective functions and the constraints of optimization models. Features of SQLMP enable 1) smooth integration of mathematical models with SQL-based databases, 2) model manipulation, and 3) attainment of a high degree of model independence. Formal syntax of the SQLMP is given.
With ongoing advances in hardware and software, the bottleneck in linearprogramming is no longer a model solution, it is the correct formulation of large models in the first place. During initial formulation (or modi...
详细信息
With ongoing advances in hardware and software, the bottleneck in linearprogramming is no longer a model solution, it is the correct formulation of large models in the first place. During initial formulation (or modification), a very large model may prove infeasible, but it is often difficult to determine how to correct it. We present a formulation aid which analyzes infeasible LPs and identifies minimal sets of inconsistent constraints from among the perhaps very large set of constraints defining the problem. This information helps to focus the search for a diagnosis of the problem, speeding the repair of the model. We present a series of filtering routines and a final integrated algorithm which guarantees the identification of at least one minimal set of inconsistent constraints. This guarantee is a significant advantage over previous methods. The algorithms are simple, relatively efficient, and easily incorporated into standard LP solvers. Preliminary computational results are reported.
We present various techniques for automatically improving the LP-representation of general zero-one linearprogramming problems. These include detection of redundant rows and blatant infeasibilities, coefficient reduc...
详细信息
We present various techniques for automatically improving the LP-representation of general zero-one linearprogramming problems. These include detection of redundant rows and blatant infeasibilities, coefficient reduction using the Euclidean algorithm, optimality fixing and variable elimination. Extensions to the case where special-ordered-set constraints are present are discussed as well. A summary of the branch-and-cut approach to general zero-one problems (including flowcharts) is given. We report numerical experiments to test the effect of such preprocessing within a branch-and-cut algorithm for eleven large-scale real-world zero-one linear-programming problems. An illustrative example is included in the Appendix.
This paper presents a new model and branch-and-bound algorithm for the asymmetric m-travelling salesmen problem. The algorithm uses a Lagrangian relaxation, a subgradient algorithm to solve the Lagrangian dual, a gree...
详细信息
This paper presents a new model and branch-and-bound algorithm for the asymmetric m-travelling salesmen problem. The algorithm uses a Lagrangian relaxation, a subgradient algorithm to solve the Lagrangian dual, a greedy algorithm for obtaining minimal m-trees, penalties to strengthen the lower bounds on candidate problems, and a new concept known as staged optimization. Computational experience for problems having up to 100 cities is presented.
H. E. Scarf has recently introduced an algorithm for integer programs based on the combinatorial concept of primitive set. We show that as the decision variables of the integer program become continuous and the intege...
详细信息
H. E. Scarf has recently introduced an algorithm for integer programs based on the combinatorial concept of primitive set. We show that as the decision variables of the integer program become continuous and the integer program reduces to a linear program, the Scarf algorithm converges to a dual simplex algorithm for the limit linearprogramming problem. This result is robust in the sense that even before the limit is reached, the dual simplex path is contained in the path of primitive sets generated by the Scarf algorithm.
An analysis and optimization method for a multivariable system is presented. The physical and design constraints and the many parameters are handled in an iterative manner using straightforward matrix formulations.
An analysis and optimization method for a multivariable system is presented. The physical and design constraints and the many parameters are handled in an iterative manner using straightforward matrix formulations.
We present an algorithm for identifying and disposing of duplicate rows in an LP matrix — that is, rows which are identical except for a scalar multiplier. This algorithm is a useful tool for debugging models as well...
详细信息
We present an algorithm for identifying and disposing of duplicate rows in an LP matrix — that is, rows which are identical except for a scalar multiplier. This algorithm is a useful tool for debugging models as well as a means of improving efficiency. Implementation in a large scale mathematical programming system and computational experience are discussed.
暂无评论