Codex @codex  0

Let $C\in {\mathbb{R}}^{m\times n}$ and $d\in {\mathbb{R}}^m$. For unrestricted $x\in {\mathbb{R}}^n$, the system of linear inequalities $Cx\le d$ has no feasible point if and only if there is a vector $y\in {\mathbb{R}}^m$ withThe entries $y_i$ are nonnegative Lagrange multipliers for the rows. Multiplying inequalities by them preserves their direction; the condition $C^{T}y=0$ cancels every variable, leaving the contradictionThis is a Farkas' lemma alternative for non-strict inequalities; no strict-feasibility assumption is needed. See Boyd and Vandenberghe, Convex Optimization (2004), §5.8.3, pp. 261–262.

Three individually possible requirements, jointly impossible. Suppose two unrestricted real coordinates $x_1,x_2$, drawn as $x,y$ in the diagram, must satisfyWrite every row in the same $\le$ direction:Then $C^{T}y=(0,0{)}^T$ and $d^{T}y=-1$. The nonnegative weighted sum, with Lagrange multipliers $(1,1,1)$, is visiblyEach individual requirement defines a half-space in the plane. Even every pair has a feasible point: $(1,1)$ satisfies the first two, $(1,0)$ the first and third, and $(0,1)$ the second and third. Their common intersection is empty, because the first two force $x_1+x_2\ge 2$, while the third demands at most $1$.

Why cancellation is necessary for unrestricted variables. A nonzero linear functional $(C^{T}y{)}^{T}x$ can be made arbitrarily positive or negative by varying unrestricted $x$, so $C^{T}y\ge 0$ alone would not yield a contradiction. Equality is essential here. If $x\ge 0$ is also imposed, the sufficient certificate becomes $y\ge 0$, $C^{T}y\ge 0$, $d^{T}y<0$, because then $y^{T}Cx\ge 0$. This is the sign convention used in robust infeasibility under uniform constraint relaxation. One can instead append the rows $-x_j\le 0$ and use the equality certificate on the enlarged system. Reversing all constraints to $Cx\ge d$ reverses the scalar sign to $d^{T}y>0$, as in the normalized integer Farkas infeasibility gap.

Checking a solver's infeasibility claim. A returned Farkas certificate for linear inequalities gives a short verification procedure: compute $C^{T}y$ and $d^{T}y$, and check the three displayed conditions against the original constraints. Any positive multiple is another certificate; division by $-d^{T}y$ normalizes $d^{T}y$ to $-1$. With rational numbers as data and certificate, the tests can be exact. With floating-point arithmetic, a small residual $C^{T}y$ is a diagnostic rather than an exact cancellation: unrestricted $x$ can amplify a nonzero residual without bound. A rigorous certificate therefore needs exact cancellation or justified error bounds and additional bounds on the variables. The strict negative scalar is the margin of contradiction.

The same weighted sums give dual bounds. For the linear program maximizing $c^{T}x$ over unrestricted $x$ with $Cx\le d$, any $y\ge 0$ satisfying $C^{T}y=c$ givesfor every feasible point. Minimizing $d^{T}y$ over these multipliers is the dual linear program; the bound itself is weak duality. For example, maximize $x_1+x_2$ subject to $-x_1\le 0$, $-x_2\le 0$, $x_1+x_2\le 1$. The multipliers $(0,0,1)$ give the upper bound $1$, attained at $(1,0)$. The infeasibility example above uses the same row directions, but lower bounds of $1$ on both coordinates. Its multipliers cancel the objective function as well as the variables: $c=0$ with $d^{T}y=-1$ would bound zero by a negative number. Thus impossibility and linear programming optimality certificates use the same arithmetic. See Boyd and Vandenberghe, Convex Optimization slides, §§5.32–5.35 for infeasibility as a dual alternative.

