> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-vii-selected-topics/29.-linear-programming.md).

# 29. Linear Programming

## Exercises

### 29.1-1

There is only one free variable $$x\_1$$, since $$x\_2=7-x\_1$$. The three feasible solutions and the objective value $$f$$ of each one are as follows:

1. $$x\_1=6,x\_2=1,f=-9$$
2. $$x\_1=5,x\_2=2,f=-4$$
3. $$x\_1=4,x\_2=3,f=1$$

### 29.1-2

We see that $$x\_3=x\_1-7$$ and because $$x\_3 \le 0$$ we must have $$x\_1 \le 7$$. The three feasible solutions and the objective value $$f$$ of each one are as follows:

1. $$x\_1=7,x\_2=3,x\_3=0,f=35$$
2. $$x\_1=6,x\_2=6,x\_3=-1,f=53$$
3. $$x\_1=5,x\_2=9,x\_3=-2,f=71$$

### 29.1-3

$$
-2x\_1-2x\_2 \le -10 \implies x\_1+x\_2 \ge 5.
$$

The terms $$x\_1 + x\_2$$ cannot simultaneously be less than or equal to 2 and greater than or equal to 5, proving the system is impossible.

### 29.1-4

Let's fix $$x\_2=0$$, such that

$$
−2x\_1 + x\_2 \le −1 \implies x\_1 \ge 1/2 \\
-x\_1-2x\_2 \le -2 \implies x\_1+2x\_2 \ge 2 \implies x\_1 \ge 2.
$$

We can choose an arbitrarily large value for $$x\_1 \ge 2$$. Therefore, the objective function also grows to infinity as $$x\_1$$ does.

### 29.1-5

$$\text{minimize } x\_1+x\_2$$

subject to

$$x\_1 \ge 0, x\_2 \ge 0$$.

### 29.1-6 🌟

{% hint style="success" %}
Shows how to convert constraints from one form to another in a linear program.
{% endhint %}

#### a.

We incorporate the following two inequalities instead of $$\sum\_{j=1}^n a\_{ij}x\_j = b\_i$$:

* $$\sum\_{j=1}^n a\_{ij}x\_j \le b\_i$$
* $$\sum\_{j=1}^n a\_{ij}x\_j \ge b\_i$$

#### b.

We incorporate the next equality constraint and a nonnegativity constraint instead of $$\sum\_{j=1}^n a\_{ij}x\_j \le b\_i$$:

* $$\left(\sum\_{j=1}^n a\_{ij}x\_j \right) +s= b\_i$$
* $$s \ge 0$$ (a new slack variable)

### 29.1-7

We just need to flip the sign of the objective function, since $$\min f(x) = -\max (-f(x))$$, set the objective to maximize, and leave the constraints unchanged.

Because the constraints are left unchanged, the feasible region is identical. Since the optimal coordinates $$\bar x$$ do not change, the two linear programs are equivalent. To find the optimal value of the original minimization problem, you simply solve the new maximization problem and negate its final objective value.

### 29.1-8

Adding the next constraints ensures that you never seem to win more voters than there actually are:

$$
\begin{align\*}
-2x\_1 + 8x\_2 + 0x\_3 + 10x\_4 &\le 100 \\
5x\_1 + 2x\_2 + 0x\_3 + 0x\_4 &\le 200 \\
3x\_1 - 5x\_2 + 10x\_3 - 2x\_4 &\le 50.
\end{align\*}
$$

The objective function to minimize total cost is

$$
C(x) = x\_1 + x\_2 + x\_3 + x\_4.
$$

The total number of voters won across the entire district is the sum of the equations for the urban, suburban, and rural demographics:

$$
V(x) = 6x\_1 + 5x\_2 + 10x\_3 + 8x\_4 \le 10C(x).
$$

Because this is a minimization problem, the cost of the optimal solution, cannot exceed the cost of any feasible solution. The book already shows one that wins 232 thousands of voters by spending 33 thousand dollars on advertising. Hence, $$V(x) \le 330 < 350$$ in an optimal solution.

### 29.2-1

$$
\begin{align\*}
\text{maximize } \&d\_x \\
\text{subject to} \\
d\_t &\le d\_s+3 \\
d\_y &\le d\_s+5 \\
d\_x &\le d\_t+6 \\
d\_y &\le d\_t+2 \\
d\_t &\le d\_y+1 \\
d\_x &\le d\_y+4 \\
d\_z &\le d\_y+6 \\
d\_s &\le d\_z+3 \\
d\_x &\le d\_z+7 \\
d\_z &\le d\_x+2 \\
d\_s &= 0.
\end{align\*}
$$

