Simplex algorithm

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Simplex_algorithm

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

The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are not actually used in the method, but one interpretation of it is that it operates on simplicial cones, and these become proper simplices with an additional constraint. The simplicial cones in question are the corners (i.e., the neighborhoods of the vertices) of a geometric object called a polytope. The shape of this polytope is defined by the constraints applied to the objective function.

History

George Dantzig worked on planning methods for the US Army Air Force during World War II using a desk calculator. During 1946, his colleague challenged him to mechanize the planning process to distract him from taking another job. Dantzig formulated the problem as linear inequalities inspired by the work of Wassily Leontief, however, at that time he didn't include an objective as part of his formulation. Without an objective, a vast number of solutions can be feasible, and therefore to find the "best" feasible solution, military-specified "ground rules" must be used that describe how goals can be achieved as opposed to specifying a goal itself. Dantzig's core insight was to realize that most such ground rules can be translated into a linear objective function that needs to be maximized. Development of the simplex method was evolutionary and happened over a period of about a year.

After Dantzig included an objective function as part of his formulation during mid-1947, the problem was mathematically more tractable. Dantzig realized that one of the unsolved problems that he had mistaken as homework in his professor Jerzy Neyman's class (and actually later solved), was applicable to finding an algorithm for linear programs. This problem involved finding the existence of Lagrange multipliers for general linear programs over a continuum of variables, each bounded between zero and one, and satisfying linear constraints expressed in the form of Lebesgue integrals. Dantzig later published his "homework" as a thesis to earn his doctorate. The column geometry used in this thesis gave Dantzig insight that made him believe that the Simplex method would be very efficient.

Overview

Further information: Linear programming

A system of linear inequalities defines a polytope as a feasible region. The simplex algorithm begins at a starting vertex and moves along the edges of the polytope until it reaches the vertex of the optimal solution.

Polyhedron of simplex algorithm in 3D

The simplex algorithm operates on linear programs in the canonical form

maximize ${\mathbf{c}}^{\mathbf{T}}\mathbf{x}$

subject to ${\displaystyle A\mathbf{x}\le \mathbf{b}}$ and ${\displaystyle \mathbf{x}\ge 0}$

with ${\displaystyle \mathbf{c}=(c_1,\dots ,c_n)}$ the coefficients of the objective function, ${\displaystyle (\cdot {)}^{\mathrm{T}}}$ is the matrix transpose, and ${\displaystyle \mathbf{x}=(x_1,\dots ,x_n)}$ are the variables of the problem, ${\displaystyle A}$ is a p×n matrix, and ${\displaystyle \mathbf{b}=(b_1,\dots ,b_p)}$. There is a straightforward process to convert any linear program into one in standard form, so using this form of linear programs results in no loss of generality.

In geometric terms, the feasible region defined by all values of ${\displaystyle \mathbf{x}}$ such that $A\mathbf{x}\le \mathbf{b}$ and ${\displaystyle \mathrm{\forall }i,x_i\ge 0}$ is a (possibly unbounded) convex polytope. An extreme point or vertex of this polytope is known as basic feasible solution (BFS).

It can be shown that for a linear program in standard form, if the objective function has a maximum value on the feasible region, then it has this value on (at least) one of the extreme points. This in itself reduces the problem to a finite computation since there is a finite number of extreme points, but the number of extreme points is unmanageably large for all but the smallest linear programs.

It can also be shown that, if an extreme point is not a maximum point of the objective function, then there is an edge containing the point so that the value of the objective function is strictly increasing on the edge moving away from the point. If the edge is finite, then the edge connects to another extreme point where the objective function has a greater value, otherwise the objective function is unbounded above on the edge and the linear program has no solution. The simplex algorithm applies this insight by walking along edges of the polytope to extreme points with greater and greater objective values. This continues until the maximum value is reached, or an unbounded edge is visited (concluding that the problem has no solution). The algorithm always terminates because the number of vertices in the polytope is finite; moreover since we jump between vertices always in the same direction (that of the objective function), we hope that the number of vertices visited will be small.

The solution of a linear program is accomplished in two steps. In the first step, known as Phase I, a starting extreme point is found. Depending on the nature of the program this may be trivial, but in general it can be solved by applying the simplex algorithm to a modified version of the original program. The possible results of Phase I are either that a basic feasible solution is found or that the feasible region is empty. In the latter case the linear program is called infeasible. In the second step, Phase II, the simplex algorithm is applied using the basic feasible solution found in Phase I as a starting point. The possible results from Phase II are either an optimum basic feasible solution or an infinite edge on which the objective function is unbounded above.

Standard form

The transformation of a linear program to one in standard form may be accomplished as follows. First, for each variable with a lower bound other than 0, a new variable is introduced representing the difference between the variable and bound. The original variable can then be eliminated by substitution. For example, given the constraint

${\displaystyle x_1\ge 5}$

a new variable, ${\displaystyle y_1}$, is introduced with

${\displaystyle \begin{array}{r}{y}_1=x_1-5\\ x_1=y_1+5\end{array}}$

The second equation may be used to eliminate ${\displaystyle x_1}$ from the linear program. In this way, all lower bound constraints may be changed to non-negativity restrictions.

Second, for each remaining inequality constraint, a new variable, called a slack variable, is introduced to change the constraint to an equality constraint. This variable represents the difference between the two sides of the inequality and is assumed to be non-negative. For example, the inequalities

${\displaystyle \begin{array}{rl}{x}_2+2x_3& \le 3\\ -x_4+3x_5& \ge 2\end{array}}$

are replaced with

${\displaystyle \begin{array}{rl}{x}_2+2x_3+s_1& =3\\ -x_4+3x_5-s_2& =2\\ s_1,s_2& \ge 0\end{array}}$

It is much easier to perform algebraic manipulation on inequalities in this form. In inequalities where ≥ appears such as the second one, some authors refer to the variable introduced as a surplus variable.

