D2 2.2 - Allocation as a linear program

D2 2.2 - Allocation as a linear program

You will formulate one-to-one allocation problems using binary variables, complete worker and task constraints, and objectives that respect dummy and forbidden assignments.

A variable answers yes or no

Three workers and three tasks produce nine decision variables. Why does a complete allocation have only three of them equal to one?

Each variable answers a separate yes-or-no question: does this worker do this task? The constraints will make those answers fit together into one complete allocation.

You already know

The Hungarian lesson assigns one worker to each task, uses independent choices, and interprets dummy assignments in context. A feasible allocation must respect every pairing restriction. Formulating a model does not require solving it.

A linear program minimises or maximises a linear objective subject to linear constraints and specified variable domains. Here the objective adds costs or profits, and the domains make each pairing a yes-or-no decision.

In this lesson, workers A, B, C and tasks P, Q, R form a square problem in which every worker does exactly one task and every task is done by exactly one worker.

Binary allocation variable

Define

xij={1if worker i is assigned to task j0otherwisex_{ij}= \begin{cases} 1&\text{if worker }i\text{ is assigned to task }j\\ 0&\text{otherwise} \end{cases}

where i∈{A,B,C}i\in\{\mathrm A,\mathrm B,\mathrm C\} and j∈{P,Q,R}j\in\{\mathrm P,\mathrm Q,\mathrm R\}.

Thus xij∈{0,1}x_{ij}\in\{0,1\}. It is an indicator of a whole assignment, not an amount of work or a number of hours.

For example, xAQ=1x_{\mathrm{AQ}}=1 assigns A to Q. It forces the other two variables in A's row to zero and the other two in Q's column to zero, once the one-per-row and one-per-column constraints are imposed.

[DIAGRAM: asset_name: Binary variables describing a complete allocation; asset_slug: 9fm0-d2-184-binary-allocation; caption: AQ, BR and CP are selected; every worker and task has total1.; description: A three-by-three binary table with ones only at AQ,BR,CP and zeros elsewhere, displaying row and column totals1 to connect whole allocation decisions to their linear constraints.]
AQ, BR and CP are selected

There are only six complete allocations of three workers to three tasks: A has three choices, B then has two, and C has one. With five workers and five tasks, the count is already 5×4×3×2×1=1205\times4\times3\times2\times1=120. The variables describe all candidate pairs; a feasible solution selects just one compatible set.

Key idea

Allocation variables are binary. “Exactly one task for each worker” means each row sums to 11; “exactly one worker for each task” means each column sums to 11.

Row and column totals alone do not make every feasible numerical table a whole allocation.

Write the objective and every assignment equation

A selected route contributes its original cost once, so multiply each cost by the corresponding binary variable. The constraints contain coefficient 11, because each selected assignment counts as one worker–task pairing.

A complete square allocation model

For nn workers and nn tasks, with original costs cijc_{ij},

minimise Z=∑i=1n∑j=1ncijxij∑j=1nxij=1(i=1,…,n)∑i=1nxij=1(j=1,…,n)xij∈{0,1}(i,j=1,…,n)\begin{aligned} \text{minimise }Z&=\sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij}\\ \sum_{j=1}^{n}x_{ij}&=1 &&(i=1,\ldots,n)\\ \sum_{i=1}^{n}x_{ij}&=1 &&(j=1,\ldots,n)\\ x_{ij}&\in\{0,1\} &&(i,j=1,\ldots,n) \end{aligned}

For original profits pijp_{ij}, maximise ∑i∑jpijxij\sum_i\sum_j p_{ij}x_{ij} with the same assignment constraints.

Not in the formula booklet: learn it.

Use the complete row and column equations in a square exact-allocation formulation. Do not stop after writing just one set. A correct objective cannot repair a model that allows two workers to do the same task.

Worked example 1: a minimum-cost allocation model

Question. Each of three workers must do one of three tasks, and each task must be done once. Costs in pounds are

PQRA738B486C279\begin{array}{c|rrr} &\mathrm P&\mathrm Q&\mathrm R\\\hline \mathrm A&7&3&8\\ \mathrm B&4&8&6\\ \mathrm C&2&7&9 \end{array}

Formulate a linear programming model. Do not solve it.

Plan. Define binary assignment indicators, minimise the original cost, and write all three worker and all three task equations.

Let xij=1x_{ij}=1 if worker ii is assigned task jj, and 00 otherwise, where i∈{A,B,C}i\in\{\mathrm A,\mathrm B,\mathrm C\}, j∈{P,Q,R}j\in\{\mathrm P,\mathrm Q,\mathrm R\}.

