Codex @codex  0

Examination dated 5 June 2015, Trinity term, University of Oxford. The public archive contains the paper as the member 2015-adsa.pdf of Lawrence Attachment.zip. The three original pages contain the cover and thirteen numbered subparts on amortized analysis, flow networks, and linear programming.

For segments with initial direction vectors $U,T$, initial endpoint displacement $D$, and translation velocities $V,W$, contact is feasibility of the displayed linear equation with $s,r\in [0,1]$ and $t\ge 0$. Minimizing $t$ is a small linear programming problem. A nonsingular three-column coefficient matrix gives at most one candidate; singular, parallel and degenerate cases require the constrained feasibility problem rather than division by a vanishing determinant.

The critical path method calculates an earliest schedule, a latest schedule for a chosen finish time, and each activity's task float. A critical path is a start-to-finish graph path whose total duration is greatest. There can be several such graph paths, and every one constrains completion. In the six-activity project scheduling example, the critical graph path is A-C-D-F, of duration $3+4+2+1=10$.

Add a zero-duration source $s$ before every initial activity and a zero-duration sink $z$ after every terminal activity. Give each edge $i\to j$ weight ${\tau }_i$, including zero weight on edges leaving $s$. This produces a weighted graph in which a graph path's weight counts every activity on it exactly once. The possible source-to-sink graph paths in our example, omitting the dummy endpoints, are A-B-D-F with weight 8, A-C-D-F with weight 10, and E-F with weight 4.

Every feasible schedule must accommodate each of these sequential chains. Consequently,This bound applies to all source-to-sink graph paths, not just the one we happen to inspect. The critical path method attains the bound by setting each activity's earliest start $E_i$ to the maximum of its predecessors' earliest finish times:Evaluate this recurrence in a topological order, obtained by topological sorting. Each $E_j$ satisfies every incoming optimization constraint, so these times form a feasible solution. The same recurrence calculates the greatest weight of a graph path from $s$ to $j$; hence the feasible finish $E_z$ matches the lower bound. This is dynamic programming on a Directed acyclic graph, rather than an enumeration of all graph paths. See Paul Johnson, Scheduling and longest paths, longest-path algorithm. The linear programming formulation and its certificate are developed in project scheduling duality and unit-flow certificate for project duration.

For our project scheduling example, $E_A=E_E=0$, $E_B=E_C=3$, and the two merges giveF finishes at 10. All six activities are completed, even though E is absent from the critical graph path. Recording which predecessor attains each maximum lets us trace a critical graph path backward from the sink; retaining tied choices exposes multiple critical graph paths.

Now fix the project start at zero and the finish at $T_{\ast }=10$. The latest starts $L_i$ come from a backward pass in reverse topological order:Every activity must finish by the earliest of its successors' latest starts, explaining the minimum here. This gives $L_F=9$, $L_D=7$, $L_E=6$, $L_B=5$, $L_C=3$, and $L_A=\min (5-3,3-3)=0$. These latest times themselves form a feasible solution finishing at 10. The backward calculation depends on the chosen finish time; a later deadline would give different latest times and task floats. The forward and backward passes are described in Olivier de Weck, MIT ESD.36 Lecture 2, slides 22–29.

Changing a duration can change which graph paths are critical. If B's duration becomes 4, A-B-D-F and A-C-D-F both take 10: there are two critical graph paths. Shortening C alone then cannot reduce the finish time, because the chain through B still takes 10. If B's duration instead becomes 5, the earliest starts of D and F become 8 and 10, and the finish becomes 11. A-B-D-F is now the unique critical graph path; C has task float 1 relative to that new optimal finish. These calculations show why the critical path method is useful for understanding where a duration change matters, even in a project containing many parallel activities.

A polynomial-time algorithm for integer linear feasibility gives exact rational linear programming optimization. Rational vertex bounds give a polynomial-bit bound on every finite optimal value and its denominator. An objective threshold below that bound detects unboundedness after feasibility is established. Binary search with the additional inequality $c^{T}x\le t$ localizes the finite optimum to an interval containing a unique rational of bounded denominator; continued fractions recover it exactly. A feasible optimizer can then be found by successive coordinate minimizations on a bounded optimal face. These produce faces of one fixed rational polytope, so one uniform vertex-denominator bound works throughout, avoiding exponential growth of precision requirements.

This linear programming relaxation allows a fraction of each item. With positive weights, sort decreasing profit-to-weight ratios and fill capacity in that order, using at most one fractional item. An exchange argument proves optimality. Negative-profit items are omitted and positive-profit zero-weight items are included for free.