### 29.2-2 🌟

{% hint style="success" %}
Provides a generalization of a linear program for the single-source shortest-paths problem.
{% endhint %}

The constraints (29.23) and (29.24) should remain the same. We just need to alter the objective function:

$$
\text{maximize } \sum\_{v \in V-{s}} d\_v
$$

### 29.2-3

Uses the optimized format from the next exercise.

$$
\begin{align\*}
\text{maximize } \&f\_{sv\_1} + f\_{sv\_2} \\
\text{subject to} \\
f\_{sv\_1} &\le 16 \\
f\_{sv\_2} &\le 13 \\
f\_{v\_1v\_3} &\le 12 \\
f\_{v\_2v\_1} &\le 4 \\
f\_{v\_2v\_4} &\le 14 \\
f\_{v\_3v\_2} &\le 9 \\
f\_{v\_3t} &\le 20 \\\
f\_{v\_4v\_3} &\le 7 \\\
f\_{v\_4t} &\le 4 \\
f\_{sv\_1} + f\_{v\_2v\_1} &= f\_{v\_1v\_3} \\
f\_{sv\_2} + f\_{v\_3v\_2} &= f\_{v\_2v\_1} + f\_{v\_2v\_4} \\\
f\_{v\_1v\_3} + f\_{v\_4v\_3} &= f\_{v\_3v\_2} + f\_{v\_3t} \\\
f\_{v\_2v\_4} &= f\_{v\_4v\_3} + f\_{v\_4t} \\
f\_{uv} &\ge 0 \text{ for all edges $(u, v)$ in the graph}.
\end{align\*}
$$

### 29.2-4 🌟

{% hint style="success" %}
Rewrites the linear program for maximum flow so that it uses only $$O(V + E)$$ constraints.
{% endhint %}

$$
\begin{align\*}
\text{maximize } &\sum\_{(s, v) \in E} f\_{sv} - \sum\_{(v, s) \in E} f\_{vs} \\
\text{subject to} \\
f\_{uv} &\le c(u, v) \quad \quad \text{ for each } (u, v) \in E \\
\sum\_{(v, u) \in E} f\_{vu} &= \sum\_{(u, v) \in E} f\_{uv} \quad \text{for each } u \in V - {s, t} \\
f\_{uv} &\ge 0 \quad \quad \quad \quad ,, \text{ for each } (u, v) \in E.
\end{align\*}
$$

### 29.2-5

One way is to first cast the maximum-bipartite-matching problem into a maximum flow problem (see Section 24.3 in the book). Afterward use the model from the previous exercise to craft an LP.

{% hint style="info" %}
The standard LP formulation does not strictly forbid fractional matchings. While the integrality theorem guarantees that pure integer optimal solutions exist at the "corners" (vertices) of the mathematical model, an LP solver might land on a fractional solution if it stops on a flat edge between corners. We could strictly avoid this by turning it into an Integer Linear Program (ILP), but ILP solvers are generally NP-hard. Fortunately, if you solve the relaxed LP using the Simplex method, it inherently searches corner-to-corner and will naturally produce an integer solution.
{% endhint %}

### 29.2-6

In this path-based formulation, flow conservation at each intermediate vertex is automatically satisfied because every decision variable $$x\_i$$ represents an unbroken end-to-end flow from the source $$s$$ to the sink $$t$$ along a valid path $$P\_i$$. Therefore, we only need to enforce the edge capacity constraints.

$$
\begin{align\*}
\text{maximize } &\sum\_{i=1}^{p} x\_i \\
\text{subject to} \\
\sum\_{{i \mid (u, v) \in P\_i}} x\_i &\le c(u, v) \quad \text{for each } (u, v) \in E \\
x\_i &\ge 0 \quad \text{for } i = 1, 2, \dots, p.
\end{align\*}
$$

The number of directed simple paths $$p$$ from $$s$$ to $$t$$ is bounded by the maximum possible number of paths in a complete directed graph. A simple path from $$s$$ to $$t$$ can contain anywhere from 0 to $$\vert{}V\vert{}-2$$ intermediate vertices. To construct a path with exactly $$k$$ intermediate vertices, you must choose $$k$$ vertices from the $$\vert{}V\vert{}-2$$ vertices and arrange them in a specific sequence. The number of ways to do this is a $$k$$-permutation

$$
P(\vert{}V\vert{}-2, k) = \frac{(\vert{}V\vert{}-2)!}{(\vert{}V\vert{}-2-k)!}.
$$