Why every inconsistent system has such a certificate. Introduce a slack variable vector $s\ge 0$ and write $Cx+s=d$. Split the unrestricted vector as $x=u-v$ with $u,v\ge 0$. Applying Farkas' lemma to the column matrix $[C-C{I}_m]$ gives $C^{T}y\ge 0$, $-C^{T}y\ge 0$, $y\ge 0$ and $d^{T}y<0$. The first two conditions together are exactly $C^{T}y=0$. This reduction explains both the equality and the nonnegative row multipliers.

For a transferable utility game, the characteristic function of a coalitional game assigns a coalition $S$ its largest total attainable revenue $v(S)$, with $v(\varnothing )=0$. The core of a cooperative game consists of payoff vectors $x$ satisfying efficiency, $x(N)=v(N)$, and coalition stability, $x(S)\ge v(S)$ for every $S$. A coalition receiving less could operate alone and distribute its extra value to make each member better off.

Use thousands of pounds as the monetary unit. The physical directed arcs are $A\to B$ and $C\to D$, owned by $i$, with capacities $3,2$; $A\to C$ and $B\to D$, owned by $j$, with capacities $1,1$; and $B\to C$, owned by $k$, with capacity $2$.

The physical network is acyclic. There are exactly three $A$–$D$ graph paths and one $B$–$C$ graph path. Let $u,v,w$ be the $A$–$D$ flows on $ABD$, $ACD$, $ABCD$, respectively, and let $z$ be the direct $B$–$C$ demand. Their capacities and revenue areEvery feasible traffic pattern decomposes into these graph paths, so these inequalities are exact. The first is redundant, since $u\le 1$ and $w\le 2$ imply it.

Formulate this as a minimum-cost flow through the two-resource path packing as minimum-cost circulation reduction. Use auxiliary vertices $s,L,R,t$ and the following arcs, whose entries are (capacity, cost):The first forward graph path carries $u$, $sLt$ carries $v$, $sLRt$ carries $w$, and $sRt$ carries $z$. Conservation at $L$ imposes $v+w\le 2$, and at $R$ imposes $w+z\le 2$; the individual finite-capacity arcs give the other bounds. The return arc closes the circulation. Its cost is exactly $-R$, so this is an ordinary minimum-cost circulation with precisely the required feasible traffic set. Unlimited capacities may all be replaced by $5$, the maximum possible total graph path flow.

An linear programming optimality certificate is particularly short:The feasible choice $u=v=w=z=1$ attains equality. Thus the actual traffic is three units from $A$ to $D$ and one from $B$ to $C$, andAll four positive terms in the bound must be tight at any optimum, so these graph path amounts are unique.

The two traffic demands must retain their identities. Merely adding fictitious return arcs $D\to A$ and $C\to B$ to the physical graph can create an invalid graph cycle combining both rewards: $A\to C\to B\to D\to A$ would credit the $j$-only network with revenue even though it carries neither requested demand. The resource-flow formulation above avoids that problem.

For the characteristic function, only complete physical graph paths owned by a coalition are available. Company $i$ or $j$ alone has no requested graph path; company $k$ carries two units of $B$–$C$ traffic. The pair $\{i,j\}$ carries one unit on each of $ABD,ACD$; the pair $\{i,k\}$ sends two units on $ABCD$ rather than selling them at the lower $B$–$C$ rate; and $\{j,k\}$ has only the two direct $B$–$C$ units. ThereforeWriting payments in thousands, all stable divisions of the revenue are exactlyEquivalently, $8\le x_k\le 10$, $0\le x_j\le 10$ and $x_i=22-x_j-x_k$. This is the entire core, not just one acceptable allocation.

The nucleolus minimizes in lexicographic order the sorted decreasing excesses of a coalition $e(S,x)=v(S)-x(S)$ over imputations. Empty and grand-coalition coalition excesses are fixed zeros and can be omitted. For the six other coalitions, efficiency givesThe two $k$-related coalition excesses sum to $-2$, so their maximum is at least $-1$. This bound is attainable, and attaining it forces $x_k=9$. All six coalition excesses are then at most $-1$ precisely when $1\le x_j\le 9$ and $x_i=13-x_j$. The fixed pair of coalition excesses equals $-1$ throughout these first-stage minimizers.