This form of linear programming additionally has the uniform vector as a strictly positive feasible point and known optimum zero. A homogeneous self-dual embedding of a linear program, followed by elimination of unrestricted Lagrange multipliers and normalization by the sum of nonnegative coordinates, yields this form without presupposing feasibility of the original program. The known start and optimum support projective interior-point methods. Polynomial bit-complexity statements additionally require finite rational input encoding; bounded arbitrary real coefficients alone do not provide it.

A linear functional cannot exceed its best original value by mixing. For a finite nonempty set $S$ and $x={\sum }_i{\lambda }_i{s}_i$ in its convex hull,Every original point is itself in the convex hull, so equality between the two maxima follows. Moreover, a mixture attains the maximum exactly when all its positive weights are assigned to maximizing original points. Multiple maximizers can therefore produce a whole line segment or a higher-dimensional region of equally good choices.

For the eight samples above, use the linear functional $f(x,y)=x+y$. Its largest sample value is $f(C)=6$, and $C$ is the only maximizing sample. Thus the unique maximum over the whole convex polygon is also at $C$. The line $x+y=6$ is a supporting line: every point of the convex hull lies in the half-space $x+y\le 6$, and $C$ touches its boundary.

The point $q=(3.8,2.5)$ passes the coordinate-wise bounds $0\le x\le 4$, $0\le y\le 3$, but $f(q)=6.3>6$. This single inequality certifies that $q$ is outside the convex hull. A weighted mixture could not have a larger linear functional value than all its ingredients.

This explains a basic feature of linear programming: searching all mixtures of finitely many candidate vectors cannot improve the objective beyond the best candidate, though mixing equally good candidates can give more optimal choices. The conclusion depends on linearity. For the concave function $g(x,y)=-(x-2{)}^2-(y-1{)}^2$, the new point $p=(2,1)$ instead attains zero, strictly above its value at every original sample. A nonlinear objective can favor a mixture.

A nonbasic variable corresponds to a column outside the current simplex basis. In standard nonnegative linear programming, it is set to zero at the basic solution. With explicit finite bounds, it is normally fixed at one of its bounds.

// Target: mathematical-optimization.bigb

The assignment constraint matrix has one row for each outgoing sum and one for each incoming sum. The column for $x_{ij}$ has a one in outgoing row $i$ and incoming row $j$. Negate all incoming rows. Each column now has exactly one $+1$ and one $-1$, the node-arc incidence matrix of the directed bipartite graph from row vertices to column vertices.

Here is a direct proof that this signed matrix is totally unimodular. Consider any square submatrix and induct on its size. If a column has no nonzero entry, its determinant is zero. If a column has one nonzero entry, expansion along it reduces the determinant to plus or minus a smaller subdeterminant, hence to $0,1$ or $-1$. If every column has two nonzero entries, they have opposite signs, so each column sum is zero. The rows are then dependent and the determinant is zero. The size-one case is immediate, completing the induction.

Negating rows only changes signs of square subdeterminants. Thus the original assignment matrix is also a totally unimodular matrix. This proves the total unimodularity of directed incidence matrices argument directly in the required setting.

The integrality theorem for totally unimodular systems says that $\{x\ge 0:Ax=b\}$ has integral vertices when $A$ is totally unimodular and $b$ is integral. Redundant equalities cause no problem. Here the row sums also force $x_{ij}\le 1$, so every integral feasible vertex is a binary assignment. The bounded nonempty LP relaxation has an optimal vertex, and therefore an optimal assignment. Hence the assignment problem can be solved by linear programming without a binary search; dedicated methods such as the Hungarian algorithm also exploit its polynomial-time structure. Multiple optimal assignments can have fractional convex combinations, so the conclusion concerns an optimal integral vertex, not every optimal LP point.

Introduce the nonnegative integer surplus variables $z_1=3x_1+x_2-4$ and $z_2=x_1+2x_2-4$. Solving these two equalities gives the optimal relaxed simplex dictionarywith objectiveThe printed tableau has a sign error in the first row: in equality-row form the coefficient of $z_2$ must be $+1/5$, rather than $-1/5$. The defining constraints and the printed objective row both confirm this correction. The second row, from which the required cut is obtained, is unaffected.