To find the absolute upper bound, we sum the permutations for all possible path lengths

$$
p \le \sum\_{k=0}^{\vert{}V\vert{}-2} \frac{(\vert{}V\vert{}-2)!}{(\vert{}V\vert{}-2-k)!} \approx e \cdot (\vert{}V\vert{}-2)!=O(\vert{}V\vert{}!).
$$

{% hint style="info" %}
The sum of fractions is the Taylor expansion of $$e$$.
{% endhint %}

### 29.2-7 🌟

{% hint style="success" %}
Expresses the minimum-cost multicommodity-flow problem as a LP.
{% endhint %}

We should set the objective function to be

$$
\text{minimize }∑*{(u,v)∈E} a(u, v) · f*{uv}.
$$

{% hint style="warning" %}
The aggregate flow $$f\_{uv}$$ is not a separate decision variable, but rather the sum of individual commodity flows on that edge $$f\_{uv} = \sum\_{i=1}^k f\_{iuv}$$. The objective function above compactly expresses this quantity.
{% endhint %}

All the other details remain the same as in the original multicommodity-flow problem.

### 29.3-1

$$
\begin{array}{lrrrrrl} \text{maximize} & 50y\_1 & + & 100y\_2 & + & 25y\_3 & \ \text{subject to} & -2y\_1 & + & 5y\_2 & + & 3y\_3 & \le 1 \ & 8y\_1 & + & 2y\_2 & - & 5y\_3 & \le 1 \ & & & & & 10y\_3 & \le 1 \ & 10y\_1 & & & - & 2y\_3 & \le 1 \ & y\_1, & y\_2, & y\_3 & \ge & 0 & \end{array}
$$

### 29.3-2 🌟

{% hint style="success" %}
Explains how to directly take the dual of an arbitrary linear program.
{% endhint %}

Use a **primal–dual correspondence table**. Introduce one dual variable for each primal constraint and one dual constraint for each primal variable. The objective function flips: a minimization primal gives a maximization dual, and vice versa.

#### If the primal is a minimization

Write the primal as

$$
\min c^T x
$$

with constraints and variable signs as below. Then the dual is

$$
\max b^T y
$$

with the following rules:

| Primal (min)                   | Dual (max)                       |
| ------------------------------ | -------------------------------- |
| constraint $$a\_i x \ge b\_i$$ | $$y\_i \ge 0$$                   |
| constraint $$a\_i x \le b\_i$$ | $$y\_i \le 0$$                   |
| constraint $$a\_i x = b\_i$$   | $$y\_i$$ free                    |
| variable $$x\_j \ge 0$$        | $$\sum\_i a\_{ij}y\_i \le c\_j$$ |
| variable $$x\_j \le 0$$        | $$\sum\_i a\_{ij}y\_i \ge c\_j$$ |
| variable $$x\_j$$ free         | $$\sum\_i a\_{ij}y\_i = c\_j$$   |

Here $$a\_{ij}$$ is the coefficient of $$x\_j$$ in the $$i$$-th primal constraint.

#### If the primal is a maximization

Use the symmetric table:

$$
\max c^T x \quad\longrightarrow\quad \min b^T y
$$

| Primal (max)                   | Dual (min)                       |
| ------------------------------ | -------------------------------- |
| constraint $$a\_i x \le b\_i$$ | $$y\_i \ge 0$$                   |
| constraint $$a\_i x \ge b\_i$$ | $$y\_i \le 0$$                   |
| constraint $$a\_i x = b\_i$$   | $$y\_i$$ free                    |
| variable $$x\_j \ge 0$$        | $$\sum\_i a\_{ij}y\_i \ge c\_j$$ |
| variable $$x\_j \le 0$$        | $$\sum\_i a\_{ij}y\_i \le c\_j$$ |
| variable $$x\_j$$ free         | $$\sum\_i a\_{ij}y\_i = c\_j$$   |

#### How to remember it

* Each primal constraint becomes a dual variable.\
  Inequality constraints give signed dual variables; equality constraints give free dual variables.
* Each primal variable becomes a dual constraint.\
  Nonnegative/nonpositive/free variables determine the direction of the dual inequality.
* Objective coefficients and right-hand sides swap roles.
* The optimization direction reverses: minimize ↔ maximize.

If a primal variable has a bound like $$x\_j \ge \ell\_j$$ with $$\ell\_j \neq 0$$, you can either treat that bound as an extra constraint or shift the variable, e.g. $$x\_j=\ell\_j+z\_j$$ with $$z\_j\ge 0$$.