Third, each unrestricted variable is eliminated from the linear program. This can be done in two ways, one is by solving for the variable in one of the equations in which it appears and then eliminating the variable by substitution. The other is to replace the variable with the difference of two restricted variables. For example, if ${\displaystyle z_1}$ is unrestricted then write

${\displaystyle \begin{array}{rl}& z_1=z_1^{+}-z_1^{-}\\ & z_1^{+},z_1^{-}\ge 0\end{array}}$

The equation may be used to eliminate ${\displaystyle z_1}$ from the linear program.

When this process is complete the feasible region will be in the form

${\displaystyle \mathbf{A}\mathbf{x}=\mathbf{b},\mathrm{\forall }{x}_i\ge 0}$

It is also useful to assume that the rank of ${\displaystyle \mathbf{A}}$ is the number of rows. This results in no loss of generality since otherwise either the system ${\displaystyle \mathbf{A}\mathbf{x}=\mathbf{b}}$ has redundant equations which can be dropped, or the system is inconsistent and the linear program has no solution.

Simplex tableau

A linear program in standard form can be represented as a tableau of the form

${\displaystyle \left[\begin{array}{ccc}1& -{\mathbf{c}}^T& 0\\ \mathbf{0}& \mathbf{A}& \mathbf{b}\end{array}\right]}$

The first row defines the objective function and the remaining rows specify the constraints. The zero in the first column represents the zero vector of the same dimension as the vector ${\displaystyle \mathbf{b}}$ (different authors use different conventions as to the exact layout). If the columns of ${\displaystyle \mathbf{A}}$ can be rearranged so that it contains the identity matrix of order ${\displaystyle p}$ (the number of rows in ${\displaystyle \mathbf{A}}$) then the tableau is said to be in canonical form. The variables corresponding to the columns of the identity matrix are called basic variables while the remaining variables are called nonbasic or free variables. If the values of the nonbasic variables are set to 0, then the values of the basic variables are easily obtained as entries in ${\displaystyle \mathbf{b}}$ and this solution is a basic feasible solution. The algebraic interpretation here is that the coefficients of the linear equation represented by each row are either ${\displaystyle 0}$, ${\displaystyle 1}$, or some other number. Each row will have ${\displaystyle 1}$ column with value ${\displaystyle 1}$, ${\displaystyle p-1}$ columns with coefficients ${\displaystyle 0}$, and the remaining columns with some other coefficients (these other variables represent our non-basic variables). By setting the values of the non-basic variables to zero we ensure in each row that the value of the variable represented by a ${\displaystyle 1}$ in its column is equal to the ${\displaystyle b}$ value at that row.

Conversely, given a basic feasible solution, the columns corresponding to the nonzero variables can be expanded to a nonsingular matrix. If the corresponding tableau is multiplied by the inverse of this matrix then the result is a tableau in canonical form.

Let

${\displaystyle \left[\begin{array}{cccc}1& -{\mathbf{c}}_B^T& -{\mathbf{c}}_D^T& 0\\ 0& I& \mathbf{D}& \mathbf{b}\end{array}\right]}$

be a tableau in canonical form. Additional row-addition transformations can be applied to remove the coefficients cT
B  from the objective function. This process is called pricing out and results in a canonical tableau

${\displaystyle \left[\begin{array}{cccc}1& 0& -{\overline{\mathbf{c}}}_D^T& z_B\\ 0& I& \mathbf{D}& \mathbf{b}\end{array}\right]}$

where z_B is the value of the objective function at the corresponding basic feasible solution. The updated coefficients, also known as relative cost coefficients, are the rates of change of the objective function with respect to the nonbasic variables.

Pivot operations

The geometrical operation of moving from a basic feasible solution to an adjacent basic feasible solution is implemented as a pivot operation. First, a nonzero pivot element is selected in a nonbasic column. The row containing this element is multiplied by its reciprocal to change this element to 1, and then multiples of the row are added to the other rows to change the other entries in the column to 0. The result is that, if the pivot element is in a row r, then the column becomes the r-th column of the identity matrix. The variable for this column is now a basic variable, replacing the variable which corresponded to the r-th column of the identity matrix before the operation. In effect, the variable corresponding to the pivot column enters the set of basic variables and is called the entering variable, and the variable being replaced leaves the set of basic variables and is called the leaving variable. The tableau is still in canonical form but with the set of basic variables changed by one element.

Algorithm

Let a linear program be given by a canonical tableau. The simplex algorithm proceeds by performing successive pivot operations each of which give an improved basic feasible solution; the choice of pivot element at each step is largely determined by the requirement that this pivot improves the solution.

Entering variable selection

Since the entering variable will, in general, increase from 0 to a positive number, the value of the objective function will decrease if the derivative of the objective function with respect to this variable is negative. Equivalently, the value of the objective function is increased if the pivot column is selected so that the corresponding entry in the objective row of the tableau is positive.

If there is more than one column so that the entry in the objective row is positive then the choice of which one to add to the set of basic variables is somewhat arbitrary and several entering variable choice rules such as Devex algorithm have been developed.

If all the entries in the objective row are less than or equal to 0 then no choice of entering variable can be made and the solution is in fact optimal. It is easily seen to be optimal since the objective row now corresponds to an equation of the form

$${\displaystyle z(\mathbf{x})=z_B+\text{non-positive terms corresponding to non-basic variables}}$$

By changing the entering variable choice rule so that it selects a column where the entry in the objective row is negative, the algorithm is changed so that it finds the minimum of the objective function rather than the maximum.

Leaving variable selection

Once the pivot column has been selected, the choice of pivot row is largely determined by the requirement that the resulting solution be feasible. First, only positive entries in the pivot column are considered since this guarantees that the value of the entering variable will be nonnegative. If there are no positive entries in the pivot column then the entering variable can take any non-negative value with the solution remaining feasible. In this case the objective function is unbounded below and there is no minimum.

Next, the pivot row must be selected so that all the other basic variables remain positive. A calculation shows that this occurs when the resulting value of the entering variable is at a minimum. In other words, if the pivot column is c, then the pivot row r is chosen so that

