27 Result(s)
within
Chapter
**-Qi PAN
Computer Science
Business Mathematics
-
Chapter
Dual Pivot Rule
A pivot rule used in the dual simplex method is termed dual pivot rule. Like in the primal simplex context, a dual pivot rule plays an important role in the dual algorithm. This chapter will present very promisin...
-
Chapter
Simplex Interior-Point Method
To cope with degeneracy, the face (or dual face) method introduced previously does not seek the optimal solution, vertex by vertex, but instead, face by face. However, it still faces degeneracy. It seems that ...
-
Chapter
Decomposition Principle
It has long been a challenge to solve large-scale LP problems that require a huge number of iterations and storage. One way is to use the decomposition methods, such as Dantzig–Wolfe decomposition and Benders ...
-
Chapter
Interior-Point Method
As it is known, the simplex method moves on the underlying polyhedron, from vertex to adjacent vertex along edges, until attaining an optimal vertex unless the lower unboundedness is detected. Nevertheless, it...
-
Chapter
Pivot Rule
Consider the following standard LP problem.
-
Chapter
Simplex Phase-I Method
The simplex method requires a feasible basis to get itself started. The so-called Phase-I procedure is for this purpose.
-
Chapter
Reduced Simplex Method
Consider the standard LP problem (12.1) with the additional assumption that the cost c is not a linear combination of rows of A.
-
Chapter
Dual Deficient-Basis Method
This chapter attacks the standard LP problem from the dual side using the deficient basis. To achieve optimality, the method presented in the previous chapter seeks dual feasibility while maintaining primal fe...
-
Chapter
Geometry of Feasible Region
The feasible region P, defined by Definition 1.4.1, is of great importance to the LP problem. Theories and methods of LP are closely related to P, without exception. In ...
-
Chapter
Generalized Reduced Simplex Method
Although we always consider the standard LP problem, the LP problems from practice are various. The latter can be transformed into a more general form, that is, the so-called bounded-variable LP problem. This typ...
-
Chapter
Dual Face Method with Cholesky Factorization
The same idea of the previous face method applies to the dual problem. The resulting so-called dual face method turns out to be even more efficient. In the next sections, we put forward the steepest ascent direct...
-
Chapter
Implementation of Simplex Method
All algorithms formulated in this book, such as the simplex algorithm and the dual simplex algorithm, are theoretical or conceptual and cannot be put into use directly. Software, resulting by the following alg...
-
Chapter
Dual Face Method with LU Factorization
In the next section, we first put forward the key to this method, which is important for understanding the subsequent derivation. In the following sections, we discuss topics, such as the ascent search directi...
-
Chapter
Primal-Dual Simplex Method
Methods perform very differently when solving the same problem. It is a common case that a problem that is solved slowly by the simplex method would be solved fast by the dual simplex method, and vice versa. C...
-
Chapter
Facial Interior-Point Method
The simplex interior-point method, introduced in the previous chapter, is a combination of the simplex method and the normal interior-point method. In contrast, the so-called facial interior-point method proposed...
-
Chapter
Generalized Simplex Method
There are various problems from practice, and all can be put into the following general form.
-
Chapter
Integer Linear Programming (ILP)
The feasible region of the LP problem is continuous since each variable is restricted to a continuous interval. If variables (or a part of variables) are further restricted to integer values, it becomes an intege...
-
Chapter
Dual Simplex Phase-l Method
The mission of a dual Phase-I procedure is to provide an initial dual feasible basis to get the dual simplex method started.
-
Chapter
Introduction
As intelligent creatures, human beings plan and carry out activities with pre-set objectives. Early human ancestors relied on their experience only, whereas their modern-day descendants make their decisions ba...
-
Chapter
D-Reduced Simplex Method
Consider the following special form of the standard LP problem.