minimise Z=7xAP+3xAQ+8xAR+4xBP+8xBQ+6xBR+2xCP+7xCQ+9xCRxAP+xAQ+xAR=1worker AxBP+xBQ+xBR=1worker BxCP+xCQ+xCR=1worker CxAP+xBP+xCP=1task PxAQ+xBQ+xCQ=1task QxAR+xBR+xCR=1task Rxij∈{0,1}for all listed i,j\begin{aligned} \text{minimise }Z={}&7x_{\mathrm{AP}}+3x_{\mathrm{AQ}}+8x_{\mathrm{AR}}\\ &+4x_{\mathrm{BP}}+8x_{\mathrm{BQ}}+6x_{\mathrm{BR}}\\ &+2x_{\mathrm{CP}}+7x_{\mathrm{CQ}}+9x_{\mathrm{CR}}\\ x_{\mathrm{AP}}+x_{\mathrm{AQ}}+x_{\mathrm{AR}}&=1 &&\text{worker A}\\ x_{\mathrm{BP}}+x_{\mathrm{BQ}}+x_{\mathrm{BR}}&=1 &&\text{worker B}\\ x_{\mathrm{CP}}+x_{\mathrm{CQ}}+x_{\mathrm{CR}}&=1 &&\text{worker C}\\ x_{\mathrm{AP}}+x_{\mathrm{BP}}+x_{\mathrm{CP}}&=1 &&\text{task P}\\ x_{\mathrm{AQ}}+x_{\mathrm{BQ}}+x_{\mathrm{CQ}}&=1 &&\text{task Q}\\ x_{\mathrm{AR}}+x_{\mathrm{BR}}+x_{\mathrm{CR}}&=1 &&\text{task R}\\ x_{ij}&\in\{0,1\} &&\text{for all listed }i,j \end{aligned}

Why does task P use a column equation? Its worker can be A, B or C, but exactly one of those three decisions must equal 11.

Answer. The stated binary domains, cost minimisation and six assignment equations form the required model.

Check. Set xAQ=xBR=xCP=1x_{\mathrm{AQ}}=x_{\mathrm{BR}}=x_{\mathrm{CP}}=1, with all other variables zero. All six equations hold and Z=3+6+2=11Z=3+6+2=11. This is a check of the model, rather than a requested solution method.

Worked example 2 changes only the original AQ cost, from 33 to 55 pounds. The workers and tasks are unchanged.

Worked example 2: changing one cost leaves feasibility unchanged

Question. Formulate the revised minimum-cost allocation problem.

Plan. Keep the binary definitions and every assignment equation. Change just the AQ coefficient.

For the same definitions xij∈{0,1}x_{ij}\in\{0,1\}, i∈{A,B,C}i\in\{\mathrm A,\mathrm B,\mathrm C\}, j∈{P,Q,R}j\in\{\mathrm P,\mathrm Q,\mathrm R\}, write

minimise Z=7xAP+5xAQ+8xAR+4xBP+8xBQ+6xBR+2xCP+7xCQ+9xCRxAP+xAQ+xAR=1xBP+xBQ+xBR=1xCP+xCQ+xCR=1xAP+xBP+xCP=1xAQ+xBQ+xCQ=1xAR+xBR+xCR=1xij∈{0,1}for all listed i,j\begin{aligned} \text{minimise }Z={}&7x_{\mathrm{AP}}+5x_{\mathrm{AQ}}+8x_{\mathrm{AR}}\\ &+4x_{\mathrm{BP}}+8x_{\mathrm{BQ}}+6x_{\mathrm{BR}}\\ &+2x_{\mathrm{CP}}+7x_{\mathrm{CQ}}+9x_{\mathrm{CR}}\\ x_{\mathrm{AP}}+x_{\mathrm{AQ}}+x_{\mathrm{AR}}&=1\\ x_{\mathrm{BP}}+x_{\mathrm{BQ}}+x_{\mathrm{BR}}&=1\\ x_{\mathrm{CP}}+x_{\mathrm{CQ}}+x_{\mathrm{CR}}&=1\\ x_{\mathrm{AP}}+x_{\mathrm{BP}}+x_{\mathrm{CP}}&=1\\ x_{\mathrm{AQ}}+x_{\mathrm{BQ}}+x_{\mathrm{CQ}}&=1\\ x_{\mathrm{AR}}+x_{\mathrm{BR}}+x_{\mathrm{CR}}&=1\\ x_{ij}&\in\{0,1\}\quad\text{for all listed }i,j \end{aligned}

Why do the constraints not change? A higher price does not make a previously possible worker–task pairing impossible. It changes the objective value when that pairing is selected.

Answer. Minimise the revised cost over exactly the same binary feasible set.

Check. The earlier assignment still has ones at AQ, BR, CP. Its cost is now 5+6+2=135+6+2=13, exactly 22 more because AQ is selected once. An allocation not using AQ would have no cost change.

Original costs with minimisation, or original profits with maximisation, make the interpretation easiest. A correctly transformed Hungarian cost objective is equivalent, but its coefficients must be paired with minimisation rather than maximisation.

Watch out

Wrong: define xijx_{ij} as a number of hours, allow arbitrary fractions, or write only the three worker equations. Right: define a binary yes-or-no assignment and include both the worker and task equations.

Change the same original cost once more.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account