${\displaystyle b_r/a_{rc}}$

is the minimum over all r so that a_rc > 0. This is called the minimum ratio test. If there is more than one row for which the minimum is achieved then a dropping variable choice rule can be used to make the determination.

Example

See also: Revised simplex algorithm § Numerical example

Consider the linear program

Minimize

${\displaystyle Z=-2x-3y-4z}$

Subject to

${\displaystyle \begin{array}{rl}3x+2y+z& \le 10\\ 2x+5y+3z& \le 15\\ x,y,z& \ge 0\end{array}}$

With the addition of slack variables s and t, this is represented by the canonical tableau

${\displaystyle \left[\begin{array}{ccccccc}1& 2& 3& 4& 0& 0& 0\\ 0& 3& 2& 1& 1& 0& 10\\ 0& 2& 5& 3& 0& 1& 15\end{array}\right]}$

where columns 5 and 6 represent the basic variables s and t and the corresponding basic feasible solution is

${\displaystyle x=y=z=0,s=10,t=15.}$

Columns 2, 3, and 4 can be selected as pivot columns, for this example column 4 is selected. The values of z resulting from the choice of rows 2 and 3 as pivot rows are 10/1 = 10 and 15/3 = 5 respectively. Of these the minimum is 5, so row 3 must be the pivot row. Performing the pivot produces

${\displaystyle \left[\begin{array}{ccccccc}3& -2& -11& 0& 0& -4& -60\\ 0& 7& 1& 0& 3& -1& 15\\ 0& 2& 5& 3& 0& 1& 15\end{array}\right]}$

Now columns 4 and 5 represent the basic variables z and s and the corresponding basic feasible solution is

${\displaystyle x=y=t=0,z=5,s=5.}$

For the next step, there are no positive entries in the objective row and in fact

$${\displaystyle Z=\frac{-60+2x+11y+4t}{3}=-20+\frac{2x+11y+4t}{3}}$$

so the minimum value of Z is −20.

Finding an initial canonical tableau

In general, a linear program will not be given in the canonical form and an equivalent canonical tableau must be found before the simplex algorithm can start. This can be accomplished by the introduction of artificial variables. Columns of the identity matrix are added as column vectors for these variables. If the b value for a constraint equation is negative, the equation is negated before adding the identity matrix columns. This does not change the set of feasible solutions or the optimal solution, and it ensures that the slack variables will constitute an initial feasible solution. The new tableau is in canonical form but it is not equivalent to the original problem. So a new objective function, equal to the sum of the artificial variables, is introduced and the simplex algorithm is applied to find the minimum; the modified linear program is called the Phase I problem.

The simplex algorithm applied to the Phase I problem must terminate with a minimum value for the new objective function since, being the sum of nonnegative variables, its value is bounded below by 0. If the minimum is 0 then the artificial variables can be eliminated from the resulting canonical tableau producing a canonical tableau equivalent to the original problem. The simplex algorithm can then be applied to find the solution; this step is called Phase II. If the minimum is positive then there is no feasible solution for the Phase I problem where the artificial variables are all zero. This implies that the feasible region for the original problem is empty, and so the original problem has no solution.

Example

Consider the linear program

Minimize

${\displaystyle Z=-2a-3b-4c}$

Subject to

${\displaystyle \begin{array}{rl}3x+2y+z& =10\\ 2x+5y+3z& =15\\ x,y,z& \ge 0\end{array}}$

This is represented by the (non-canonical) tableau

${\displaystyle \left[\begin{array}{ccccc}1& 2& 3& 4& 0\\ 0& 3& 2& 1& 10\\ 0& 2& 5& 3& 15\end{array}\right]}$

Introduce artificial variables u and v and objective function W = u + v, giving a new tableau

${\displaystyle \left[\begin{array}{cccccccc}1& 0& 0& 0& 0& -1& -1& 0\\ 0& 1& 2& 3& 4& 0& 0& 0\\ 0& 0& 3& 2& 1& 1& 0& 10\\ 0& 0& 2& 5& 3& 0& 1& 15\end{array}\right]}$

The equation defining the original objective function is retained in anticipation of Phase II.

By construction, u and v are both basic variables since they are part of the initial identity matrix. However, the objective function W currently assumes that u and v are both 0. In order to adjust the objective function to be the correct value where u = 10 and v = 15, add the third and fourth rows to the first row giving

${\displaystyle \left[\begin{array}{cccccccc}1& 0& 5& 7& 4& 0& 0& 25\\ 0& 1& 2& 3& 4& 0& 0& 0\\ 0& 0& 3& 2& 1& 1& 0& 10\\ 0& 0& 2& 5& 3& 0& 1& 15\end{array}\right]}$

Select column 5 as a pivot column, so the pivot row must be row 4, and the updated tableau is

${\displaystyle \left[\begin{array}{cccccccc}3& 0& 7& 1& 0& 0& -4& 15\\ 0& 3& -2& -11& 0& 0& -4& -60\\ 0& 0& 7& 1& 0& 3& -1& 15\\ 0& 0& 2& 5& 3& 0& 1& 15\end{array}\right]}$

Now select column 3 as a pivot column, for which row 3 must be the pivot row, to get

${\displaystyle \left[\begin{array}{cccccccc}7& 0& 0& 0& 0& -7& -7& 0\\ 0& 7& 0& -25& 0& 2& -10& -130\\ 0& 0& 7& 1& 0& 3& -1& 15\\ 0& 0& 0& 11& 7& -2& 3& 25\end{array}\right]}$

The artificial variables are now 0 and they may be dropped giving a canonical tableau equivalent to the original problem:

${\displaystyle \left[\begin{array}{ccccc}7& 0& -25& 0& -130\\ 0& 7& 1& 0& 15\\ 0& 0& 11& 7& 25\end{array}\right]}$

This is, fortuitously, already optimal and the optimum value for the original linear program is −130/7.