### 29.3-3

To formulate the dual of the maximum-flow linear program shown in equations (29.25)–(29.28), we assign dual variables to each primal constraint. Let $$y\_{uv}$$ be the non-negative dual variable for each capacity constraint $$f\_{uv} \le c(u,v)$$, and let $$p\_u$$ be the unrestricted dual variable for each flow conservation constraint for node $$u$$: $$\sum\_v f\_{vu} = \sum\_v f\_{uv}$$. To elegantly handle the objective function (29.25), we can define two constants for the source and sink nodes: $$p\_s = 1$$ and $$p\_t = 0$$ (see the text below for more details). The dual linear program is

$$
\begin{array}{ll} \text{minimize} & \sum\_{u, v \in V} c(u, v) y\_{uv} \ \text{subject to} & y\_{uv} + p\_v - p\_u \ge 0 \quad \text{for each } u, v \in V \ & p\_s = 1 \ & p\_t = 0 \ & y\_{uv} \ge 0 \quad \text{for each } u, v \in V \ & p\_u \text{ unrestricted for each } u \in V \setminus {s, t} \end{array}
$$

Because the edge variable $$f\_{uv}$$ represents flow leaving node $$u$$ (giving it a -1 coefficient in $$u$$'s conservation equation) and entering node $$v$$ (giving it a 1 coefficient in $$v$$'s conservation equation), their respective dual variables combine for that specific edge constraint to form exactly $$p\_v - p\_u$$ (see the first inequality in the model).

#### The Problem at the Boundaries

The first inequality works perfectly for intermediate nodes. However, the primal LP does not include flow conservation constraints for the source $$s$$ or sink $$t$$ (noted by $$V - {s,t}$$ in equation 29.27). Therefore, strictly speaking, the dual variables $$p\_s$$ and $$p\_t$$ do not exist. Furthermore, edges connected to $$s$$ and $$t$$ do appear in the primal objective function (29.25). If we build the dual constraints for these specific edges without $$p\_s$$ and $$p\_t$$, they look disjointed:&#x20;

* **For an edge leaving the source**: The primal objective coefficient is 1. The raw dual constraint is: $$y\_{sv} + p\_v \ge 1$$.
* **For an edge entering the source**: The primal objective coefficient is -1. The raw dual constraint is: $$y\_{vs} - p\_v \ge -1$$.

If we wrote the dual this way, we would have to list five different types of constraints depending on whether an edge touches $$s$$, touches $$t$$, or is purely intermediate. To avoid a messy formulation, we can "pretend" that $$s$$ and $$t$$ have conservation constraints and assign them dummy variables: $$p\_s = 1$$ and $$p\_t = 0$$. By defining these constants, we can use the generic formula $$y\_{uv} + p\_v - p\_u \ge 0$$ for every single edge in the graph. The dummy variables automatically recreate the correct objective coefficients algebraically.

#### Minimum-Cut Interpretation

This dual formulation perfectly mirrors the mechanics of the minimum-cut problem. Here is how the variables function as a partition and cost calculator:

