All Pages
From Glossary
Saddlepoint 
Let Then, is a saddle point of if minimizes on , and maximizes on . Equivalently,
Von Neumann (1928) proved this equivalent to:
A sufficient condition for a saddle point to exist is that and are nonempty, compact, convex sets, is convex on for each in , and is concave on for each in .
Saddle point equivalence underlies duality. See also Lagrangian saddlepoint equivalence as well as the associated supplement.
Satisfiability problem 
(SAT). Find a truth assignment to logical propositions such that a (given) collection of clauses is true (or ascertain that at least one clause must be false in every truth assignment). This fundamental problem in computational logic forms the foundation for NPcompleteness. When SAT is in conjunctive normal form and may not be satisfiable, we define the problem of maximizing the number of true clauses as MAXSAT.
Scaling 
Changing the units of measurement, usually for the numerical stability of an algorithm. The variables are transformed as where The diagonal elements are the scale values, which are positive: Constraint function values can also be scaled. For example, in an LP, the constraints can be scaled by where such that (This affects the dual values.) Some LP scaling methods simply scale each column of A by dividing by its greatest magnitude (null columns are identified and removed).
Example  A column scaling  A row scaling  



Another method is logarithmic scaling, which scales by the logarithm of the greatest magnitude. More sophisitcated methods are algorithmic, taking both row and column extremes into account.
Scatter search 
This is a populationbased metaheuristic, starting with a collection of reference points, usually obtained by the application of some heuristic. A new point is created by taking combinations of points in the population, and rounding elements that must be integervalued. It bears some relation to a genetic algorithm, except that scatter search uses linear combinations of the population, while the GA ``crossover operation can be nonlinear.
Scheduling 
(e.g., jobs). A schedule for a sequence of jobs, say is a specification of start times, say such that certain constraints are met. A schedule is sought that minimizes cost and/or some measure of time, like the overall project completion time (when the last job is finished) or the tardy time (amount by which the completion time exceeds a given deadline). There are precedence constraints, such as in the construction industry, where a wall cannot be erected until the foundation is laid.
There is a variety of scheduling heuristics. Two of these for scheduling jobs on machines are list heuristics: the Shortest Processing Time (SPT), and the Longest Processing Time (LPT). These rules put jobs on the list in nondecreasing and nonincreasing order of processing time, respectively.
Other scheduling problems, which might not involve sequencing jobs, arise in production planning.
Scope 
The scope of a constraint is the set of directly constrained variables. For example, in the constraint , the set is the scope.
Search 
Search is a systematic way of trying out different values for variables until a solution is found that satisfies all constraints or it is proven that no solution exists.
During search, a search tree is constructed where each node represents the current state of the variables and edges represent value assignments to a particular variable. This means, with increasing depth of the search tree, more variables are assigned to specific values.
Search tree 
The tree formed by a branch and bound algorithm strategy. It is a tree because at each (forward) branching step the problem is partitioned into a disjunction. A common one is to dichotomize the value of some variable, This creates two nodes from the parent:
Secant method 
A method to find a root of a univariate function, say F. The iterate is
If
the order of convergence is the golden mean, say g (approx.= 1.618), and the limiting ratio is:
Secondorder conditions 
This descends from classical optimization, using the secondorder term in Taylor's expansion. For unconstrained optimization, the secondorder necessary condition (for ) is that the hessian is negative semidefinite (for a max). Secondorder sufficient conditions are the firstorder conditions plus the hessian be negative definite. For constrained optimization, the secondorder conditions are similar, using projection for a regular mathematical program and the Lagrange Multiplier Rule. They are as follows (all functions are in and the mathematical program is in standard form, for a local maximum):
 Secondorder necessary conditions. There exist Lagrange multipliers, (u,v), such that and for which: (1) and (2) is negative semidefinite on the tangent plane.
 Secondorder sufficient conditions. The above necessary conditions hold but with (2) replaced by (2') H_x[L(x*,u,v)] is negative definite on the tangent plane.
Self concordance 
Properties of a function that yield nice performance of Newton's method used for line search when optimizing a barrier function. Specifically, let B be a barrier function for with strict interior Let x be in S and let d be a direction vector in such that the line segment is in S for where Then, define by:
(while noting that F depends on x and d). The function F is selfconcordant if it is convex in C^{3} and satisfies the following for all x and d:
One calls F kselfconcordant in an open convex domain if
The logarithmic barrier function, associated with linear programming, is selfconcordant with
This further extends naturally to functions in
Semiassignment problem 
This is like the assignment problem, except only the rows or the columns (not both) of the assignment matrix is constrained to equal 1. With linear objective, the problem is:
(The sum constraint could be over j, for all i.) An example is to assign jobs to people, but allow some jobs to be assigned to more than one person and some jobs not assigned at all. A more realistic example arises in biology. We are given a rotamer library of side chain confirmations, and each amino acid residue in a protein must be assigned some rotamer. The same rotamer could be assigned to more than one site, and some rotamers need not be assigned at all.
Semidefinite program 
where is the class of positive semidefinite matrices, and where each for is a (given) symmetric matrix. This includes the linear program as a special case.
Semiinfinite program 
A mathematical program with a finite number of variables or constraints, but an infinite number of constraints or variables, respectively. The randomized program is a semiinfinite program because it has an infinite number of variables when X is not finite.
Sensitivity analysis 
The concern with how the solution changes if some changes are made in either the data or in some of the solution values (by fixing their value). Marginal analysis is concerned with the effects of small perturbations, maybe measurable by derivatives. Parametric analysis is concerned with larger changes in parameter values that affect the data in the mathematical program, such as a cost coefficient or resource limit.
Under suitable assumptions, the multipliers in the Lagrange Multiplier Rule provide derivatives of the optimal response function – i.e., under certain conditions, For special approaches in LP, see compatibility theory, the 100% Rule, and the tolerance approach.
Separable program 
The functions are separable:
The classical (LP) approaches to separable programming are called lambdaform and deltaform, both using piecewise linear approximations.
Let be a specified set of points, where and let be decision variables that are the coefficients of convex combinations, giving the following linear program:
A restricted basis entry rule is invoked during the simplex method to yield an approximate solution. (However, this is dominated by the Generalized Lagrange Multiplier method, which can be viewed as generating the approximating breakpoints posteriori, getting successively finer near the solution.)
The delta form uses the differences: The associated functional differences are:
Then, the approximating LP is:
where and (a similar constant was dropped from the objective). Another restricted basis rule is invoked: implies for all and all .
Separating hyperplane 
A hyperplane for which two (given) sets lie in opposite halfspaces. The separation is strict if the two sets are contained in their respective open halfspace.
____  ____    \ /  S1   /S2\ ____  \__/  separating hyperplane (line)
Sequencing problems 
Finding an ordering, or permutation, of a finite collection of objects, like jobs, that satisfies certain conditions, such as precedence constraints.
Sequential decision process 
See dynamic programming and Timestaged models.
Sequential linear programming 
(SLP). Solving a nonlinear program by a sequence of linear approximations and using linear programming to solve each one. The linear approximations are usually done by using the firstorder Taylor expansion.
Sequential quadratic programming 
(SQP). Solving a nonlinear program by a sequence of quadratic approximations and using quadratic programming to solve each one. The approximations are usually done by using the secondorder Taylor expansion.
Sequential unconstrained minimization technique 
(SUMT). This is the penalty function approach.
Set constraint 
A set constraint is a constraint on one or more set variables. For example, the following are common set constraints:
 for ground values (e.g., integers)
Set covering problem 
See covering problem.
Set variable 
A variable (often in constraint programming) whose value is a set, and therefore whose domain is the powerset of all elements.
For example, the set of all people who will be in the group that will play golf Sunday starting at 3 PM can be represented as a set variable.
Shadow price 
An economic term to denote the rate at which the optimal value changes with respect to a change in some righthand side that represents a resource supply or demand requirement. (This is sometimes taken as synonymous with the dual price, but this can be erroneous, as in the presence of degeneracy – see marginal price.) Also see pricing.
ShermanMorrison formula 
This is a useful identity:
where is a nonsingular matrix and and are nvectors, provided the inverse (on the left) exists.
Shortest path 
In a graph or network, this is a path from one node to another whose total cost is the least among all such paths. The "cost" is usually the sum of the arc costs, but it could be another function (e.g., the product for a reliability problem, or max for a fuzzy measure of risk). There are some particular labeling algorithms given.
Signomial 
The difference between two posynomials. This class of function defines the general geometric program.
Simplex 
(pl. simplices). For , this is a point For n=2, this is a line segment, joining points (1,0) and (0,1). For this is a triangle, joining the vertices (1,0,0), (0,1,0), and (0,0,1). This is sometimes called an nsimplex, denoted by (note its dimension is n1). The open simplex excludes the axes:
More generally, some authors define a simplex to be the convex hull of any affinely independent vectors, and refer to the special case of the unit vectors as the standard simplex.
Simplex method 
An algorithm invented to solve a linear program by progressing from one extreme point of the feasible polyhedron to an adjacent one. The method is an algorithm strategy, where some of the tactics include [[Pricing]]ricing and [[Pivot]]ivot selection.
The elementary simplex method is the name of Dantzig's original (1947) algorithm, with the following rules applied to the standard form:
 Let reduced cost of terminate if
 Select as one of greatest magnitude.
 In the associated column () of the tableau, compute the min ratio: (If LP is unbounded).
 Enter into the basic set, in exchange for , and update the tableau.
Among the variations are:
 select the incoming variable (j) differently;
 select the outgoing variable (i) differently, especially to avoid cycling;
 do not maintain a tableau (use a factored form of the basis).
The revised simplex method is the use of a particular factored form of the basis: (after k iterations), where each is an elementary matrix. Then, the revised simplex method uses forward transformation to pivot and backward transformation to update the pricing vector. (For this distinction, the elementary simplex method is sometimes called the tableau method.)
The simplex method draws its name from imagining a normalization constraint, and thinking of the jth column of to be selected by the weight in Then, at an iteration, an msimplex is specified by the basic variables, and an adjacent simplex is chosen to improve the objective value. This view is in requirements space.
(For a different algorithm, used as a heuristic in NLP, see the NelderMead simplex method.)
Simplex multiplier 
See pricing.
Simplicial subdivision 
Given a simplex, , its simplicial subdivision is a collection of simplices, say such that and for any and , either the intersection is empty or equals the closure of a common face. The mesh of the subdivision is the diameter of the largest subsimplex. This arises in a fixed point approach to compute an economic equilibrium.
Simulated annealing 
An algorithm for solving hard problems, notably combinatorial programs, based on the metaphor of how annealing works: reach a minimum energy state upon cooling a substance, but not too quickly in order to avoid reaching an undesirable final state. As a heuristic search, it allows a nonimproving move to a neighbor with a probability that decreases over time. The rate of this decrease is determined by the cooling schedule, often just a parameter used in an exponential decay (in keeping with the thermodynamic metaphor). With some (mild) assumptions about the cooling schedule, this will converge in probability to a global optimum.
Skew symmetric matrix 
is square and
Slack variable 
In an inequality constraint of the form the slack is which is designated by the slack variable, . Then, the original constraint is equivalent to the defining equation,
Slater condition 
Originally for the purely inequality system with g convex, it means there exists for which More generally, for a mathematical program in standard form, it means there exists for which
Smooth 
A function is smooth if it has continuous first derivatives.
Soft constraint 
A soft constraint can be seen as a preferential constraint whose satisfaction is not required but preferred. Originally, soft constraints were proposed to model and solve overconstrained problems, i.e., the problems where there is no solution satisfying all the constraints. By weakening some constraints into soft constraints, we can find a solution satisfying all the hard constraints and as many soft constraints as possible.
See also:
Spanning tree 
A subgraph that is a tree containing all nodes. The max weight spanning tree problem is to find a spanning tree such that the sum of (given, positive) weights of the edges is a maximum.
 The max spanning tree problem is solvable by the following greedy algorithm:
 Input. connected graph with weights,
 Output. maximum weight spanning tree, T.
 Initialization: Set graph with given nodes and no edges.
 Iteration (until ): Test if the kth edge forms a cycle with T. If not, add it to T; if so, discard the edge. In either case, increment k and iterate.
Here is a supplement, Greedy Algorithms for Minimum Spanning Tree.
Sparsity 
The fraction of zeroes in a matrix. If is and for of its elements, its sparsity is Large linear programs tend to be very sparse, increasingly so as the dimensions grow. For example, consider the standard transportation problem with s sources and d destinations. This has constraints and variables. Each column, however, has exactly 2 nonzeroes since A is the incidence matrix of the network, so its sparsity is which decreases as the number of sources and/or destinations grows large.
The sparsity of a simple graph (or network) is the sparsity of its adjacency matrix. More generally, the sparsity of a multigraph refers to the average degree of its nodes.
See super sparsity for extensions of this idea.
Specially ordered set 
(SOS). These are sets of nonnegative variables that are required to sum to 1. For computational efficiency, it is sometimes better to define these sets by some marking data structure, rather than include them along with other equality constraints. There are two types of SOSs, distinguished by what they represent. A Type 1 SOS is when each variable is binary, so the constraint is one of Multiple Choice. A Type 2 SOS is when a restricted basis entry rule is used, as in the lambdaform of separable programming.
Spectral radius 
The spectral radius of a matrix, . The radius of a disk that contains the spectrum:
Spectrum 
The set of eigenvalues of a matrix.
Speed of convergence 
See convergence.
Stability region 
The set of parameter values for which an optimal solution remains optimal. This arises naturally when solving combinatorial programs, where a solution is often a subgraph, such as a tree, and the question is for what range of arc weights is this subgraph optimal (such as a spanning tree that is minimum for given weights). More generally, could be a solution generated by some algorithm, , from an initial value Then, suppose the feasibility region depends on the parameter , say and the objective also depends on , say Let denote the generated solution from algorithm A, starting at with parameter value Let the parameter set be (which includes ). The stability region of is The algorithm may be a heuristic, so need not be optimal. For example, one could use an nOpt heuristic for the travelling salesman problem, so x represents a tour. The parameters could be the costs, or they could be the location of each point in a Euclidean TSP. The stability region is the set of costs, or coordinates in the plane, for which the tour generated by nOpt is the same.
Stable math program 
Roughly, one whose solution does not change much under perturbation. For the inequality case, we have the following
 Stability conditions:
 is bounded for some
The first stability condition pertains to upper semicontinuity and the second, called the closure condition, pertains to lower semicontinuity.
 The conditions are not only sufficient to ensure the respective semicontinuity, but they are necessary when:
 is bounded.
Stable set 
Same as independent set
Standard linearization 
The standard way to linearize the product of two binary variables and is to replace with a continuous variable and add four linear inequalities as auxiliary constraints:
Collectively, these imply for all binary values of and . This can be generalized for the product of binary variables for all in some index set by replacing
with a continuous variable and adding auxiliary constraints:
Stationary point 
Usually this is used to mean a KuhnTucker point, which specializes to one for which grad_f(x)=0 if the mathematical program is unconstrained. In the context of an algorithm, it is a fixed point.
Stationary policy 
In a dynamic program, this is a policy that is independent of time – i.e., (some function of state, but not of time, t).
Steel beam assortment problem 
A steel corporation manufactures structured beams of a standard length, but a variety of strengths. There is a known demand of each type of strength, but a stronger one may fulfill demand (or part thereof) for another beam (but not conversely). The manufacture of each type of steel beam involves a fixed charge for its setup. In addition, there is a shipping cost proportional to the difference in the demanded strength and the actual strength, and proportional to the quantity shipped.
Let = number of varieties of strengths = demand for beam of strength (where ) amount of beams of strength manufactured manufacturing cost of units of beam of strength (incl. fixed charge) total excess of beams of strength before fulfilling demand shipping cost
Although does not index time, the mathematical program for this problem is the same form as the production scheduling problem, using the inventory balance equations to relate and . This is valid because implies can be used to fulfill demand (Also, note that here is not a "holding cost".)
Steepest ascent 
(descent, if minimizing). This is a class of algorithms, where such that the direction vector d is chosen by maximizing the initial "velocity" of change, and the step size is chosen by line search. Generally used in the context of unconstrained optimization, the mathematical program is where (For descent, change Max to Min.) Then, is chosen to maximize the firstorder Taylor approximation, subject to a normalization constraint: where denotes the norm of the direction vector, . When the Euclidean norm is used, this yields the original steepest ascent algorithm by Cauchy, which moves in the direction of the gradient:
(No direction vector is sought if such algorithms stop when reaching a stationary point.)
Other norms, such as where is symmetric and positive definite, lead to other directions that are steepest relative to that norm. In particular, if this yields the modified Newton method.
Steiner problem 
Find a subgraph of a graph, say such that contains (a specified subset of nodes), and is minimized. It is generally assumed When this is the shortest path problem. When this is the (minimum) spanning tree problem.
Step size 
This is a scalar in an algorithm of the form: where is the direction vector. After is chosen (nonzero), the step size is specified. One step size selection rule is line search; another is a fixed sequence, like
Stochastic matrix 
A nonnegative matrix whose row sums are each 1. (A column stochastic matrix is one whose column sums are 1.) This arises in dynamic programs whose state transition is described by a stochastic matrix containing the probabilities of each transition.
Stochastic program 
It is written in the form of a mathematical program extended to a parameter space whose values are random variables (generally with known distribution function). This is converted to a standard form by forming a certainty equivalent.
 Here are some certainty equivalents:
 Average value. Replace all random variables with their means.
 Chance constraint. Given a stochastic program with a random variable, p, in its constraint:
a certainty equivalent is to replace this with the constraint,
where is a (known) probability function on the range of , and is some acceptance level ( means the constraint must hold for all values of , except on a set of measure zero). Some models separate constraints with several levels:
The case of one chance constraint with the only random variable being the righthand side is particularly simple. Suppose is the cumulative distribution function of for the chance constraint If is a continuous random variable and is continuous and strictly increasing, the chance constraint is equivalent to (where is the inverse function of ). In particular, if the program remains linear.  Recourse model. This assumes decisions are made over time where the effect of an early decision can be compensated by later decisions. The objective is to optimize the expected value. The 2stage model has the form:
(Sums could be replaced by other operators.) Once is implemented, becomes known and is chosen. The certainty equivalent is: where
for all p2 (except on set of measure zero). (E[] denotes the expected value.) The 'Sup' is used to define the second stage value for a particular value of because the choice of might be infeasible. The nature of the recourse model is pessimistic: must be chosen such that the original constraints hold no matter what the values of the random variables. With a finite number of possibilities, this means a system of constraints for each possible realization of This extends recursively to a kstage model. The linear 2stage recourse model has the form:
where
Here the second stage variable is denoted it is determined after has been set and the random variable has been realized. The LP data depend on as functions, and The fixed recourse model has The complete recourse model assumes it fixed and is all of (where = number of rows of ). This means that no matter what value of is chosen for the first stage, there is feasible recourse This is simple recourse if so we can think of y as having two parts: and The second stage LP simplifies to the following:
Also see robust optimization. The certainty equivalent depends upon the underlying decision process. If it is adaptive, the recourse model applies (but RO might be more practical). The chance constraint model represents a notion of an allowed frequency of violations, as in environmental control models.
Strict interior 
Let be the level set of Then, its strict interior is (This is not to be confused with the relative interior or the set interior  see Myths and Counter Examples in Mathematical Programming.)
Strict optimum 
Same as proper optimum.
Strictly complementary 
Each complementary pair of variables must have exactly one zero (the other positive).
Strictly concave function 
Negative is strictly convex.
Strictly convex function 
A convex function that also satisfies the defining inequality strictly for distinct points, say x and y:
Strictly quasiconcave function 
Negative is strictly quasiconvex.
Strictly quasiconvex function 
is a convex set and for which and is in (0, 1). (Note: need not be quasiconvex  see Myths and Counter Examples in Mathematical Programming.)
Strong duality 
See dual
Strongly concave function 
Negative is strongly convex.
Strongly convex function 
Arises for eigenvalues of hessian are bounded away from zero (from below): there exists such that for all For example, the function is strictly convex on but its second derivative is which is not bounded away from zero. The minimum is not achieved because the function approaches its infimum of zero without achieving it for any (finite) Strong convexity rules out such asymptotes.
Strongly quasiconcave function 
Negative is strongly quasiconvex.
Strongly quasiconvex function 
( on ). is a convex set and with and
Structural variable 
See linear program.
Subadditive function 
(where in the domain implies is in the domain).
Subdifferential 
(of at ). Also see conjugate function. If is convex and differentiable with gradient,
The subdiffenential is built on the concept of supporting hyperplane, generally used in convex analysis. When is differentiable in a deleted neighborhood of (but not necessarily at ), the Bsubdifferential is the set of limit points:
If is continuously differentiable in a neighborhood of (including ),
Otherwise,
is generally not a convex set. For example, if
The Clarke subdifferential is the convex hull of
Subgradient 
A member of the subdifferential.
Sublinear rate of convergence 
See convergence.
Submodular function 
Let be a finite set and let be a function on the subsets of into . Then, is submodular if it satisfies:
Example:
(binary nvectors) and
Instance:
Then,
(The linearity of Sum makes the inequality hold with inequality.)
Subspace 
A subset of a vector space that is, itself, a vector space. An example is the null space of a matrix, as well as its orthogonal complement.
Substitution 
See forward substitution and backward substitution.
Successive approximation 
The iterative scheme by which an approximation is used for the basic design of an algorithm. The sequence generated is of the form where is an algorithm map specified by its approximation to some underlying goal. Typically, this is used to find a fixed point, where (e.g., seeking let so the iterations are converging to if f satisfies certain conditions, such as a contraction map).
 Here are some special types:
 Inner approximation
 Outer approximation
 Successive Linear Approximation
 Successive Quadratic Approximation
Sufficient matrix 
Let be an matrix. Then, is column sufficient if
is row sufficient if its transpose is column sufficient. is sufficient if it is both column and row sufficient. One example is when is symmetric and positive semidefinite. Here is an example of a matrix that is column sufficient, but not row sufficient:
This arises in linear complementarity problems.
Super sparsity 
The fraction of distinct nonzero values in a matrix. If a matrix has z nonzeros i.e. z = sparsity × m × n, then the supersparsity is number of distinct values divided by z. Although related to the idea of sparsity, a matrix can be highly supersparse yet not sparse. For example if for all then sparsity is 0 but supersparsity is
These matrices arise naturally in models with repetitive substructures. For example, a process may be modeled as a linear program with activities that convert raw materials into finished products (like a refinery converting crude oil into petroleum products). The yields are determined by the engineering, so this model would be the same if embedded into a larger linear program that uses it in numerous regions. Then, the yield values are replicated for each region, which makes the resulting linear program matrix supersparse. Additionally, any network problem in which the coefficient matrix is the incidence matrix is supersparse. This leads to the special case of only zeros and ones.
Superadditive function 
Negative is subadditive.
Superbasic variable 
When using a method like the convex simplex method or projected gradient, the nonbasic variables are partitioned into those that are at one of their bound values and those that are not. The latter are called superbasic.
Superconsistent 
Arises in geometric programming, and in semiinfinite programming as one that satisfies the Slater interiority condition.
Superlinear rate of convergence 
See convergence.
Supermodular function 
Negative is submodular.
Support set 
of
Supporting hyperplane 
Supporting hyperplane of a set, S. A hyperplane that contains S in one of its closed halfspaces and intersects the closure of S with at least one point.
Suppose S is closed and convex. A key fact is that every supporting hyperplane contains an extreme point of S. If S is a polyhedron, the facets define a finite collection of supporting hyperplanes that completely determine the polyhedron (as the intersection of the associated halfspaces that contain S).
Supremum 
(abbr. Sup). This is the least upper bound on a (realvalued) function over (a subset of) its domain. If is unbounded from above, and if the domain is empty, Otherwise, suppose U is any upper bound: for all is a least upper bound if, for any there exists in the domain for which (That is, we can get arbitrarily close to in the range of ) Note that the supremum is always defined, and its range is in the extended reals. The supremum is the maximum, if it is attained by some point in its domain.
Surplus variable 
In an inequality constraint of the form the level of surplus is which is designated by the surplus variable, Then, the original constraint is equivalent to the defining equation, plus the nonnegativity,
Surrogate constraint 
An aggregation of the constraints, such as a (nonnegative) linear sum of the (inequalities and) equations. Of special interest is the integer equivalent aggregation. (Also see the surrogate dual in the supplement on duals.)
Surrogate dual 
See it in the supplement on duals.
Surrogate relaxation 
Solving the surrogate dual problem, see the supplement on duals. For given multipliers the surrogate dual objective is the relaxed mathematical program:
(More generally, the surrogate could be a nonlinear combination of the constraints.)
Symbolic CSP 
A CSP is symbolic if its variables range over nonnumeric domains.
Symmetric dual 
See it in the supplement on duals.
Symmetry exclusion 
Symmetry exclusion. Excluding symmetric solutions, usually when solving combinatorial programs. For example, suppose x_{i}j = 1 if item i is assigned to be at position j (in 2 or 3 dimensional space); otherwise, x_{i}j=0. When branching on x_{i}j=1, the alternative optimal value x_ik=1 is being considered for position k that maps from j under reflection, translation, or rotation. So, when considering the complementary branch, x_{i}j=0, the symmetry exclusion condition, x_{i}k=0, is also added. Symmetry exclusion can sometimes be done by ordering variables, or with cutting planes. It arises in most problems with a geometric meaning, including the symmetric traveling salesman problem, where every tour, (1,2,...,n,1), has the symmetric solutions (2,3,...,n,1,2) and (1,n,n1,...,2,1). The first of these symmetries is excluded by defining city 1 as the first (or "home") city. Fixing the home does not exclude the second symmetry, which is a tour reversal. Nongeometric problems can also have symmetries, such as graph coloring; any coloring has the symmetric solution by swapping colors – e.g., every red node becomes green, and every green node becomes red.
Categories: Nonlinear Programming  Common Problems  MIP/CO  Linear Algebra & Geometry  Common Problems  Constraint Programming  Constraint Programming  MIP/CO  Nonlinear Programming  Nonlinear Programming  Nonlinear Programming  Nonlinear Programming  Linear Programming  MIP/CO  Nonlinear Programming  Linear Algebra & Geometry  Common Problems  MIP/CO  Linear Programming  Nonlinear Programming  Nonlinear Programming  Constraint Programming  MIP/CO  Constraint Programming  Linear Programming  Common Problems  MIP/CO  Linear Algebra & Geometry  Linear Programming  Linear Programming  MIP/CO  Linear Programming  Nonlinear Programming  Constraint Programming  Common Problems  MIP/CO  Linear Programming  Linear Programming  MIP/CO  Nonlinear Programming  Nonlinear Programming  Common Problems  Linear Programming  Nonlinear Programming  Common Problems  MIP/CO  Nonlinear Programming  Nonlinear Programming  Linear Programming  Nonlinear Programming  Nonlinear Programming  Nonlinear Programming  Nonlinear Programming  Linear Programming  MIP/CO  Nonlinear Programming  Nonlinear Programming  Nonlinear Programming  MIP/CO  Nonlinear Programming  Linear Algebra & Geometry  Nonlinear Programming  MIP/CO  Nonlinear Programming  MIP/CO  Linear Programming  Linear Algebra & Geometry  Linear Programming  MIP/CO  MIP/CO  Constraint Programming  Linear Programming  MIP/CO