Assignment Problem Integer Programming Differ

In terms of the model notation the solution is:

It is interesting to observe how the integer programming model for the assignment problem is different from the combinatorial model. The assignment problem is written as an IP below. It also has a pure network flow model.

When the integrality constraints are neglected and the model is solved with an LP algorithm, the solution turns out to be integer. This fortunate event occurs because the constraint matrix has the total unimodularity property. This property assures that every extreme point of the feasible region of the LP, and hence the optimal extreme point, has all integer values. The math programming models for the transportation, maximum flow, shortest path and pure min-cost flow problems also have this characteristic. These are combinatorial problems that are easy to solve. Why create a COP model for them?

One reason is that the COP model is simpler. The IP has 0-1 variables and 2n constraints where the combinatorial model only has n variables and no constraints. A solution described by a permutation automatically satisfies the requirements that all machines are assigned and all tasks are performed.

Another reason for the COP model is that it can handle a broader range of assumptions. If one adds logical constraints to the IP model, the solution of the LP relaxation may no longer be integer and an IP algorithm such as branch and bound is necessary. A nonlinear objective function results in an integer-nonlinear model. Mild changes in the situation change the problem from easy to hard. This is illustrated in the next section.

The company's problem is to find out how much of each substance to produce at which composition, such that the profit is maximized.

Because we have two substances and three raw materials, we introduce 6 (=2 x 3 ) decision variables xij, i = A, B, and j = I, II, III.

For example, xBIII is the amount of raw material III in substance B. The goal function is thus to maximize the profits minus the treatment costs:

max 10(xAI+xAII+xAIII) + 8(xBI+xBII +xBIII) - 4(xAI +xBI) - 5(xAII +xBII) - 6(xAIII+xBIII)

Rewriting this in terms of the 6 decision variables, the equivalent problem is:

max: 6xAI + 5xAII + 4xAIII + 4xBI + 3xBII + 2xBIII

The material constraints are:

xAI + xBI      £   400
xAII + xBII    £   500
xAIII + xBIII   £   300.

The composition constraints are:

0.2(xAI + xAII+ xAIII)     ³     xAI

0.1(xAI + xAII + xAIII)     ³     xAII

0.2(xAI + xAII + xAIII)     £     xAIII

0.4(xBI + xBII + xBIII)     ³     xBI

0.5(xBI + xBII + xBIII)     ³     xBIIII

From the first inequality in the table above, we can derive the following constraint:

0 £ -0.8xAI + 0.2xAII + 0.2xAIII

Our problem has therefore five constraints from the table above plus three material constraints, and one goal function. In addition, we require that the decision variables, xij, take on only non-negative integer values.

Using your sogtware package, the optimal solution is:

xAI = 85, xAII = 42, xAIII = 299, xBI = 306, xBII = 458, xBIII = 1,

with a total gain of 4,516.

This means that the company should produce 426 kg of substance A and 765 kg of substance B. Of the 400 kg of material I only 391 kg is used, while all of the 500 kg of material II and all of the 300 kg of material III are used.

References & Further Readings:

The Copyright Statement: The fair use, according to the 1996 Fair Use Guidelines for Educational Multimedia, of materials presented on this Web site is permitted for non-commercial and classroom purposes only.
This site may be mirrored intact (including these notices), on any server with public access, and linked to other Web pages. All files are available at for mirroring.

Kindly e-mail me your comments, suggestions, and concerns. Thank you.

Professor Hossein Arsham   

This site was launched on 2/25/1994, and its intellectual materials have been thoroughly revised on a yearly basis. The current version is the 8 Edition. All external links are checked once a month.

Back to:

Dr Arsham's Home Page

EOF: 1994-2012.

0 thoughts on “Assignment Problem Integer Programming Differ

Leave a Reply

Your email address will not be published. Required fields are marked *