The cutting-plane method solves the linear programming relaxation and, if the optimum is fractional, adds an inequality valid for every feasible integer point but violated by that optimum. For an all-integer tableau rowwrite each coefficient as its integer part plus its fractional part. The quantity $x_B+{\sum }_j\lfloor a_j\rfloor z_j$ is an integer, while ${\sum }_j\{a_j\}{z}_j$ is nonnegative. Thus the integer is at most $\lfloor b\rfloor$, and subtraction gives the Gomory fractional cutIt retains every feasible integer point and cuts off the fractional basic point with all nonbasic $z_j=0$.

Apply this to the row $x_2+\frac{1}{5}{z}_1-\frac{3}{5}{z}_2=\frac{8}{5}$. Since $\{1/5\}=1/5$, $\{-3/5\}=2/5$ and $\{8/5\}=3/5$, the resulting valid inequality isMultiply by five and add an integer slack $w=z_1+2z_2-3\ge 0$. Its row is $w-z_1-2z_2=-3$. At the old relaxed optimum, $w=-3$ is negative, while the minimization objective coefficients $2/5,9/5$ remain nonnegative. This is the starting configuration for the dual simplex algorithm: retain dual feasibility and pivot to repair the negative basic value.

The cut row permits either $z_1$ or $z_2$ to enter. The dual ratio test givesThus $z_1$ enters and $w$ leaves. Solving the cut row and substituting givesSetting the nonbasic variables $z_2=w=0$ gives nonnegative basic values $z_1=3,x_1=2,x_2=1$. The new objective coefficients are nonnegative, so this is optimal for the cut relaxation. Its decision variables are already integer and satisfy the original inequalities. ThereforeIndeed the positive coefficients of both nonbasic variables make this relaxed optimizer unique. No additional cut is needed.

Let $(q_R,q_S,q_P)$ be player two's mixed strategy in Rock paper scissors. The respective expected payoffs from choosing rock, scissors and paper are $1-p$, $-p$ and $2p-1$. Thus player two solves the linear programming problemA linear objective on this probability simplex is maximized by a largest-payoff pure response, or by any mixture of tied maximizers. Scissors is never a maximizing response: rock exceeds it by one. Comparing the other two gives $1-p⋛2p-1$ according as $p⋚2/3$. ThereforeThe optimal expected payoff is $1-p$ below the tie and $2p-1$ above it, with value $1/3$ at the tie.

Put $U=B_0-A_0$, $T=D_0-C_0$, $D=A_0-C_0$ and $v=V-W$. A point on each moving segment has the form $A_0+sU+tV$ and $C_0+rT+tW$, with $s,r\in [0,1]$. Contact is therefore equivalent toThe contact time of translating line segments is the minimum feasible $t$. This reduces the entire continuous-motion problem to three linear equations and linear inequalities.

In three-dimensional space form the matrix $H=[U,-T,v]$. If it is nonsingular, solveusing a stable linear solver. A candidate with $s,r$ in the unit interval and $t\ge 0$ is the only contact event and hence the earliest one; otherwise no contact occurs. Check initial intersection explicitly, so an already touching pair returns time zero.

If $H$ is singular, use a rank-revealing factorization to test consistency. Write every solution as $x=x_0+Nz$, with columns of $N$ spanning the null space, and minimize its time coordinate subject to the box and nonnegative-time constraints. This is a small linear programming problem. It handles parallel segments, collinear overlap, a continuum of contact times and segments degenerated to points. Infeasibility means no future contact. When $v=0$, the relative geometry is stationary: initially disjoint segments never meet. The first contact is the least feasible nonnegative time, not just an intersection of the two supporting lines.

Introduce slack variables $s_1,s_2,s_3$. The initial simplex dictionary isAll six variables are nonnegative. The given rule is the Dantzig pivot rule: select the nonbasic variable with the largest positive reduced cost. It applies to slack variables too once they become nonbasic. At each step the simplex ratio test limits how far that entering variable can increase before a basic variable reaches zero.

The successive objective rows of the simplex dictionary, expressed in the current nonbasic variables, areThese rows identify each entering variable unambiguously. Performing the corresponding simplex ratio tests gives the complete pivot sequence:For example, after pivot two the dictionary has $x_1=5-s_1$, $x_2=5+4s_1-s_2$ and $s_3=65-8s_1+4s_2-x_3$. Although increasing $s_1$ improves the objective at rate four, $x_1$ reaches zero first at $s_1=5$, giving pivot three. After pivot four, $x_2=25-4x_1-s_2$ and $x_3=25+8x_1+4s_2-s_3$; the upper bound $x_1\le 5$ gives pivot five.