* **Node Partitioning**: While $$p\_u$$ is modeled as a continuous unrestricted variable, the properties of this specific constraint matrix (total unimodularity) guarantee that an optimal solution exists where every $$p\_u$$ takes an integer value (see also the remark in [Exercise 29.2-5](#id-29.2-5)). In this case, either 0 or 1 . Therefore, $$p\_u$$ acts as a binary indicator assigning each node to one side of a cut.
  * If $$p\_u = 1$$, node $$u$$ belongs to the source set $$S$$. The constraint $$p\_s = 1$$ anchors the source node in this set.
  * If $$p\_u = 0$$, node $$u$$ belongs to the sink set $$T$$. The constraint $$p\_t = 0$$ anchors the sink node in this set.
* **Edge Selection**: The constraint $$y\_{uv} \ge p\_u - p\_v$$ dictates which edges are in a cut:
  * If an edge goes from $$S$$ to $$T$$ (where $$p\_u = 1$$ and $$p\_v = 0$$), the constraint becomes $$y\_{uv} \ge 1$$. Because we are minimizing the objective, the optimizer will force $$y\_{uv} = 1$$.
  * If an edge stays within the same set (e.g., 1 - 1 = 0) or goes backward from $$T$$ to $$S$$ (e.g., 0 - 1 = -1), the constraint is $$y\_{uv} \ge 0$$ or $$y\_{uv} \ge -1$$. Because $$y\_{uv}$$ must be non-negative, the optimizer will set $$y\_{uv} = 0$$.
* **Objective Function**: The objective $$\sum c(u,v)y\_{uv}$$ multiplies the capacity of each edge by its $$y\_{uv}$$ indicator. Because $$y\_{uv} = 1$$ only for edges crossing strictly from $$S$$ to $$T$$, the dual objective calculates the exact capacity of the cut. By minimizing this objective, the dual directly solves for the minimum cut.

### 29.3-4 🌟

{% hint style="success" %}
Introduces the [complementary slackness theorem](https://people.math.carleton.ca/~kcheung/math/notes/MATH5801/03/3_3_cs.html) in linear programming
{% endhint %}

Relying on the mechanism from the previous exercise, the resulting dual linear program is

$$
\begin{array}{ll} \text{maximize} & d \cdot p\_s - \sum\_{u, v \in V} c(u, v) y\_{uv} \ \text{subject to} & p\_u - p\_v - y\_{uv} \le a(u,v) \quad \text{for each } u, v \in V \ & p\_t = 0 \ & y\_{uv} \ge 0 \quad \text{for each } u, v \in V \ & p\_u \text{ unrestricted for each } u \in V \setminus {t} \end{array}
$$

This seems to be in contrary to the conversion table laid out in [Exercise 29.3-2](#id-29.3-2). If we apply the table to the primal constraint $$f\_{uv} \le c(u,v)$$ as written, we get a dual variable that must be non-positive. Let's call it $$y'*{uv} \le 0$$. In network economics, it is highly counterintuitive to work with negative prices or negative penalties/cost. To fix this, we define a new non-negative variable $$y*{uv} = -y'\_{uv}$$ and use it instead of the original variable.

#### Graph and Flow Interpretation

This dual formulation frames the minimum-cost-flow problem as a self-regulating market problem on the graph:

* **Node Potentials**: The variable $$p\_u$$ represents the potential of the commodity at node $$u$$. The sink node is treated as the baseline where the potential is zero ($$p\_t = 0$$). Therefore, $$p\_u$$ acts as per-unit market value of shipping a commodity from node $$u$$ toward the sink $$t$$.
* **Reduced Potential Constraints**: Rearranging the main dual constraint ($$p\_u - p\_v \le a(u,v) + y\_{uv}$$) reveals the economic logic of the edges. The potential difference between node $$u$$ and node $$v$$ cannot exceed the intrinsic per-unit cost along that edge, $$a(u,v)$$, which dictates the maximum baseline difference in market value allowed between the two nodes, plus a penalty variable $$y\_{uv}$$.&#x20;
* **Edge Tolls / Capacity Penalties**: If the potential difference between two nodes is greater than the base cost of the edge ($$p\_u - p\_v > a(u,v)$$), the constraint forces $$y\_{uv}$$ to be strictly positive to make up the difference. This $$y\_{uv}$$ acts as an additional toll on the edge. Because $$y\_{uv}$$ is multiplied by the edge capacity $$c(u,v)$$ and subtracted from the maximized objective, the system only makes $$y\_{uv}$$ positive when the edge is highly valuable and fully saturated with flow (see the explanation below).&#x20;
* **The Objective Balance**: The dual objective seeks to maximize the total value of the $$d$$ units shipped at the source minus the total capacity penalties paid across the network. By strong duality, this maximum achievable gain perfectly equals the minimum transportation cost required in the primal problem.

Complementary slackness (see [Problem 26-2](#id-29-2-complementary-slackness)) dictates that in any optimal solution, there is a strict algebraic relationship between a primal constraint's "slack" (how far it is from its limit) and the value of its corresponding dual variable. Specifically, their product must always evaluate to zero. For the minimum-cost-flow problem, the primal capacity constraint is $$f\_{uv} \le c(u,v)$$. We can express the "slack" on this edge as $$c(u,v) - f\_{uv}$$. Its corresponding dual variable is the penalty $$y\_{uv}$$. The complementary slackness condition for this specific constraint pair is

<p align="center"><span class="math">\underbrace{y_{uv}}_{\ge 0} \cdot \underbrace{(c(u,v) - f_{uv})}_{\ge 0} = 0</span> .</p>

Because both terms are non-negative, the only mathematical way for their product to be zero is if at least one of them is exactly zero. This locks the optimal solution into two possible states:

* **Unsaturated Edge**: If the edge is not operating at full capacity, the slack term is strictly positive. For the equation to equal zero, the dual variable $$y\_{uv}$$ must be exactly 0. The mathematical model cannot apply a capacity penalty to an edge that still has available room.
* **Active Penalty**: If the dual penalty variable is strictly positive, then the slack term must be exactly zero to satisfy the equation. This means $$f\_{uv} = c(u,v)$$; the edge must be completely saturated.

When the potential difference does exceed $$a(u,v)$$, it is a mathematical guarantee that the physical network has bottlenecked. By penalizing the objective function by exactly $$y\_{uv}$$ times the total capacity $$c(u,v)$$, the dual taxes away the exact aggregate value of the price bloat, perfectly bridging the physical limitations of the network with the economic valuation of the nodes.

{% hint style="info" %}
The minimum-cost-flow dual perfectly embodies the core philosophy of penalty methods: it converts a hard structural constraint into an economic penalty within the objective function.

In penalty function optimization, a constrained problem is solved by allowing constraints to be violated, but adding a severe cost to the objective function proportional to the size of the violation. The dual formulation maps directly to this concept through the mechanism of [Lagrangian relaxation](https://en.wikipedia.org/wiki/Lagrangian_relaxation).
{% endhint %}

### 29.3-5

This follows directly from the conversion table introduced in [Exercise 29.3-2](#id-29.3-2). Because the transformation rules are strictly symmetric, applying them twice acts as an identity transformation. Recall that $$(A^T)^T=A$$, thus

$$
\begin{array}{ll} \text{maximize} & c^T x \ \text{subject to} & A x \le b \ & x \ge 0 \end{array} \to \begin{array}{ll} \text{minimize} & b^T y \ \text{subject to} & A^T y \ge c \ & y \ge 0 \end{array} \to \begin{array}{ll} \text{maximize} & c^T x \ \text{subject to} & A x \le b \ & x \ge 0 \end{array}.
$$

### 29.3-6

In linear programming, the principle of weak duality dictates that the objective value of any feasible solution to a primal maximization problem is always less than or equal to the objective value of any feasible solution to its corresponding dual minimization problem.&#x20;

For a flow network, the primal problem seeks to maximize the flow, while the dual problem seeks to minimize the capacity of a cut. Corollary 24.5 establishes that any feasible primal solution (a flow) is less than or equal to any feasible dual solution (a cut). Thus, this theorem perfectly functions as the weak duality condition for the maximum-flow problem.

### 29.3-7 🌟

{% hint style="success" %}
Illustrates various conditions under which the primal LP and its dual may differ pertaining to their feasability.
{% endhint %}

The dual is

$$
\begin{array}{ll} \text{minimize} & sy \ \text{subject to} & ry \ge t \ & y \ge 0 \end{array}
$$

1. When $$r$$, $$s$$ and $$t$$ are positive then both the primal LP and its dual has the same optimal objective value of $$st/r$$.
2. When $$r$$ is negative, $$s$$ and $$t$$ are positive, only the primal LP is feasible, although the feasible  region is unbounded. The dual does not have a viable solution, since $$ry\le0\<t$$ for any $$y \ge 0$$.
3. When $$s$$ is negative, $$r$$ and $$t$$ are positive, only the dual LP is feasible, , although the feasible region is unbounded. The primal does not have a viable solution, since $$s\<rx \le 0$$ for any $$x \ge0$$.
4. When $$r=0$$, $$s$$ is negative and $$t$$ is postive neither the primal nor the dual is feasible.

### 29.3-8

The [proof](https://people.math.carleton.ca/~kcheung/math/notes/MATH5801/03/3_1_fundamental_theorem.html) is available as part of the lecture notes for the MATH 5801 Linear Optimization course.

## Problems

### 29-1 Linear-inequality feasibility

#### a.

We simply setup the corresponding linear program without an objective function (or for that matter fixing it at zero). If the solver would respond with a feasible solution, then the set of inequalities is feasible. Otherwise, it is not.

#### b.

To solve a linear programming problem using a linear-inequality feasibility algorithm, that only outputs YES/NO answers, you can use Theorem 29.4; combine the primal constraints, the dual constraints, and a strict equality condition for their objective functions into a single, unified system of inequalities.

Let the standard primal linear program be

maximize $$c^T x$$ \
subject to $$Ax \le b$$ and $$x \ge 0$$.

Its corresponding dual is&#x20;

minimize $$b^T y$$ \
subject to $$A^T y \ge c$$ and $$y \ge 0$$.

According to strong duality, if a finite optimal solution exists, the maximum primal objective value exactly equals the minimum dual objective value ($$c^T x = b^T y$$). Furthermore, weak duality guarantees that $$c^T x \le b^T y$$ for all valid primal and dual solutions.

You can construct the following single linear-inequality feasibility problem $$S$$:

* $$Ax \le b$$ (Primal constraints)
* $$x \ge 0$$ (Primal non-negativity)
* $$A^T y \ge c$$ (Dual constraints)
* $$y \ge 0$$ (Dual non-negativity)
* $$c^T x \ge b^T y$$ (Optimality condition)

Because weak duality inherently enforces $$c^T x \le b^T y$$ across the feasible regions, adding the final constraint $$c^T x \ge b^T y$$ forces the system into the exact state where $$c^T x = b^T y$$.

If the feasibility algorithm reports that $$S$$ is infeasible, the original LP is either unbounded or completely infeasible. You can definitively determine which one by running the feasibility algorithm a second time exclusively on the primal constraints. At any rate, you are done.

If the algorithm reports that $$S$$ is feasible, then treat it as a list of independent inequalities. Iterate through every single inequality one by one:

* Take the current inequality (e.g., $$a\_1 x\_1 + a\_2 x\_2 \dots \le b\_1$$).
* Temporarily convert it into a strict equality ($$a\_1 x\_1 + a\_2 x\_2 \dots = b\_1$$) by appending the reverse inequality to the system.
* Query the feasibility algorithm with this newly modified system and check the answer:
  * If YES: The optimal solution can exist on this strict boundary. Permanently keep the equality in the system.
  * If NO: No optimal solution exists on that boundary. Discard the equality and revert to the original inequality.

Geometrically, the set of optimal solutions forms a flat "face" on the polyhedron. By looping through all constraints and forcing them to be strict equations wherever mathematically possible without losing feasibility, you are algebraically shrinking that face down to its lowest possible dimension. Because standard LPs include non-negativity constraints ($$x \ge 0, y \ge 0$$), the feasible region cannot contain infinite lines (don't mix them up with rays). Therefore, the lowest-dimensional non-empty face is guaranteed to be a zero-dimensional vertex (a single unique point).

Once the loop is complete, the inequalities you successfully converted into equalities will form a full-rank system of linear equations. You simply discard the remaining inequalities and solve this system of linear equations to reveal the exact numerical values of the optimal vectors $$x$$ and $$y$$.

{% hint style="info" %}
You will likely end up with more equations than variables. For instance, in a system with 10 variables, the algorithm might lock in 14 inequalities that successfully converted to equalities. However, in a pointed polyhedron, any extra equations beyond the required 10 are simply linearly dependent (redundant). They geometrically represent multiple walls intersecting at the exact same corner. A solver for the system of linear equations may ignore them.

On the other hand, the number of variables will never be larger than the number of equations. As stated in the book "*The simplex algorithm terminates when it reaches a local maximum, which is a vertex from which all neighboring vertices have a smaller objective value.*" But for this vertex to exist all dimensions must be locked, i.e., the number of linearly independent equations must match the number of variables. Please note that while our procedure here does not behave exactly like the simplex algorithm, the underlying polyhedral geometry is identical (as both methods ultimately hunt down a vertex).
{% endhint %}

Both the number of variables and the number of inequalities scale linearly, which easily satisfies the requirement that they remain polynomial in $$n$$ and $$m$$. Furthermore, the entire process to extract the exact variables runs in polynomial time.

### 29-2 Complementary slackness

#### a.

We have $$\bar x=(8.25, 0, 1.5)$$ and $$\bar y=(0, 0.625, 0.4375)$$, thus:

* Equation (29.38): 8.25 + 0 + 3(1.5) = 12.75. Because 12.75 ≠ 30, $$y\_1$$ must be 0. ✔️
* Equation (29.39): 2(8.25) + 2(0) + 5(1.5) = 16.5 + 7.5 = 24. Because 24 = 24, $$y\_2$$ is permitted to be non-zero (0.625). ✔️
* Equation (29.40): 4(8.25) + 0 + 2(1.5) = 33 + 3 = 36. Because 36 = 36, $$y\_3$$ is permitted to be non-zero (0.4375). ✔️
* Equation (29.43): 0 + 2(0.625) + 4(0.4375) = 1.25 + 1.75 = 3. Because 3 = 3, $$x\_1$$ is permitted to be non-zero (8.25). ✔️
* Equation (29.44): 0 + 2(0.625) + 0.4375 = 1.25 + 0.4375 = 1.6875. Because 1.6875 ≠ 1, $$x\_2$$ must be 0. ✔️
* Equationt (29.45): 3(0) + 5(0.625) + 2(0.4375) = 3.125 + 0.875 = 4. Because 4 = 4, $$x\_3$$ is permitted to be non-zero (1.5). ✔️

#### b.

The [proof](https://people.math.carleton.ca/~kcheung/math/notes/MATH5801/03/3_3_cs.html) is available as part of the lecture notes for the MATH 5801 Linear Optimization course.

#### c.

See the linked material above. It answers both parts.

### 29-3 Integer linear programming

#### a.

The proof of Lemma 29.1 relies on inequalities (29.32) and (29.35) which still hold even for ILP.

#### b.

In [Problem 29-2(a)](#a-2) (where all coefficients are integers) the objective function attains the same value 30.75 both in the primal and its dual. If we restrict values to be only integers, then Theorem 29.4 doesn't hold anymore (see also the previous part). The primal ILP optimal value can be at most $$\lfloor 30.75 \rfloor = 30$$. The dual ILP optimal value must be at least $$\lceil 30.75 \rceil = 31$$.

#### c.

Theorem 29.4 says that $$P=D$$. Since an ILP is a more restricted version of LP it cannot attain a better solution than a relaxed version. Therefore, $$IP \le P$$ and $$D \le ID$$. By combining these statements we get $$IP \le P=D\le ID$$.

### 29-4 Farkas’s lemma

The [proof](https://people.math.carleton.ca/~kcheung/math/notes/MATH5801/02/2_2_farkas_lemma.html) is available as part of the lecture notes for the MATH 5801 Linear Optimization course. The linked material handles one of the many variants of the Farkas’s lemma, but all of them can be proven in virtually the same manner.

### 29-5 Minimum-cost circulation

#### a.

$$
\begin{array}{lll} \text{minimize} & \sum\_{(u,v) \in E} a(u, v) \cdot f\_{uv} & \\\[0.4cm] \text{subject to} & f\_{uv} \le c(u, v) & \text{for each } u, v \in V \\\[0.1cm] & \sum\_{v \in V} f\_{vu} - \sum\_{v \in V} f\_{uv} = 0 & \text{for each } u \in V \\\[0.1cm] & f\_{uv} \ge 0 & \text{for each } u, v \in V \end{array}
$$

#### b.

Any positive flow would increase the total cost. In this case, the zero flow is the optimal minimum-cost solution.

#### c.

To formulate the maximum-flow problem as a minimum-cost-circulation problem, we need to create a circulation network where maximizing the flow from the source $$s$$ to the sink $$t$$ corresponds to minimizing the total cost. We can achieve this by adding a "return edge" from $$t$$ to $$s$$ with an infinite capacity and a negative cost. The network will minimize its cost by pushing as much flow as possible across this negative-cost cycle.

Given the maximum-flow network $$G = (V, E)$$ with capacities $$c(u,v)$$, define the minimum-cost-circulation network $$G' = (V', E')$$ as follows:

* **Vertices:** $$V' = V$$
* **Edges:** $$E' = E \cup {(t, s)}$$ (add a single directed edge from the sink back to the source)
* **Capacities:**
  * $$c'(u, v) = c(u, v)$$ for all original edges $$(u, v) \in E$$
  * $$c'(t, s) = \infty$$
* **Costs:**
  * $$a'(u, v) = 0$$ for all original edges $$(u, v) \in E$$
  * $$a'(t, s) = -1$$

Use the LP from part (a) using these redefined elements.

#### d.

To properly reduce the single-source shortest-path problem to a minimum-cost-circulation problem, we define the new network $$G' = (V', E')$$ as follows:

* **Vertices:** $$V' = V$$
* **Edges**: $$E' = E \cup {(v, s) \mid \text{for all } v \in V - {s}}$$
* **Capacities**:
  * $$c'(u, v) = \infty$$ for all original (non-return) edges.
  * $$c'(v, s) = 1$$ for all return edges.
* **Costs**:
  * $$a'(u, v) = w(u, v)$$ for all original (non-return) edges $$(u, v) \in E$$.&#x20;
  * $$a'(v, s) = -M$$ for all return edges, where $$M$$ is a sufficiently large constant (e.g., $$M > \sum\_{(u,v) \in E} \vert{}w(u,v)\vert{}$$).

Use the LP from part (a) using these redefined elements.

By giving every return edge a capacity of 1 and a heavily negative cost, the LP is forced to push exactly 1 unit of flow from $$s$$ to every other vertex $$v$$ to reap the $$-M$$ "reward". Because it still wants to minimize the overall cost, it will route that 1 unit of flow through the original edges with the lowest possible sum of weights—effectively calculating the shortest paths to every vertex.