Advanced topics

Implementation

Main article: Revised simplex algorithm

The tableau form used above to describe the algorithm lends itself to an immediate implementation in which the tableau is maintained as a rectangular (m + 1)-by-(m + n + 1) array. It is straightforward to avoid storing the m explicit columns of the identity matrix that will occur within the tableau by virtue of B being a subset of the columns of [A, I]. This implementation is referred to as the "standard simplex algorithm". The storage and computation overhead is such that the standard simplex method is a prohibitively expensive approach to solving large linear programming problems.

In each simplex iteration, the only data required are the first row of the tableau, the (pivotal) column of the tableau corresponding to the entering variable and the right-hand-side. The latter can be updated using the pivotal column and the first row of the tableau can be updated using the (pivotal) row corresponding to the leaving variable. Both the pivotal column and pivotal row may be computed directly using the solutions of linear systems of equations involving the matrix B and a matrix-vector product using A. These observations motivate the "revised simplex algorithm", for which implementations are distinguished by their invertible representation of B.

In large linear-programming problems A is typically a sparse matrix and, when the resulting sparsity of B is exploited when maintaining its invertible representation, the revised simplex algorithm is much more efficient than the standard simplex method. Commercial simplex solvers are based on the revised simplex algorithm.

Degeneracy: stalling and cycling

If the values of all basic variables are strictly positive, then a pivot must result in an improvement in the objective value. When this is always the case no set of basic variables occurs twice and the simplex algorithm must terminate after a finite number of steps. Basic feasible solutions where at least one of the basic variables is zero are called degenerate and may result in pivots for which there is no improvement in the objective value. In this case there is no actual change in the solution but only a change in the set of basic variables. When several such pivots occur in succession, there is no improvement; in large industrial applications, degeneracy is common and such "stalling" is notable. Worse than stalling is the possibility the same set of basic variables occurs twice, in which case, the deterministic pivoting rules of the simplex algorithm will produce an infinite loop, or "cycle". While degeneracy is the rule in practice and stalling is common, cycling is rare in practice. A discussion of an example of practical cycling occurs in Padberg. Bland's rule prevents cycling and thus guarantees that the simplex algorithm always terminates. Another pivoting algorithm, the criss-cross algorithm never cycles on linear programs.

History-based pivot rules such as Zadeh's rule and Cunningham's rule also try to circumvent the issue of stalling and cycling by keeping track of how often particular variables are being used and then favor such variables that have been used least often.

Efficiency in the worst case

The simplex method is remarkably efficient in practice and was a great improvement over earlier methods such as Fourier–Motzkin elimination. However, in 1972, Klee and Minty gave an example, the Klee–Minty cube, showing that the worst-case complexity of simplex method as formulated by Dantzig is exponential time. Since then, for almost every variation on the method, it has been shown that there is a family of linear programs for which it performs badly. It is an open question if there is a variation with polynomial time, although sub-exponential pivot rules are known.

In 2014, it was proved that a particular variant of the simplex method is NP-mighty, i.e., it can be used to solve, with polynomial overhead, any problem in NP implicitly during the algorithm's execution. Moreover, deciding whether a given variable ever enters the basis during the algorithm's execution on a given input, and determining the number of iterations needed for solving a given problem, are both NP-hard problems. At about the same time it was shown that there exists an artificial pivot rule for which computing its output is PSPACE-complete. In 2015, this was strengthened to show that computing the output of Dantzig's pivot rule is PSPACE-complete.

Efficiency in practice

Analyzing and quantifying the observation that the simplex algorithm is efficient in practice despite its exponential worst-case complexity has led to the development of other measures of complexity. The simplex algorithm has polynomial-time average-case complexity under various probability distributions, with the precise average-case performance of the simplex algorithm depending on the choice of a probability distribution for the random matrices. Another approach to studying "typical phenomena" uses Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the simplex algorithm in a polynomial number of steps.

Another method to analyze the performance of the simplex algorithm studies the behavior of worst-case scenarios under small perturbation – are worst-case scenarios stable under a small change (in the sense of structural stability), or do they become tractable? This area of research, called smoothed analysis, was introduced specifically to study the simplex method. Indeed, the running time of the simplex method on input with noise is polynomial in the number of variables and the magnitude of the perturbations.

Other algorithms

Other algorithms for solving linear-programming problems are described in the linear-programming article. Another basis-exchange pivoting algorithm is the criss-cross algorithm. There are polynomial-time algorithms for linear programming that use interior point methods: these include Khachiyan's ellipsoidal algorithm, Karmarkar's projective algorithm, and path-following algorithms. The Big-M method is an alternative strategy for solving a linear program, using a single-phase simplex.

Linear-fractional programming

Main article: Linear-fractional programming

Linear–fractional programming (LFP) is a generalization of linear programming (LP). In LP the objective function is a linear function, while the objective function of a linear–fractional program is a ratio of two linear functions. In other words, a linear program is a fractional–linear program in which the denominator is the constant function having the value one everywhere. A linear–fractional program can be solved by a variant of the simplex algorithm or by the criss-cross algorithm.

Graphical widget

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Graphical_widget

gtk3-demo, a program to demonstrate the widgets in GTK+ version 3.

A graphical widget (also graphical control element or control) in a graphical user interface is an element of interaction, such as a button or a scroll bar. Controls are software components that a computer user interacts with through direct manipulation to read or edit information about an application. User interface libraries such as Windows Presentation Foundation, Qt, GTK, and Cocoa, contain a collection of controls and the logic to render these.

Each widget facilitates a specific type of user-computer interaction, and appears as a visible part of the application's GUI as defined by the theme and rendered by the rendering engine. The theme makes all widgets adhere to a unified aesthetic design and creates a sense of overall cohesion. Some widgets support interaction with the user, for example labels, buttons, and check boxes. Others act as containers that group the widgets added to them, for example windows, panels, and tabs.

Structuring a user interface with widget toolkits allows developers to reuse code for similar tasks, and provides users with a common language for interaction, maintaining consistency throughout the whole information system.

