Basic feasible solution

Last updated

In the theory of linear programming, a basic feasible solution (BFS) is a solution with a minimal set of non-zero variables. Geometrically, each BFS corresponds to a vertex of the polyhedron of feasible solutions. If there exists an optimal solution, then there exists an optimal BFS. Hence, to find an optimal solution, it is sufficient to consider the BFS-s. This fact is used by the simplex algorithm, which essentially travels from one BFS to another until an optimal solution is found. [1]

Contents

Definitions

Preliminaries: equational form with linearly-independent rows

For the definitions below, we first present the linear program in the so-called equational form:

maximize
subject to and

where:

Any linear program can be converted into an equational form by adding slack variables.

As a preliminary clean-up step, we verify that:

Feasible solution

A feasible solution of the LP is any vector such that . We assume that there is at least one feasible solution. If m = n, then there is only one feasible solution. Typically m < n, so the system has many solutions; each such solution is called a feasible solution of the LP.

Basis

A basis of the LP is a nonsingular submatrix of A, with all m rows and only m<n columns.

Sometimes, the term basis is used not for the submatrix itself, but for the set of indices of its columns. Let B be a subset of m indices from {1,...,n}. Denote by the square m-by-m matrix made of the m columns of indexed by B. If is nonsingular, the columns indexed by B are a basis of the column space of . In this case, we call Ba basis of the LP.

Since the rank of is m, it has at least one basis; since has n columns, it has at most bases.

Basic feasible solution

Given a basis B, we say that a feasible solution is a basic feasible solution with basis B if all its non-zero variables are indexed by B, that is, for all .

Properties

1. A BFS is determined only by the constraints of the LP (the matrix and the vector ); it does not depend on the optimization objective.

2. By definition, a BFS has at most m non-zero variables and at least n-m zero variables. A BFS can have less than m non-zero variables; in that case, it can have many different bases, all of which contain the indices of its non-zero variables.

3. A feasible solution is basic if-and-only-if the columns of the matrix are linearly independent, where K is the set of indices of the non-zero elements of . [1] :45

4. Each basis determines a unique BFS: for each basis B of m indices, there is at most one BFS with basis B. This is because must satisfy the constraint , and by definition of basis the matrix is non-singular, so the constraint has a unique solution:

The opposite is not true: each BFS can come from many different bases. If the unique solution of satisfies the non-negativity constraints , then B is called a feasible basis.

5. If a linear program has an optimal solution (i.e., it has a feasible solution, and the set of feasible solutions is bounded), then it has an optimal BFS. This is a consequence of the Bauer maximum principle: the objective of a linear program is convex; the set of feasible solutions is convex (it is an intersection of hyperspaces); therefore the objective attains its maximum in an extreme point of the set of feasible solutions.

Since the number of BFS-s is finite and bounded by , an optimal solution to any LP can be found in finite time by just evaluating the objective function in all BFS-s. This is not the most efficient way to solve an LP; the simplex algorithm examines the BFS-s in a much more efficient way.

Examples

Consider a linear program with the following constraints:

The matrix A is:

Here, m=2 and there are 10 subsets of 2 indices, however, not all of them are bases: the set {3,5} is not a basis since columns 3 and 5 are linearly dependent.

The set B={2,4} is a basis, since the matrix is non-singular.

The unique BFS corresponding to this basis is .

Geometric interpretation

Elongated pentagonal orthocupolarotunda.png

The set of all feasible solutions is an intersection of hyperspaces. Therefore, it is a convex polyhedron. If it is bounded, then it is a convex polytope. Each BFS corresponds to a vertex of this polytope. [1] :53–56

Basic feasible solutions for the dual problem

As mentioned above, every basis B defines a unique basic feasible solution . In a similar way, each basis defines a solution to the dual linear program:

minimize
subject to .

The solution is .

Finding an optimal BFS

There are several methods for finding a BFS that is also optimal.

Using the simplex algorithm

In practice, the easiest way to find an optimal BFS is to use the simplex algorithm. It keeps, at each point of its execution, a "current basis" B (a subset of m out of n variables), a "current BFS", and a "current tableau". The tableau is a representation of the linear program where the basic variables are expressed in terms of the non-basic ones: [1] :65

where is the vector of m basic variables, is the vector of n non-basic variables, and is the maximization objective. Since non-basic variables equal 0, the current BFS is , and the current maximization objective is .

If all coefficients in are negative, then is an optimal solution, since all variables (including all non-basic variables) must be at least 0, so the second line implies .

If some coefficients in are positive, then it may be possible to increase the maximization target. For example, if is non-basic and its coefficient in is positive, then increasing it above 0 may make larger. If it is possible to do so without violating other constraints, then the increased variable becomes basic (it "enters the basis"), while some basic variable is decreased to 0 to keep the equality constraints and thus becomes non-basic (it "exits the basis").

If this process is done carefully, then it is possible to guarantee that increases until it reaches an optimal BFS.