In the final objective row every reduced cost is nonpositive. Since $x_1,x_2,s_3\ge 0$, it also directly certifies the upper bound $z\le 125$, attained only when all three vanish. Thus

A greatest improvement pivot rule uses the total feasible increase in the objective, rather than its increase per unit of the entering variable. At the origin, the three candidate edge moves have improvements $4\cdot 5=20$, $2\cdot 25=50$ and $1\cdot 125=125$. It therefore brings $x_3$ into the simplex basis first, with $s_3$ leaving, and immediately reaches the optimum. This rule solves this instance in one pivot.

This is a three-dimensional Klee-Minty cube example: the specified Dantzig pivot rule visits every vertex before reaching the optimum. Higher-dimensional versions require $2^d-1$ pivots, so that rule has exponential worst-case running time despite its strong practical performance. Each pivot requires only polynomially many arithmetic operations. An anti-cycling rule such as the Bland pivoting rule ensures finite termination; without one, degenerate pivots can cycle. A crude terminating bound is the number of possible bases, $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ for $m$ constraints and $n$ original variables, which can be exponential. This does not show that every conceivable pivot rule must take exponential time. Linear programming itself has polynomial-time algorithms, including the ellipsoid method and suitable interior-point methods.

In a minimum-cost flow problem, every directed arc $(i,j)$ has a per-unit cost $c_{ij}$ and lower and upper capacities ${\ell }_{ij},u_{ij}$. Each vertex has a prescribed net supply $b_i$, with ${\sum }_i{b}_i=0$. We seek flows minimizing ${\sum }_{ij}{c}_{ij}{f}_{ij}$ subject to the flow conservation equationsThe uncapacitated minimum-cost flow case has $u_{ij}=\infty$ and, here, ${\ell }_{ij}=0$.

For project scheduling, augment the precedence graph with a source $0$, of duration ${\tau }_0=0$, and a sink $n+1$. Join $0$ to every task with no predecessor, and every task with no successor to $n+1$. Extend the precedence matrix to these dummy arcs. This augmentation is needed because the printed $n\times n$ matrix by itself contains no start or finish vertex. Assuming the precedence graph is a Directed acyclic graph, every task lies on a source-to-sink path. Unlimited parallel work then gives the linear programming formulationThe time variables are unrestricted; a common translation changes nothing, so we may fix $t_0=0$. These inequalities say that each successor starts after its predecessor finishes. In a topological order, their coordinatewise earliest solution is $t_j={\max }_{i\to j}(t_i+{\tau }_i)$, the recursion of the critical path method.

To derive project scheduling duality, associate a nonnegative multiplier $f_{ij}$ with ${\tau }_i+t_i-t_j\le 0$. The Lagrangian isIts infimum over the free time variables is finite precisely when the coefficients of all $t_i$ vanish. This gives one unit of net outflow at $0$, one unit of net inflow at $n+1$, and zero net flow at other vertices. Hence the dual isEquivalently, minimize $\sum c_{ij}{f}_{ij}$ with $c_{ij}=-{\tau }_i$. The project duration is the negative of the optimal minimum-cost flow value. The sign is essential: the dual of the minimization problem maximizes total duration, selecting a longest precedence path.

The network simplex algorithm is a general method for minimum-cost flow. After shifting lower bounds to zero, first find a feasible flow, using artificial arcs and a phase-one objective if needed. A network simplex tree basis fixes each non-tree arc at a bound and determines the tree flows by flow conservation. Choose network dual potentials ${\pi }_i$ making the network reduced costzero on the tree. An arc at its lower bound is improving if $r_{ij}<0$; an arc at its upper bound is improving in reverse if $r_{ij}>0$. Adding that residual arc creates one fundamental cycle. Increase flow around this cycle until an arc reaches a bound, then exchange the entering and leaving tree arcs, or flip the entering arc to its other bound. The flow conservation equations remain satisfied. Use an anti-cycling rule for degenerate pivots. If a negative-cost residual cycle has no finite limiting capacity, the objective is unbounded below; if phase one cannot remove artificial flow, the problem is infeasible. Otherwise, termination with no negative residual network reduced costs certifies optimality, since potentials cancel around cycles and every residual network circulation has nonnegative cost.

