Does it need a feasible starting basis?

No. That is a defining distinction of the classical criss-cross approach.

Must the objective improve at every pivot?

No. The method does not generally preserve a monotone sequence of feasible objective values.

Is any sign-based pivot rule finite?

No. A finiteness result applies to a specified rule under its assumptions, not to every plausible modification.

AI Glossary / Mathematics and optimization / Advanced

Criss-cross algorithm

Definition

The criss-cross algorithm is a family of pivot methods for linear programming that can start from a basis without requiring primal or dual feasibility. It exchanges basic and nonbasic variables according to sign-based rules until it obtains an optimality or inconsistency certificate. The classical least-index version has a finite-termination proof under exact arithmetic.

What it means

Linear programming chooses variables to optimize a linear objective under linear constraints. A basis provides an algebraic description of a candidate solution, but that candidate may violate nonnegativity or fail the associated dual conditions.

The primal simplex method normally preserves primal feasibility once its main optimization phase begins. A criss-cross method permits intermediate bases outside that feasible region. Its path therefore need not move steadily through feasible vertices or improve the objective monotonically. What makes the method valid is its pivot rule and termination reasoning, not continuous improvement of every intermediate candidate.

How it works

Express the linear program as a dictionary: each basic variable is a constant plus a linear combination of nonbasic variables. Setting nonbasic variables to zero defines the current basic solution. For a maximization dictionary in this convention, negative basic constants violate primal feasibility, while positive objective coefficients violate dual feasibility.

Fix an ordering of variable indices. The least-index rule chooses the smallest-index variable among those sign violations. A violated basic row seeks a nonbasic column with a suitable positive coefficient; a violated objective column seeks a basic row with a suitable negative coefficient. Among eligible choices, the fixed ordering selects the pivot partner.

Pivot by solving one dictionary equation for the entering variable and substituting throughout. If no sign violations remain, the basis is optimal. If the required partner does not exist, the terminal sign pattern supplies an inconsistency certificate, interpreted for the relevant primal or dual problem.

Three practical examples

1. Linear-programming education: demonstrate how an algorithm can solve a problem without first constructing a primal-feasible starting solution.

2. Exact optimization research: study finite pivot sequences and certificates using rational arithmetic, separating combinatorial rules from floating-point tolerances.

3. Solver experimentation: compare a specified criss-cross variant with other pivot methods on linear formulations, measuring total work rather than assuming that a simpler rule is automatically faster.

Think of it this way

Think of rearranging a system of bookkeeping equations while temporarily allowing the displayed provisional balances to violate the final rules. Each rearrangement remains algebraically valid, and the goal is a representation in which the required sign conditions all hold.

The analogy does not permit a business to act on an infeasible intermediate plan. These are internal computational states. The final certificate, not the provisional balances, determines what the algorithm has established.

Worked example

Consider the original problem maximize x subject to 1≤x≤3 and x≥0. Introduce nonnegative variables s₁=x−1 and s₂=3−x. Start with s₁=−1+x, s₂=3−x and objective z=x, treating x as nonbasic.

At x=0 the basic values are s₁=−1 and s₂=3. The starting solution is infeasible because s₁ is negative. The objective coefficient of x is also positive, so the dictionary has both primal and dual sign violations.

Fix the variable order x<s₁<s₂. The smallest-index violated variable is x. Its column has coefficient +1 in the s₁ row and −1 in the s₂ row. The eligible negative coefficient therefore selects s₂ to leave the basis.

Solve s₂=3−x for x, obtaining x=3−s₂. Substitute into the other expressions: s₁=2−s₂ and z=3−s₂. Now s₂ is nonbasic. Setting it to zero gives x=3 and s₁=2, both nonnegative, and the objective coefficient of s₂ is −1. The dictionary is optimal.

The independent bound x≤3 confirms the objective cannot exceed 3. This hand-checked one-pivot illustration starts infeasibly but does not show every possible criss-cross behavior, degeneracy or certificate case.

Illustrative case study

Fictional case: an optimization class develops a small planning prototype using exact rational inputs. Students choose a basis that violates a minimum-production requirement. Rather than modifying the model or treating the provisional plan as valid, they apply a documented least-index criss-cross rule.

The teaching report records each basis and the final certificate. When moving to decimal input, the team separately investigates numerical tolerances and coefficient scaling. It does not infer that the exact-arithmetic finiteness theorem automatically prevents every numerical difficulty in its implementation.

Common misconceptions and mistakes

Do not assume “infeasible intermediate solution” means the original problem has no feasible solution. The example starts with a bad basis for a feasible problem.

Do not apply an arbitrary pivot and expect the least-index termination proof to remain valid. Ordering and eligibility conditions are part of the algorithm.

Do not equate finite termination with polynomial-time complexity or superior practical speed. Also distinguish primal inconsistency, dual inconsistency and primal unboundedness carefully: a certificate must be interpreted with the formulation and any established feasibility conditions in view.

Business use

The method is valuable for understanding primal-dual structure and for specialized algorithmic work. A business evaluating optimization software should focus on accurate certificates, reliable numerical handling and representative performance rather than the method's appealingly simple description.

Specify whether calculations use exact arithmetic or floating-point approximations. Check reported feasibility and objective values against the original constraints. If comparing solvers, include preprocessing, factorization updates and certificate verification in the cost; a pivot count alone is incomplete evidence of efficiency.

Check your understanding

Why is the initial x=0 in the example not evidence that the model is infeasible?

Answer: It violates the lower bound, but another value such as x=3 satisfies all constraints. Initial basic infeasibility is a property of that candidate, not the entire feasible set.

Related terms

Linear programming
Basis
Dictionary
pivot
primal feasibility
dual feasibility
simplex method
optimality certificate

Learn next

follow the same example with a different fixed variable ordering and verify the resulting dictionaries. Then study terminal sign patterns and how they certify primal or dual inconsistency.

Fixed variable

Sources

Sources: Komei Fukuda, “Introduction to Optimization,” Chapter 4 and Section 4.4.1, primary author notes and least-index pseudocode read: https://people.inf.ethz.ch/fukudak/lect/opt2011/aopt11note2.pdf . The entry addresses linear-programming criss-cross pivot methods, not similarly named population heuristics. Worked dictionary and case are original; no software run is claimed.

Previous: Credence (statistics) Next: Criterion validity