Yödelheim Ministry of Transport


The country of Yödelheim has three tunnels and two bridges that need to be repaired:
the Niffelheim tunnel, the Moria tunnel, the Orpheus tunnel, the Bifrost bridge, and the Gjallarbrú bridge.

The Yödelheim Ministry of Transport has only enough equipment and labor force in-house to repair any one of these.   Because of the nature of government accounting, it will cost ten million Rheingolds (®10,000,000) whichever project they do in-house.

Whichever project they do themselves, they will outsource each of the other four to a private company.  The Prime Minister has decreed that they cannot give more than one of these large projects to any one company, even if it is the lowest bidder on more than one.

Four private companies have each bid on some of the projects: Trolls R Us, NoTrump Bridge & Tunnel, Dante's Underworld Enterprises, and the Tallahatchee Bridge Company.

Trolls R Us has bid ®12,000,000 to repair the Niffelheim tunnel,  ®7,500,000 to repair  the Moria tunnel,  ®18,000,000 to repair the Orpheus tunnel,  ®5,000,000 to repair  the Bifrost bridge, and  ®11,000,000 to repair  the Gjallarbrú bridge.

NoTrump Bridge & Tunnel has bid ®11,000,000 to repair the Niffelheim tunnel,  ®16,000,000 to repair the Moria tunnel,  ®15,000,000 to repair the Orpheus tunnel,  ®5,000,000 to repair  the Bifrost bridge, and  ®15,000,000 to repair  the Gjallarbrú bridge.

Dante's Underworld Enterprises has bid ®8,000,000 to repair the Niffelheim tunnel,  ®15,000,000 to repair  the Moria tunnel, and ®6,000,000 to repair  the Orpheus tunnel.  As an underground specialist, they did not submit any bids to repair the Bifrost bridge or the Gjallarbrú bridge.

The Tallahatchee Bridge Company has bid ®7,000,000 to repair  the Bifrost bridge, and  ®11,000,000 to repair  the Gjallarbrú bridge.  They did not submit bids on any of the tunnels.

The Ministry of Transport needs to decide which project to do in-house, and which project to award to each of the four companies.

One way to do this would be to start with the lowest bid, then the lowest bid amount the remaining companies and projects, and so on.  Expressing costs in millions of Rheingolds, the bids are as follows:


  Niffelheim tunnel Moria
tunnel
Orpheus tunnel Bifrost bridge Gjallarbrú bridge
YMOT 10 10 10 10 10
Trolls 12 7.5 18 5 11
NoTrump 11 16 15 10 15
Dante 8 15 6 99 99
Tall 99 99 99 7 11

The lowest bid is Trolls R Us's ®5,000,000 to repair the Bifrost bridge. If we make this award, the remaining decision looks like this:

  Niffelheim tunnel Moria
 tunnel
Orpheus tunnel Gjallarbrú bridge
YMOT 10 10 10 10
NoTrump 11 16 15 15
Dante 8 15 6 99
Tall 99 99 99 11

The best opportunity in this table is to award the Orpheus Tunnel project to Dante's Underworld Enterprises for ®6,000,000. After that, we are down to

  Niffelheim tunnel Moria
 tunnel
Gjallarbrú bridge
YMOT 10 10 10
NoTrump 11 16 15
Tall 99 99 11

The Yödelheim Ministry of Transport itself is the lowest cost option for each of the three remaining projects, at ®10,000,000. It should be clear that they should take on the Moria tunnel repairs since the only other option is the highest of the remaining bids. (99 is used to indicate no bid.) That brings us to the last two:

  Niffelheim tunnel Gjallarbrú bridge
NoTrump 11 15
Tall 99 11

NoTrump Bridge & Tunnel is the only option left for the Niffelheim tunnel at ®11,000,000, leaving Tallahatchee Bridge Company to repair the Gjallarbrú bridge also for ®11,000,000.

The total cost of this selection is ®5,000,000 + ®6,000,000+ ®10,000,000+ ®11,000,000+ ®11,000,000, or 43 million Rheingolds

However, this method (known as the "greedy algorithm") actually wastes 1.5 million Rheingolds.
The best solution can be found using Linear Programming; problems of this type are collectively known as Assignment problems.

See Yodelheim.xls for the LP solution, with a total cost of 41.5 million Rheingolds.

The matrix B3:F7 contains the costs (in millions of Rheingolds) for each potential assignment of a project to an organization.  These are the coefficients of the objective function.  They are called "Objective Coefficients" for short in the sensitivity report.  (To see the answer reports and sensitivity reports, download the spreadsheet, run Solver, and request these reports in the Solver Results box.)

The numbers in the matrix B12:F15 are the assignments: 1 means the organization specified in the row does the project specified in the column.  These assignments are the decision variables in an assignment problem, so they are specified in the "By Changing Cells" box in the Solver setup.  They're called "Adjustable Cells" in the Answer Report and the Sensitivity Report.

There are two blocks of constraints in addition to the usual non-negativity constraints.  The first block requires each organization to do one and only one project; the total number of projects assigned to each organization can be found in cells G 12:G15, and there is a constraint line that says each of these cells must be EQUAL (not less than or equal to) the RHS constant 1.  Similarly, each project must be assigned to one and only one organization;
the total number of organizations  assigned to each project can be found in cells B 16:F15, and there is a constraint line that says each of these cells must be EQUAL (not less than or equal to) the RHS constant 1.

The matrix B20:F24 shows the assignments in terms of the cost; it is found by multiplying corresponding numbers in the cost matrix and the assignment matrix.  Row 25 summarizes the costs for each project.  The objective function, total cost, is the sum of row 25, found in cell  B27.  So, in the Solver setup, the Target Cell is B27.  Of course, min is checked instead of max;
the Yödelheim taxpayers would not appreciate a Ministry of Transport that used the maximum cost option!


Technical notes:
This is NOT an "integer programming" or "binary programming" problem,  The mathematics of the problem automatically give all decision variables an value of zero or one without having to force this directly.
Also, assignment problems are always highly degenerate, but that's OK since changing the RHS of a constraint would violate the basic assumptions of the assignment problem anyway.
Finally, if there are more rows than columns and one project had to be carried over until next year, we would create another row labeled "next year" and fill in the cost matrix for this row with the cost of delaying each of the six projects.  If, instead, we had five projects and six organizations, we could create another column called "no project."  The Ministry's costs in this column of the cost matrix would ordinarily be zero.