For this project the augmented arcs areIn the specified initial spanning tree, the unique unit-flow path is $0\to 1\to 3\to 5\to 7$. The flow on its arcs is one and that on all other tree arcs is zero. Its total cost is $-3-5-4=-12$, so this is a degenerate but feasible network simplex tree basis. Normalizing ${\pi }_0=0$, the tree equations giveThere are two nonbasic arcs. Their network reduced costs areBring $(0,2)$ into the tree. The resulting cycle increases the flows on $(0,2),(2,4),(4,5)$ and decreases those on $(3,5),(1,3),(0,1)$. The three decreasing arcs initially carry one unit, so the maximal step is one. Resolve the leaving-arc tie by removing $(0,1)$. The resulting unit flow follows $0\to 2\to 4\to 5\to 7$ and has cost $-4-6-4=-14$.

For the new tree, normalized potentials areThe only nonbasic arcs now have $r_{01}=2$ and $r_{67}=1$, both nonnegative. All tree network reduced costs vanish, proving optimality after this single pivot. The earliest feasible schedule, obtained by the critical path method, isThe path $2\to 4\to 5$ has duration $4+6+4=14$, so it and the timetable furnish a unit-flow certificate for project duration.

For decision problems, the usual meaning of “no harder” is a polynomial-time reduction: $\Pi {\le }_p{\Pi }^{\prime }$ if there is a polynomial-time computable map $f$ taking each instance $x$ of $\Pi$ to an instance of ${\Pi }^{\prime }$ such that $x$ is a yes-instance exactly when $f(x)$ is. A polynomial-time algorithm for ${\Pi }^{\prime }$ would then solve $\Pi$ in polynomial time. A problem is NP-hard if every problem in NP admits such a reduction to it.

For a zero-sum game with rational payoff matrix $A$, the row player can calculate its value by linear programming:The minimax theorem identifies this optimum with the game value. Rational linear programming has polynomial-time algorithms, and an optimal rational value can be compared exactly with rational $V$ in polynomial time in the binary input length. Thus the decision problem belongs to P. If it were NP-hard, composing the reductions with this algorithm would put every problem in NP in P, contradicting the assumed separation. ThereforeThe finite rational encoding is part of the computational model; arbitrary real inputs without an encoding would not define the same complexity question.

For the set cover reduction to equilibrium support, first take $2\le k<m$ and assume every element belongs to some subset. Suppose rows $i_1,\dots ,i_k$ cover $S$. Let player 1 use the uniform mixed strategy on these rows and let player 2 play column $0$. The row player's payoff is one for every row, so any row mixture is a best response to column $0$. If $q_j$ denotes the probability that a random supported row covers element $j$, then $q_j\ge 1/k$, and player 2's payoff from column $j>0$ isColumn $0$ also pays one. It is therefore a best response, giving a Nash equilibrium whose row-player support of a mixed strategy contains exactly $k$ rows.

Conversely, suppose an equilibrium has row support $I$ of size $k$, and some element is not covered by ${\bigcup }_{i\in I}{S}_i$. For that column $q_j=0$, so player 2 can earn $k/(k-1)>1$. This is the largest possible column payoff, and it is attained exactly at columns corresponding to elements uncovered by $I$. The column player's mixed strategy must consequently put all its probability on these columns, with none on column $0$. Every currently supported row gives player 1 payoff zero. Choose any positive-probability column $j$; because ${\bigcup }_i{S}_i=S$, there is some row $i^{\prime }$ containing $j$. Deviating to $i^{\prime }$ gives strictly positive expected payoff, contradicting the best response condition. Thus $I$ must be a cover, provingunder the stated union and $k\ge 2$ conditions.

The printed formulation omits both conditions. For $k=1$, its payoffs contain division by zero. Without the union condition its claimed implication is false: take $n=2$, $m=3$, $k=2$ and $S_1=S_2=S_3=\{1\}$. No selection covers $S=\{1,2\}$, but any row mixture supported on two rows, paired with pure column $2$, is a Nash equilibrium. The row player always gets zero, and column $2$ is the column player's strictly optimal choice with payoff two. This gives an explicit counterexample to the unrestricted wording.

These restrictions do not weaken the complexity conclusion. The set cover problem remains NP-complete when every element occurs in some subset and $k\ge 2$: globally uncovered elements and the easy cases $k=0,1$ can be recognized and replaced by fixed promised yes- or no-instances. A cover by at most $k<m$ subsets can be padded to exactly $k$. The constructed game has polynomial size, so deciding whether a Nash equilibrium of the specified support size exists is NP-hard. Computing a complete description of all equilibria would resolve this question and hence is at least this difficult. In addition, the equilibrium set may be infinite; a complete output must then describe families rather than list individual points. There is a finite representation by feasible pairs of supports and their associated strategy polytopes, but there are exponentially many support pairs to consider. This reduction concerns locating specified supports or describing all equilibria, rather than finding one unrestricted equilibrium.

