\myheading{Wood workshop, linear programming and Leonid Kantorovich}

\renewcommand{\CURPATH}{equations/kantorovich}

Let's say, you work for a wood workshop.
You have a supply of rectangular wood workpieces, 6*13 inches, or meters, or whatever unit you use:

A workpiece (6*13 inches):

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.45]
	\draw[thick] (0,0) rectangle ++(13,6); % width, height
\end{tikzpicture}
\caption{A 6*13 workpiece}
\end{figure}

You want to produce 800 rectangles of 4*5 size and 400 rectangles of 2*3 size:

\begin{figure}[H]
\centering

\begin{subfigure}{.5\textwidth}
\centering
\begin{tikzpicture}[scale=0.45]
	\draw[thick] (0,0) rectangle ++(5,4); % width, height
\end{tikzpicture}
\caption{Output A (4*5, we want 800 of these)}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
\centering
\begin{tikzpicture}[scale=0.45]
	\draw[thick] (0,0) rectangle ++(3,2); % width, height
\end{tikzpicture}
\caption{Output B (2*3, we want 400 of these)}
\end{subfigure}
\caption{Rectangles we want}
\end{figure}

To cut a piece as A/B rectangles, you can cut a 6*13 workpiece in 4 ways.
Or, to put it in another way, you can place A/B rectangles on 6*13 rectangle in 4 ways:

% https://tex.stackexchange.com/questions/37581/latex-figures-side-by-side
\begin{figure}[H]
\centering

\begin{subfigure}{.5\textwidth}
\centering
\begin{tikzpicture}[scale=0.45]
	\draw[thick] (0,0) rectangle ++(4,5); % width, height
	\draw[thick] (4,0) rectangle ++(4,5);
	\draw[thick] (8,0) rectangle ++(5,4);
	\draw[thick] (8,4) rectangle ++(3,2);
\end{tikzpicture}
\caption{Cut A (Output A: 3, Output B: 1)}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
\centering
\begin{tikzpicture}[scale=0.45]
	\draw[thick] (0,0) rectangle ++(5,4);
	\draw[thick] (5,0) rectangle ++(5,4);
	\draw[thick] (0,4) rectangle ++(3,2);
	\draw[thick] (3,4) rectangle ++(3,2);
	\draw[thick] (6,4) rectangle ++(3,2);
	\draw[thick] (9,4) rectangle ++(3,2);
	\draw[thick] (10,0) rectangle ++(3,2);
	\draw[thick] (10,2) rectangle ++(3,2);
\end{tikzpicture}
\caption{Cut B (Output A: 2, Output B: 6)}
\end{subfigure}

\begin{subfigure}{.5\textwidth}
\centering
\begin{tikzpicture}[scale=0.45]
	\draw[thick] (0,0) rectangle ++(4,5);

	\draw[thick] (4,0) rectangle ++(3,2);
	\draw[thick] (4+3,0) rectangle ++(3,2);
	\draw[thick] (4+3+3,0) rectangle ++(3,2);

	\draw[thick] (4,2) rectangle ++(3,2);
	\draw[thick] (4+3,2) rectangle ++(3,2);
	\draw[thick] (4+3+3,2) rectangle ++(3,2);

	\draw[thick] (4,2+2) rectangle ++(3,2);
	\draw[thick] (4+3,2+2) rectangle ++(3,2);
	\draw[thick] (4+3+3,2+2) rectangle ++(3,2);
\end{tikzpicture}
\caption{Cut C (Output A: 1, Output B: 9)}
\end{subfigure}%
\begin{subfigure}{.5\textwidth}
\centering
\begin{tikzpicture}[scale=0.45]
	\draw[thick] (0,0) rectangle ++(2,3);
	\draw[thick] (0,3) rectangle ++(2,3);

	\draw[thick] (2,0) rectangle ++(2,3);
	\draw[thick] (2,3) rectangle ++(2,3);

	\draw[thick] (2+2,0) rectangle ++(2,3);
	\draw[thick] (2+2,3) rectangle ++(2,3);

	\draw[thick] (2+2+2,0) rectangle ++(2,3);
	\draw[thick] (2+2+2,3) rectangle ++(2,3);

	\draw[thick] (2+2+2+2,0) rectangle ++(2,3);
	\draw[thick] (2+2+2+2,3) rectangle ++(2,3);

	\draw[thick] (2+2+2+2+2,0) rectangle ++(3,2);
	\draw[thick] (2+2+2+2+2,2) rectangle ++(3,2);
	\draw[thick] (2+2+2+2+2,2+2) rectangle ++(3,2);
\end{tikzpicture}
\caption{Cut D (Output A: 0, Output B: 13)}
\end{subfigure}%
\caption{Four ways of cutting the workpiece}
\end{figure}

Now the problem.
Which cuts are most efficient?
You want to consume as little workpieces as possible.

This is optimization problem and I can solve it with Z3:

\lstinputlisting[style=custompy]{\CURPATH/1.py}

\lstinputlisting{\CURPATH/1.txt}

So you want to cut 250 workpieces in A's way and 25 pieces in B's way, this is the most optimal way.

Also, the problem is small enough to be solved by my toy bit-blaster MK85,
(thanks to the Open-WBO MaxSAT solver):

\lstinputlisting[style=customsmt]{\CURPATH/1.smt}

\lstinputlisting[caption=The result]{\CURPATH/res.txt}

The task I solved I've found in Leonid Kantorovich's book 
"The Best Uses of Economic Resources" (1959).
And these are 5 pages with the task and solution
\footnote{\url{\RepoURL/\CURPATH/from_book}}
(in Russian).

Leonid Kantorovich was indeed consulting plywood factory in 1939 about optimal use of materials.
And this is how linear programming (LP) and \ac{ILP} has emerged.

See also: \url{https://en.wikipedia.org/wiki/Guillotine_cutting\#Finding_an_optimal_cutting-pattern}.