Graphical user interface builders facilitate the authoring of GUIs in a WYSIWYG manner employing a user interface markup language. They automatically generate all the source code for a widget from general descriptions provided by the developer, usually through direct manipulation.

History

Further information: History of the graphical user interface

Around 1920, widget entered American English, as a generic term for any useful device, particularly a product manufactured for sale; a gadget.

In 1988, the term widget is attested in the context of Project Athena and the X Window System. In An Overview of the X Toolkit by Joel McCormack and Paul Asente, it says:

The toolkit provides a library of user-interface components ("widgets") like text labels, scroll bars, command buttons, and menus; enables programmers to write new widgets; and provides the glue to assemble widgets into a complete user interface.

The same year, in the manual X Toolkit Widgets - C Language X Interface by Ralph R. Swick and Terry Weissman, it says:

In the X Toolkit, a widget is the combination of an X window or sub window and its associated input and output semantics.

Finally, still in the same year, Ralph R. Swick and Mark S. Ackerman explain where the term widget came from:

We chose this term since all other common terms were overloaded with inappropriate connotations. We offer the observation to the skeptical, however, that the principal realization of a widget is its associated X window and the common initial letter is not un-useful.

Usage

Example of enabled and disabled widgets; the frame at the bottom is disabled, they are grayed out.

Any widget displays an information arrangement changeable by the user, such as a window or a text box. The defining characteristic of a widget is to provide a single interaction point for the direct manipulation of a given kind of data. In other words, widgets are basic visual building blocks which, combined in an application, hold all the data processed by the application and the available interactions on this data.

GUI widgets are graphical elements used to build the human-machine-interface of a program. GUI widgets are implemented like software components. Widget toolkits and software frameworks, like e.g. GTK+ or Qt, contain them in software libraries so that programmers can use them to build GUIs for their programs.

A family of common reusable widgets has evolved for holding general information based on the Palo Alto Research Center Inc. research for the Xerox Alto User Interface. Various implementations of these generic widgets are often packaged together in widget toolkits, which programmers use to build graphical user interfaces (GUIs). Most operating systems include a set of ready-to-tailor widgets that a programmer can incorporate in an application, specifying how it is to behave. Each type of widget generally is defined as a class by object-oriented programming (OOP). Therefore, many widgets are derived from class inheritance.

In the context of an application, a widget may be enabled or disabled at a given point in time. An enabled widget has the capacity to respond to events, such as keystrokes or mouse actions. A widget that cannot respond to such events is considered disabled. The appearance of a widget typically differs depending on whether it is enabled or disabled; when disabled, a widget may be drawn in a lighter color ("grayed out") or be obscured visually in some way. See the adjacent image for an example.

The benefit of disabling unavailable controls rather than hiding them entirely is that users are shown that the control exists but is currently unavailable (with the implication that changing some other control may make it available), instead of possibly leaving the user uncertain about where to find the control at all. On pop-up dialogues, buttons might appear greyed out shortly after appearance to prevent accidental clicking or inadvertent double-tapping.

Widgets are sometimes qualified as virtual to distinguish them from their physical counterparts, e.g. virtual buttons that can be clicked with a pointer, vs. physical buttons that can be pressed with a finger (such as those on a computer mouse).

A related (but different) concept is the desktop widget, a small specialized GUI application that provides some visual information and/or easy access to frequently used functions such as clocks, calendars, news aggregators, calculators and desktop notes. These kinds of widgets are hosted by a widget engine.

List of common generic widgets

Various widgets shown in Ubuntu.

Qt 'widgets rendered according to three different skins (artistic design): Plastik, Keramik, and Windows

See also: Graphical user interface elements

Selection and display of collections

• Button – control which can be clicked upon to perform an action. An equivalent to a push-button as found on mechanical or electronic instruments.
  • Radio button – control which can be clicked upon to select one option from a selection of options, similar to selecting a radio station from a group of buttons dedicated to radio tuning. Radio buttons always appear in pairs or larger groups, and only one option in the group can be selected at a time; selecting a new item from the group's buttons also de-selects the previously selected button.
  • Check box – control which can be clicked upon to enable or disable an option. Also called a tick box. The box indicates an "on" or "off" state via a check mark/tick ☑ or a cross ☒. Can be shown in an intermediate state (shaded or with a dash) to indicate that various objects in a multiple selection have different values for the property represented by the check box. Multiple check boxes in a group may be selected, in contrast with radio buttons.
  • Toggle switch - Functionally similar to a check box. Can be toggled on and off, but unlike check boxes, this typically has an immediate effect.
  • Toggle Button - Functionally similar to a check box, works as a switch, though appears as a button. Can be toggled on and off.
  • Split button – control combining a button (typically invoking some default action) and a drop-down list with related, secondary actions
  • Cycle button - a button that cycles its content through two or more values, thus enabling selection of one from a group of items.
• Slider – control with a handle that can be moved up and down (vertical slider) or right and left (horizontal slider) on a bar to select a value (or a range if two handles are present). The bar allows users to make adjustments to a value or process throughout a range of allowed values.
• List box – a graphical control element that allows the user to select one or more items from a list contained within a static, multiple line text box.
• Spinner – value input control which has small up and down buttons to step through a range of values
• Drop-down list – A list of items from which to select. The list normally only displays items when a special button or indicator is clicked.
• Menu – control with multiple actions which can be clicked upon to choose a selection to activate
  • Context menu – a type of menu whose contents depend on the context or state in effect when the menu is invoked
  • Pie menu – a circular context menu where selection depends on direction
• Menu bar – a graphical control element which contains drop down menus
• Toolbar – a graphical control element on which on-screen buttons, icons, menus, or other input or output elements are placed
  • Ribbon – a hybrid of menu and toolbar, displaying a large collection of commands in a visual layout through a tabbed interface.