Minimize the largest of the remaining coalition excesses. They become $x_j-13,-x_j,x_j-10,-1-x_j$, whose maximum is $\max (-x_j,x_j-10)$. Its unique minimum is $-5$ at $x_j=5$. Hence $x_i=8$ and $x_k=9$. The sorted proper coalition excesses there are $(-1,-1,-5,-5,-6,-8)$, and

Use two-phase simplex to handle the constraint of the opposite inequality direction. Introduce nonnegative slack variables $s_1,s_2$, a surplus variable $s_3$, and an artificial variable $a$. The equality constraints areFor Phase I maximize $w=-a$, initially with basis $(s_1,s_2,a)$. Its initial simplex dictionary isChoose $x_1$ to enter. The simplex ratio test compares $30$, $35/2$ and $40$, so $s_2$ leaves. The new dictionary isSince $w=-45/2+(5/2)x_2-x_3-s_2/2-s_3$, choose $x_2$ to enter. Its limiting ratios are $25/3$ from $s_1$ and $9$ from $a$, so $s_1$ leaves. This givesNow $w=-5/3-(8/3)x_3+s_2/3-(5/3)s_1-s_3$, so let $s_2$ enter. Its limiting ratios are $65$ from $x_1$ and $5$ from $a$; the artificial variable leaves. The simplex dictionary becomesSetting all nonbasic variables to zero gives $a=0$, a feasible original basis. Since $-a\le 0$, Phase I is optimal with value zero; delete $a$.

For Phase II the original objective in this basis isAll nonbasic reduced costs are strictly negative, so no further improving simplex pivot exists. As the nonbasic variables are nonnegative, the dictionary also directly certifies $z\le 700$, with equality only when $x_3=s_1=s_3=0$. ThereforeThe second original constraint has slack five and the other two are tight. As an independent linear programming optimality certificate, multiply the first constraint by $130$ and the third, after reversing it, by $80$. This gives $50x_1-30x_2+210x_3\le 700$, and subtracting $209x_3\ge 0$ proves the same upper bound for the objective.

Write the amended primal as $\min c^{\mathsf{T}}x$ with $Ax\le b$, $x\ge 0$. A convenient linear programming duality convention uses $y\le 0$ and gives $\max b^{\mathsf{T}}y$ subject to $A^{\mathsf{T}}y\le c$. Explicitly the dual isThe optimal dual vector is the negative of the three payoff-row slack coefficients:Indeed substitution gives $A^{\mathsf{T}}{y}^{\ast }=(2,-3,-5{)}^{\mathsf{T}}=c$, so all dual inequalities hold. To certify optimality directly by weak duality, for any feasible primal and dual vectors,where the second inequality uses $Ax\le b$ and $y\le 0$. Our feasible primal and dual vectors have equal values $-349/40$, so neither can be improved. This is a linear programming optimality certificate.

Introduce nonnegative slack variables $s_i$ and write $z=c^{\mathsf{T}}x$. A maximizing simplex dictionary is dual feasible when every nonbasic coefficient in the objective is nonpositive. After inserting a constraint, the dual simplex algorithm retains this property while repairing any negative basic value. For a leaving row $x_B=\beta +{\sum }_j{d}_j{x}_j$ with $\beta <0$, only $d_j>0$ can enter; choose a column minimizing the ratio of its objective penalty to $d_j$.

For the first linear program, $x_1$ has the best profit-to-resource ratio. Pivot it into the initial slack basis to obtainAll basic values are nonnegative and all reduced costs are nonpositive, so the optimal point is $(5,0,0,0)$, with value five. Adding the second constraint givesThe same basis remains feasible and optimal: the second constraint does not change the answer.

The third constraint gives the new rowThe current dictionary is dual feasible but primal infeasible. The eligible entering variables are $x_3,x_4$, with dual ratio-test values $2$ and $3$ respectively. Enter $x_3$ and leave $s_3$; solving that row and substituting into the old rows yieldsThis is a feasible optimal simplex dictionary. Thus the new optimal point is $(2,0,1,0)$, with value three. As an independent linear programming optimality certificate, dual multipliers $(3,0,2)$ have weighted objective bound $3\cdot 5+2(-6)=3$ and weighted coefficient row $(1,4,1,2)$, which dominates the profit row.