Converting any optimal solution to an optimal BFS

In the worst case, the simplex algorithm may require exponentially many steps to complete. There are algorithms for solving an LP in weakly-polynomial time, such as the ellipsoid method; however, they usually return optimal solutions that are not basic.

However, Given any optimal solution to the LP, it is easy to find an optimal feasible solution that is also basic. [2] :see also "external links" below.

Finding a basis that is both primal-optimal and dual-optimal

A basis B of the LP is called dual-optimal if the solution is an optimal solution to the dual linear program, that is, it minimizes . In general, a primal-optimal basis is not necessarily dual-optimal, and a dual-optimal basis is not necessarily primal-optimal (in fact, the solution of a primal-optimal basis may even be unfeasible for the dual, and vice versa).

If both is an optimal BFS of the primal LP, and is an optimal BFS of the dual LP, then the basis B is called PD-optimal. Every LP with an optimal solution has a PD-optimal basis, and it is found by the Simplex algorithm. However, its run-time is exponential in the worst case. Nimrod Megiddo proved the following theorems: [2]

Megiddo's algorithms can be executed using a tableau, just like the simplex algorithm.

Related Research Articles

<span class="mw-page-title-main">Linear algebra</span> Branch of mathematics

Linear algebra is the branch of mathematics concerning linear equations such as:

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

<span class="mw-page-title-main">Linear programming</span> Method to solve optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

<span class="mw-page-title-main">System of linear equations</span> Several equations of degree 1 to be solved simultaneously

In mathematics, a system of linear equations is a collection of one or more linear equations involving the same variables. For example,

In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints are linear.

Column generation or delayed column generation is an efficient algorithm for solving large linear programs.

<span class="mw-page-title-main">Interior-point method</span> Algorithms for solving convex optimization problems

Interior-point methods are algorithms for solving linear and non-linear convex optimization problems. IPMs combine two advantages of previously-known algorithms:

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests for a solution in nonlinear programming to be optimal, provided that some regularity conditions are satisfied.

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem. Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem. Therefore, the solution to the primal is an upper bound to the solution of the dual, and the solution of the dual is a lower bound to the solution of the primal. This fact is called weak duality.

In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions over convex sets. The ellipsoid method generates a sequence of ellipsoids whose volume uniformly decreases at every step, thus enclosing a minimizer of a convex function.

Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.

The dual of a given linear program (LP) is another LP that is derived from the original LP in the following schematic way:

Benders decomposition is a technique in mathematical programming that allows the solution of very large linear programming problems that have a special block structure. This block structure often occurs in applications such as stochastic programming as the uncertainty is usually represented with scenarios. The technique is named after Jacques F. Benders.

In mathematical optimization, linear-fractional programming (LFP) is a generalization of linear programming (LP). Whereas the objective function in a linear program is a linear function, the objective function in a linear-fractional program is a ratio of two linear functions. A linear program can be regarded as a special case of a linear-fractional program in which the denominator is the constant function 1.

In applied mathematics, Graver bases enable iterative solutions of linear and various nonlinear integer programming problems in polynomial time. They were introduced by Jack E. Graver. Their connection to the theory of Gröbner bases was discussed by Bernd Sturmfels. The algorithmic theory of Graver bases and its application to integer programming is described by Shmuel Onn.

A separation oracle is a concept in the mathematical theory of convex optimization. It is a method to describe a convex set that is given as an input to an optimization algorithm. Separation oracles are used as input to ellipsoid methods.

The configuration linear program (configuration-LP) is a linear programming technique used for solving combinatorial optimization problems. It was introduced in the context of the cutting stock problem. Later, it has been applied to the bin packing and job scheduling problems. In the configuration-LP, there is a variable for each possible configuration - each possible multiset of items that can fit in a single bin. Usually, the number of configurations is exponential in the problem size, but in some cases it is possible to attain approximate solutions using only a polynomial number of configurations.

The Karmarkar–Karp (KK) bin packing algorithms are several related approximation algorithm for the bin packing problem. The bin packing problem is a problem of packing items of different sizes into bins of identical capacity, such that the total number of bins is as small as possible. Finding the optimal solution is computationally hard. Karmarkar and Karp devised an algorithm that runs in polynomial time and finds a solution with at most bins, where OPT is the number of bins in the optimal solution. They also devised several other algorithms with slightly different approximation guarantees and run-time bounds.

References

  1. 1 2 3 4 Gärtner, Bernd; Matoušek, Jiří (2006). Understanding and Using Linear Programming. Berlin: Springer. ISBN   3-540-30697-8.:44–48
  2. 1 2 Megiddo, Nimrod (1991-02-01). "On Finding Primal- and Dual-Optimal Bases". ORSA Journal on Computing. 3 (1): 63–65. CiteSeerX   10.1.1.11.427 . doi:10.1287/ijoc.3.1.63. ISSN   0899-1499.