• Combo box (text box with attached menu or List box) – A combination of a single-line text box and a drop-down list or list box, allowing the user to either type a value directly into the control or choose from the list of existing options.
• Icon – a quickly comprehensible symbol of a software tool, function, or a data file.
• Tree view – a graphical control element that presents a hierarchical view of information
• Grid view or datagrid – a spreadsheet-like tabular view of data that allows numbers or text to be entered in rows and columns.

Navigation

• Link – Text with some kind of indicator (usually underlining and/or color) that indicates that clicking it will take one to another screen or page.
• Tab – a graphical control element that allows multiple documents or panels to be contained within a single window
• Scrollbar – a graphical control element by which continuous text, pictures, or any other content can be scrolled in a predetermined direction (up, down, left, or right)

Text/value input

• Text box – (edit field) - a graphical control element intended to enable the user to input text

Output

• Label – text used to describe another widget
• Tooltip – informational window which appears when the mouse hovers over another control
• Balloon help
• Status bar – a graphical control element which poses an information area typically found at the window's bottom
• Progress bar – a graphical control element used to visualize the progression of an extended computer operation, such as a download, file transfer, or installation
• Infobar – a graphical control element used by many programs to display non-critical information to a user

Container

• Window – a graphical control element consisting of a visual area containing some of the graphical user interface elements of the program it belongs to
• Collapsible panel – a panel that can compactly store content which is hidden or revealed by clicking the tab of the widget.
  • Drawer: Side sheets or surfaces containing supplementary content that may be anchored to, pulled out from, or pushed away beyond the left or right edge of the screen.
• Accordion – a vertically stacked list of items, such as labels or thumbnails where each item can be "expanded" to reveal the associated content
• Modal window – a graphical control element subordinate to an application's main window which creates a mode where the main window can not be used.
• Dialog box – a small window that communicates information to the user and prompts for a response
• Palette window – also known as "Utility window" - a graphical control element which floats on top of all regular windows and offers ready access tools, commands or information for the current application
  • Inspector window – a type of dialog window that shows a list of the current attributes of a selected object and allows these parameters to be changed on the fly
• Frame – a type of box within which a collection of graphical control elements can be grouped as a way to show relationships visually
• Canvas – generic drawing element for representing graphical information
• Cover Flow – an animated, three-dimensional element to visually flipping through snapshots of documents, website bookmarks, album artwork, or photographs.
• Bubble Flow – an animated, two-dimensional element that allows users to browse and interact the entire tree view of a discussion thread.
• Carousel (computing) – a graphical widget used to display visual cards in a way that's quick for users to browse, both on websites and on mobile apps

List of graphical user interface elements

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/List_of_graphical_user_interface_elements

Graphical user interface elements are those elements used by graphical user interfaces (GUIs) to offer a consistent visual language to represent information stored in computers. These make it easier for people with few computer skills to work with and use computer software.

This article explains the most common elements of visual language interfaces found in the WIMP ("window, icon, menu, pointer") paradigm, although many are also used at other graphical post-WIMP interfaces. These elements are usually embodied in an interface using a widget toolkit or desktop environment.

Structural elements

Graphical user interfaces use visual conventions to represent the generic information shown. Some conventions are used to build the structure of the static elements on which the user can interact, and define the appearance of the interface.

Window

Main article: Window (computing)