On inserting the fourth constraint the slack isIt has a negative constant and no eligible entering column. Since all its nonbasic variables are nonnegative, this row cannot be satisfied: the fourth linear program is infeasible, and adding the fifth constraint cannot restore feasibility. The requested optimal values are therefore

The arbitrary-data selection question is a maximum feasible subsystem problem. With rational input it is in NP: guess the selected row indices, and test their linear programming feasibility in polynomial time. Equivalently, a nonempty rational polyhedron has a feasible rational point of polynomially bounded encoding length, which serves as a certificate.

For an explicit NP-hardness reduction, take an independent set instance with graph $H$ having $r$ vertices and desired independent-set size $K$. Use variables $x_v\ge 0$, one inequality $-x_v\le -1$ for each vertex, and $M=r+1$ identical copies of $x_u+x_v\le 1$ for each edge. Ask for a feasible subsystem of size $M|E(H)|+K$. An independent set of size $K$ gives such a subsystem: include all edge rows and those $K$ vertex rows, and use its indicator vector. Conversely, omitting every copy of even one edge row leaves at most $M(|E(H)|-1)+r<M|E(H)|+K$ selectable rows. Hence any qualifying subsystem retains every edge inequality and at least $K$ vertex inequalities. Their vertices must be independent, since two adjacent selected vertices would force $x_u+x_v\ge 2$. The construction has polynomial size; $c$ is irrelevant to feasibility. Thus the rational-input decision problem is NP-complete, not merely difficult because there are many subsets to enumerate.

Introduce nonnegative slack variables $r_1,\dots ,r_4$ for the four dual inequalities. The initial simplex dictionary isAt the origin all four basic slacks are positive. Enter ${\lambda }_2$: the simplex ratio test compares bounds $2$ from $r_2$ and $3$ from $r_3$, so $r_2$ leaves at ${\lambda }_2=2$. Entering ${\lambda }_1$ initially would tie two limiting bounds and produce degeneracy in linear programming; the chosen pivot avoids this. The new simplex dictionary isOnly ${\lambda }_3$ has positive objective coefficient. Enter it; the limiting bound is $1/3$ from $r_3$, rather than $7$ from $r_4$. Thus $r_3$ leaves, givingEvery nonbasic variable has nonpositive objective coefficient, so this feasible simplex basis is optimal. Setting the nonbasic variables to zero yieldsBoth new basic solutions have strictly positive basic coordinates; neither pivot is degenerate.

The first and fourth dual constraints have positive slacks $8/3$ and $20/3$. Complementary slackness therefore requires $x_1=x_4=0$. Since ${\lambda }_2,{\lambda }_3>0$, the second and third primal constraints must be equalities:ConsequentlyThe first primal left side is $10/3\ge 3$, so the vector is feasible. Its value matches the feasible dual value, giving a linear programming optimality certificate.

The feasible triangle has verticesThese come from the three pairs of active boundary lines and satisfy the remaining inequalities. Its denominator $3x_1+x_2+2$ is positive at each vertex, with minimum $12/5$, so is positive throughout the triangle because it is an affine function.

For a direct linear programming optimality certificate, add twice the second inequality to the third to get $-x_1-3x_2\le 2$. Thus $x_1+3x_2+2\ge 0$, equivalently $2(x_1-x_2)\le 3x_1+x_2+2$. Division by the positive denominator gives an objective at most $1/2$. Both inequalities used in the bound are equalities at $v_3$, where the first inequality is also satisfied. ThereforeEquality requires the two bounding inequalities to be tight, so this optimizer is unique.

For every primal feasible solution $\mathbf{x}$, weak duality givesThus no primal feasible solution improves on ${\mathbf{x}}^{\ast }$. Similarly, for every dual feasible solution $\mathbf{y}$,Therefore both candidates are optimal, with the same objective function value. Equality is a linear programming optimality certificate and does not require a separate existence argument.