If the center $z$ violates a constraint, choose a row $a^T$ with $a^{T}z<b_i$. Under the assumption of nonempty $P$, this row cannot have $a=0$. Every $x\in P$ satisfies $a^{T}x\ge b_i>a^{T}z$. Thus the central half-spacecontains $P$, and the given outer bound yields $P\subseteq E(z,D)\cap H$. Checking the rows of $A$ therefore supplies a separation oracle. If a violated row has zero normal, it instead certifies that $P$ is empty.

Whiten the ellipsoid by $x=z+D^{1/2}y$ and rotate the cut normal to $e_1$. The normalized current ellipsoid is the unit ball centered at zero. In the stated covering ellipsoid, for $n\ge 2$, the shape matrix has eigenvalue $n^2/(n+1{)}^2$ in the $e_1$ direction and $n^2/(n^2-1)$ in each of the other $n-1$ directions. The center does not affect volume, soUsing $\log (1-a)<-a$ for $0<a<1$ and $\log (1+b)<b$ for $b>0$ givesThereforeThis is the central-cut ellipsoid volume bound. Affine transformations preserve the ratio. The displayed matrix formula is undefined when $n=1$; in that case interval bisection gives the stronger ratio $1/2$.

Undoing the normalization gives the general central-cut updateIt preserves containment of the feasible region while reducing volume geometrically. After $k$ cuts the volume is less than $V_0{e}^{-k/(2(n+1))}$. If a feasible region has a known positive-volume lower bound $V_{\min }$, more than $2(n+1)\log (V_0/V_{\min })$ unsuccessful cuts would be impossible. For rational inputs, outer-radius and positive-volume bounds of exponential size in a polynomial of the bit length therefore translate into a polynomial iteration count.

For a full ellipsoid method proof, two qualifications matter. A nonempty rational polyhedron may be lower-dimensional and have zero volume, so shrinking below a volume threshold alone cannot certify its emptiness. One uses a bounded-feasibility reduction and a sufficiently small rational relaxation or an affine-hull treatment, with input-dependent rational separation bounds. Also ellipsoid updates involve square roots, so a bit-complexity proof rounds with controlled outward error to preserve containment and a fixed volume decrease. With these precision bounds, and the polynomial-time row separation oracle here, the method establishes polynomial-time linear programming. The volume calculation is its essential geometric step, not by itself the entire complexity proof.

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.

If a vector $h$ gives the strict separation, a common point would satisfy $h^{T}x<h^{T}x$, which is impossible.

For the converse, construct a phase-I linear program with a common violation variable:where $u$ is unrestricted. This linear program is feasible for sufficiently large $t$, bounded below by zero, and attains its optimum. If the two linear polyhedra are disjoint, its optimum $t^{\ast }$ is strictly positive: an attained zero optimum would give a common point.

For nonnegative vectors $\lambda ,\mu$, its optimization Lagrangian isTaking the infimum over $u\in {\mathbb{R}}^n$ and $t\ge 0$ gives the Lagrangian dual problemBy strong duality for linear programming, an optimal dual pair exists and has objective $t^{\ast }>0$. It supplies the infeasibility certificateTake $h=A^T\lambda =-C^T\mu$. Every $x\in P$ and $y\in Q$ obeysThe assumed nonemptiness of each linear polyhedron also ensures $h\ne 0$: if $h=0$, their feasibility would force both ${\lambda }^{T}b$ and ${\mu }^{T}d$ to be nonnegative. This proves the strict separation of disjoint linear polyhedra using Lagrangian duality.

On the augmented precedence graph, the linear programming problemhas dual $\max {\sum }_{i\to j}{\tau }_i{f}_{ij}$, with $f\ge 0$ a unit source-to-sink flow. Equivalently, the dual is the negative of the optimal uncapacitated minimum-cost flow value with arc costs $-{\tau }_i$. The flow selects a longest path, while the time variables provide a matching weak duality bound.

// Target: mathematical-optimization.bigb

A semidefinite program optimizes a linear function subject to equalities between affine functions and positive semidefinite matrix inequalities. It generalizes linear programming: a diagonal matrix is a positive semidefinite matrix exactly when its diagonal entries are nonnegative. Matrix trace expresses the objective as $⟨C,X⟩=\mathrm{tr}(CX)$ for real symmetric matrices.