A window is an area on the screen that displays information, with its contents being displayed independently from the rest of the screen. An example of a window is what appears on the screen when the "My Documents" icon is clicked in Microsoft Windows. It is easy for a user to manipulate a window: it can be shown and hidden by clicking on an icon or application, and it can be moved to any area by dragging it (that is, by clicking in a certain area of the window – usually the title bar along the top – and keeping the pointing device's button pressed, then moving the pointing device). A window can be placed in front or behind another window, its size can be adjusted, and scrollbars can be used to navigate the sections within it. Multiple windows can also be open at one time, in which case each window can display a different application or file – this is very useful when working in a multitasking environment. The system memory is the only limitation to the number of windows that can be open at once. There are also many types of specialized windows.

• A container window encloses other windows or controls. When it is moved or resized, the enclosed items move, resize, reorient, or are clipped by the container window.
• A browser window allows the user to view and navigate through a collection of items, such as files or web pages. Web browsers are an example of these types of windows.
• Text terminal windows present a character-based, command-driven text user interfaces within the overall graphical interface. MS-DOS and Unix consoles are examples of these types of windows. Terminal windows often conform to the hotkey and display conventions of CRT-based terminals that predate GUIs, such as the VT-100.
• A child window opens automatically or as a result of a user activity in a parent window. Pop-up windows on the Internet can be child windows.
• A message window, or dialog box, is a type of child window. These are usually small and basic windows that are opened by a program to display information to the user and/or get information from the user. They almost always have one or more buttons, which allow the user to dismiss the dialog with an affirmative, negative, or neutral response.

Menu

Menus allow the user to execute commands by selecting from a list of choices. Options are selected with a mouse or other pointing device within a GUI. A keyboard may also be used. Menus are convenient because they show what commands are available within the software. This limits the amount of documentation the user reads to understand the software.

• A menu bar is displayed horizontally across the top of the screen and/or along the tops of some or all windows. A pull-down menu is commonly associated with this menu type. When a user clicks on a menu option the pull-down menu will appear.
• A menu has a visible title within the menu bar. Its contents are only revealed when the user selects it with a pointer. The user is then able to select the items within the pull-down menu. When the user clicks elsewhere the content of the menu will disappear.
• A context menu is invisible until the user performs a specific mouse action, like pressing the right mouse button. When the software-specific mouse action occurs the menu will appear under the cursor.
• Menu extras are individual items within or at the side of a menu.

Icons

An icon is a small picture that represents objects such as a file, program, web page, or command. They are a quick way to execute commands, open documents, and run programs. Icons are also very useful when searching for an object in a browser list, because in many operating systems all documents using the same extension will have the same icon.

Controls (or widgets)

Main article: Widget (GUI)

Interface elements known as graphical control elements, controls or widgets are software components that a computer user interacts with through direct manipulation to read or edit information about an application. Each widget facilitates a specific user-computer interaction. Structuring a user interface with Widget toolkits allow developers to reuse code for similar tasks, and provides users with a common language for interaction, maintaining consistency throughout the whole information system.

Common uses for widgets involve the display of collections of related items (such as with various list and canvas controls), initiation of actions and processes within the interface (buttons and menus), navigation within the space of the information system (links, tabs and scrollbars), and representing and manipulating data values (such as labels, check boxes, radio buttons, sliders, and spinners.)

Tabs

A tab is typically a rectangular small box which usually contains a text label or graphical icon associated with a view pane. When activated the view pane, or window, displays widgets associated with that tab; groups of tabs allow the user to switch quickly between different widgets. This is used in all modern web browsers. With these browsers, you can have multiple web pages open at once in one window, and quickly navigate between them by clicking on the tabs associated with the pages. Tabs are usually placed in groups at the top of a window, but may also be grouped on the side or bottom of a window. Tabs are also present in the settings panes of many applications. Microsoft Windows, for example, uses tabs in most of its control panel dialogues.

Interaction elements

Some common idioms for interaction have evolved in the visual language used in GUIs. Interaction elements are interface objects that represent the state of an ongoing operation or transformation, either as visual remainders of the user intent (such as the pointer), or as affordances showing places where the user may interact.

Cursor

Main article: Cursor (user interface)

A cursor is an indicator used to show the position on a computer monitor or other display device that will respond to input from a text input or pointing device.

Pointer

Main article: Pointer (user interface)

The pointer echoes movements of the pointing device, commonly a mouse or touchpad. The pointer is the place where actions take place that are initiated through direct manipulation gestures such as click, touch and drag.

Insertion point

The caret, text cursor or insertion point represents the point of the user interface where the focus is located. It represents the object that will be used as the default subject of user-initiated commands such as writing text, starting a selection or a copy-paste operation through the keyboard.

Selection

A selection is a list of items on which user operations will take place. The user typically adds items to the list manually, although the computer may create a selection automatically.

Adjustment handle

A handle is an indicator of a starting point for a drag and drop operation. Usually the pointer shape changes when placed on the handle, showing an icon that represents the supported drag operation.

Desktop environment

From Wikipedia, the free encyclopedia

https://en.wikipedia.org/wiki/Desktop_environment

In computing, a desktop environment (DE) is an implementation of the desktop metaphor made of a bundle of programs running on top of a computer operating system that share a common graphical user interface (GUI), sometimes described as a graphical shell. The desktop environment was seen mostly on personal computers until the rise of mobile computing. Desktop GUIs help the user to easily access and edit files, while they usually do not provide access to all of the features found in the underlying operating system. Instead, the traditional command-line interface (CLI) is still used when full control over the operating system is required.

A desktop environment typically consists of icons, windows, toolbars, folders, wallpapers and desktop widgets (see Elements of graphical user interfaces and WIMP). A GUI might also provide drag and drop functionality and other features that make the desktop metaphor more complete. A desktop environment aims to be an intuitive way for the user to interact with the computer using concepts which are similar to those used when interacting with the physical world, such as buttons and windows.

While the term desktop environment originally described a style of user interfaces following the desktop metaphor, it has also come to describe the programs that realize the metaphor itself. This usage has been popularized by projects such as the Common Desktop Environment, KDE, and GNOME.

Implementation

On a system that offers a desktop environment, a window manager in conjunction with applications written using a widget toolkit are generally responsible for most of what the user sees. The window manager supports the user interactions with the environment, while the toolkit provides developers a software library for applications with a unified look and behavior.

A windowing system of some sort generally interfaces directly with the underlying operating system and libraries. This provides support for graphical hardware, pointing devices, and keyboards. The window manager generally runs on top of this windowing system. While the windowing system may provide some window management functionality, this functionality is still considered to be part of the window manager, which simply happens to have been provided by the windowing system.

Applications that are created with a particular window manager in mind usually make use of a windowing toolkit, generally provided with the operating system or window manager. A windowing toolkit gives applications access to widgets that allow the user to interact graphically with the application in a consistent way.

History and common use

Further information: History of the graphical user interface

The first desktop environment was created by Xerox and was sold with the Xerox Alto in the 1970s. The Alto was generally considered by Xerox to be a personal office computer; it failed in the marketplace because of poor marketing and a very high price tag. With the Lisa, Apple introduced a desktop environment on an affordable personal computer, which also failed in the market.

The desktop metaphor was popularized on commercial personal computers by the original Macintosh from Apple in 1984, and was popularized further by Windows from Microsoft since the 1990s. As of 2014, the most popular desktop environments are descendants of these earlier environments, including the Windows shell used in Microsoft Windows, and the Aqua environment used in macOS. When compared with the X-based desktop environments available for Unix-like operating systems such as Linux and BSD, the proprietary desktop environments included with Windows and macOS have relatively fixed layouts and static features, with highly integrated "seamless" designs that aim to provide mostly consistent customer experiences across installations.

Microsoft Windows dominates in marketshare among personal computers with a desktop environment. Computers using Unix-like operating systems such as macOS, ChromeOS, Linux, BSD or Solaris are much less common; however, as of 2015 there is a growing market for low-cost Linux PCs using the X Window System or Wayland with a broad choice of desktop environments. Among the more popular of these are Google's Chromebooks and Chromeboxes, Intel's NUC, the Raspberry Pi, etc.

On tablets and smartphones, the situation is the opposite, with Unix-like operating systems dominating the market, including the iOS (BSD-derived), Android, Tizen, Sailfish and Ubuntu (all Linux-derived). Microsoft's Windows phone, Windows RT and Windows 10 are used on a much smaller number of tablets and smartphones. However, the majority of Unix-like operating systems dominant on handheld devices do not use the X11 desktop environments used by other Unix-like operating systems, relying instead on interfaces based on other technologies.

Desktop environments for the X Window System

A brief timeline of the most popular modern desktop environments for Unix-like operating systems (greyscale logos indicate when the project's development started, while colorized logos indicate the project's first release)

Further information: Comparison of X Window System desktop environments

On systems running the X Window System (typically Unix-family systems such as Linux, the BSDs, and formal UNIX distributions), desktop environments are much more dynamic and customizable to meet user needs. In this context, a desktop environment typically consists of several separate components, including a window manager (such as Mutter or KWin), a file manager (such as Files or Dolphin), a set of graphical themes, together with toolkits (such as GTK+ and Qt) and libraries for managing the desktop. All these individual modules can be exchanged and independently configured to suit users, but most desktop environments provide a default configuration that works with minimal user setup.

Some window managers‍—‌such as IceWM, Fluxbox, Openbox, ROX Desktop and Window Maker‍—‌contain relatively sparse desktop environment elements, such as an integrated spatial file manager, while others like evilwm and wmii do not provide such elements. Not all of the program code that is part of a desktop environment has effects which are directly visible to the user. Some of it may be low-level code. KDE, for example, provides so-called KIO slaves which give the user access to a wide range of virtual devices. These I/O slaves are not available outside the KDE environment.

In 1996 the KDE was announced, followed in 1997 by the announcement of GNOME. Xfce is a smaller project that was also founded in 1996, and focuses on speed and modularity, just like LXDE which was started in 2006. A comparison of X Window System desktop environments demonstrates the differences between environments. GNOME and KDE were usually seen as dominant solutions, and these are still often installed by default on Linux systems. Each of them offers:

• To programmers, a set of standard APIs, a programming environment, and human interface guidelines.
• To translators, a collaboration infrastructure. KDE and GNOME are available in many languages.
• To artists, a workspace to share their talents.
• To ergonomics specialists, the chance to help simplify the working environment.
• To developers of third-party applications, a reference environment for integration. OpenOffice.org is one such application.
• To users, a complete desktop environment and a suite of essential applications. These include a file manager, web browser, multimedia player, email client, address book, PDF reader, photo manager, and system preferences application.

In the early 2000s, KDE reached maturity. The Appeal and ToPaZ projects focused on bringing new advances to the next major releases of both KDE and GNOME respectively. Although striving for broadly similar goals, GNOME and KDE do differ in their approach to user ergonomics. KDE encourages applications to integrate and interoperate, is highly customizable, and contains many complex features, all whilst trying to establish sensible defaults. GNOME on the other hand is more prescriptive, and focuses on the finer details of essential tasks and overall simplification. Accordingly, each one attracts a different user and developer community. Technically, there are numerous technologies common to all Unix-like desktop environments, most obviously the X Window System. Accordingly, the freedesktop.org project was established as an informal collaboration zone with the goal being to reduce duplication of effort.

As GNOME and KDE focus on high-performance computers, users of less powerful or older computers often prefer alternative desktop environments specifically created for low-performance systems. Most commonly used lightweight desktop environments include LXDE and Xfce; they both use GTK+, which is the same underlying toolkit GNOME uses. The MATE desktop environment, a fork of GNOME 2, is comparable to Xfce in its use of RAM and processor cycles, but is often considered more as an alternative to other lightweight desktop environments.

For a while, GNOME and KDE enjoyed the status of the most popular Linux desktop environments; later, other desktop environments grew in popularity. In April 2011, GNOME introduced a new interface concept with its version 3, while a popular Linux distribution Ubuntu introduced its own new desktop environment, Unity. Some users preferred to keep the traditional interface concept of GNOME 2, resulting in the creation of MATE as a GNOME 2 fork.

Examples of desktop environments

The most common desktop environment on personal computers is Windows Shell in Microsoft Windows. Microsoft has made significant efforts in making Windows shell visually pleasing. As a result, Microsoft has introduced theme support in Windows 98, the various Windows XP visual styles, the Aero brand in Windows Vista, the Microsoft design language (codenamed "Metro") in Windows 8, and the Fluent Design System and Windows Spotlight in Windows 10. Windows shell can be extended via Shell extensions.

Many mainstream desktop environments for Unix-like operating systems, including KDE, GNOME, Xfce, and LXDE, use the X Window System or Wayland, any of which may be selected by users, and are not tied exclusively to the operating system in use. The desktop environment for macOS, which is also a Unix-like system, is Aqua, which uses the Quartz graphics layer, rather than using X or Wayland.

A number of other desktop environments also exist, including (but not limited to) CDE, EDE, GEM, IRIX Interactive Desktop, Sun's Java Desktop System, Jesktop, Mezzo, Project Looking Glass, ROX Desktop, UDE, Xito, XFast. Moreover, there exists FVWM-Crystal, which consists of a powerful configuration for the FVWM window manager, a theme and further adds, altogether forming a "construction kit" for building up a desktop environment.

X window managers that are meant to be usable stand-alone — without another desktop environment — also include elements reminiscent of those found in typical desktop environments, most prominently Enlightenment. Other examples include OpenBox, Fluxbox, WindowLab, Fvwm, as well as Window Maker and AfterStep, which both feature the NeXTSTEP GUI look and feel. However newer versions of some operating systems make self configure.

The Amiga approach to desktop environment was noteworthy: the original Workbench desktop environment in AmigaOS evolved through time to originate an entire family of descendants and alternative desktop solutions. Some of those descendants are the Scalos, the Ambient desktop of MorphOS, and the Wanderer desktop of the AROS open source OS. WindowLab also contains features reminiscent of the Amiga UI. Third-party Directory Opus software, which was originally just a navigational file manager program, evolved to become a complete Amiga desktop replacement called Directory Opus Magellan.

OS/2 (and derivatives such as eComStation and ArcaOS) use the Workplace Shell. Earlier versions of OS/2 used the Presentation Manager.

The BumpTop project was an experimental desktop environment. Its main objective is to replace the 2D paradigm with a "real-world" 3D implementation, where documents can be freely manipulated across a virtual table.