Model the following problems in terms of LP and ILP and solve the LP-models with a solver of your choice: PC-Prog, SIMPLEX, or better LINDO or CPLEX. See Dealing with LP-problems for further explanations. In these exercise make a proper distinction beteen LP and ILP models.
An ILP (Integer Linear Programming problem) is formulated as an LP (Linear Programming problem) with the additional requirement that some variables can only take integral values. Note that, from a mathematical view point, this makes a big difference: the set of solutions is much smaller now. DO NOT be tempted to believe - let alone speak out loud - that this will lead to an easier problem. The contrary is true!
Note that the simplex method, dealt with in the theoretical part, only deals with problems stated in continuous variables. Yet, one may use the simplex method as a tool to find integral solutions. The first trick is to forget about the integrality conditions for a moment, and hope for the best. Iff - by coincidence - the solution returned by the simplex method, is integral after all, you are done. However, if that is not the case, the principle of branch-and-bound may be applied. Select a variable that has a fractional value in the optimal solution to the LP. And split the current problem into two cases which have to be dealt with separately. Both cases should exclude the particular solutiuon found in the first place. Note that you may end up with having to check an exponentional number of subcases!
DEFINITION:
Given a set of N points (N even), and given edges between these points, with
associated to them a cost; a PERFECT MATCHING on the graph is a selection of N
pairwise disjoint edges. The cost of a MATCHING is the sum of the costs of its
edges. An OPTIMAL perfect matching is a perfect matching of MINIMUM cost.
Problem 1:
Formulate - in general - the perfect matching problem on N points, with costs
C_ij on the edge between points i and j, as an Integral Linear Programming
problem.
Problem 2:
Give a complete formulation of the perfect matching problem on 24 points, given
the costs in the matrix below. Set up the problem in LP-format and solve it.
In order to prevent typing errors a possible objective function is given in MatchingCost.
Problem 3:
Use the formulation of the problem above and drop the integrality constraints.
Solve the problem and describe the difference to the previous answer.
DEFINITION:
We are given a set of N points V and a set of N points W. Furthermore there are
costs assigned to edges between point v in V and w in W. A BIPARTITE MATCHING
is a subset of N edges (all containing one point from V and one from W, that
have no point in common. An OPTIMAL bipartite matching is one of minimal
cost.
Problem 4:
Formulate - in general - the Bipatite Matching problem as an ILP.
Problem 5:
Set up the complete formulation of the bipartite matching problem on 24 points in total,
with V = {1,2,...,12} and W = {13,14,...,24}, and use the cost matrix below.
Find the cheapest bipartite matching.
Problem 6:
Use the formulation of the problem above and drop the integrality constraints.
Solve the problem and describe the difference to the previous answer.
Problem 7:
What is the difference betwwen the GENERAL and the BIPARTITE MATCHING problem, if you solve them both with teh
(I)LP-model? Are they essentially different? If so, why?
Problem 8:
Is the optimal solution to the bipartite problem (problem 5) UNIQUE? Can there
be another solution of equal cost? Hint: use the possibilities of sensitivity
analysis for LP-problems.
24 by 24 cost table
0 877 73 922 583 1296 1735 1117 1220 1062 1634 1783 1190 1587 1997 2011 1764 1067 1699 1644 1312 1909 1493 1315 877 0 812 900 339 1725 1140 1429 1554 2002 1282 1627 1900 1865 1924 1611 1983 1120 1673 1593 1904 1864 1157 1877 73 812 0 851 921 1944 1527 1542 1232 1412 1011 1547 1200 1911 1887 1925 1027 1292 1456 1005 1574 1059 1905 1415 922 900 851 0 983 1493 1374 1080 1142 1968 1984 2006 1101 1837 1834 2022 1757 1337 1540 1989 1749 1552 1512 1950 583 339 921 983 0 1439 1375 1851 1467 1667 1283 1472 1217 1343 1354 1633 1302 1847 2007 1382 1989 1951 1342 1972 1296 1725 1944 1493 1439 0 28 155 782 27 1912 1095 1567 1877 1844 1095 1366 1770 1535 1741 1598 2002 1385 1881 1735 1140 1527 1374 1375 28 0 450 602 200 1804 1211 1503 1627 1195 1885 1593 1122 1204 1541 1151 1359 1299 1178 1117 1429 1542 1080 1851 155 450 0 248 394 1745 1101 1214 1841 1467 1985 1352 1185 1559 1330 1570 1416 1780 1148 1220 1554 1232 1142 1467 782 602 248 0 617 1561 1360 1096 1164 1555 1981 1757 1677 1161 1274 1828 1521 1573 2006 1062 2002 1412 1968 1667 27 200 394 617 0 1769 1967 1728 1870 1158 1545 1314 1119 1897 1499 1678 1203 1045 1070 1634 1282 1011 1984 1283 1912 1804 1745 1561 1769 0 983 193 687 520 1553 1783 1685 1084 1741 1418 1762 1902 1693 1783 1627 1547 2006 1472 1095 1211 1101 1360 1967 983 0 566 399 242 1549 1144 1186 1253 2015 1344 1798 1305 1463 1190 1900 1200 1101 1217 1567 1503 1214 1096 1728 193 566 0 671 804 1117 1874 1849 1187 1833 1018 1875 1330 1572 1587 1865 1911 1837 1343 1877 1627 1841 1164 1870 687 399 671 0 634 2015 1656 1351 1409 1394 1230 1078 1961 1629 1997 1924 1887 1834 1354 1844 1195 1467 1555 1158 520 242 804 634 0 1321 1486 1774 1507 1739 1765 1851 1513 1046 2011 1611 1925 2022 1633 1095 1885 1985 1981 1545 1553 1549 1117 2015 1321 0 290 160 850 407 1010 1675 1594 1843 1764 1983 1027 1757 1302 1366 1593 1352 1757 1314 1783 1144 1874 1656 1486 290 0 693 445 149 1241 1056 1140 1898 1067 1120 1292 1337 1847 1770 1122 1185 1677 1119 1685 1186 1849 1351 1774 160 693 0 407 550 1268 1637 1628 1205 1699 1673 1456 1540 2007 1535 1204 1559 1161 1897 1084 1253 1187 1409 1507 850 445 407 0 243 1949 1691 2017 1432 1644 1593 1005 1989 1382 1741 1541 1330 1274 1499 1741 2015 1833 1394 1739 407 149 550 243 0 1406 1758 1259 1919 1312 1904 1574 1749 1989 1598 1151 1570 1828 1678 1418 1344 1018 1230 1765 1010 1241 1268 1949 1406 0 804 549 55 1909 1864 1059 1552 1951 2002 1359 1416 1521 1203 1762 1798 1875 1078 1851 1675 1056 1637 1691 1758 804 0 630 956 1493 1157 1905 1512 1342 1385 1299 1780 1573 1045 1902 1305 1330 1961 1513 1594 1140 1628 2017 1259 549 630 0 65 1315 1877 1415 1950 1972 1881 1178 1148 2006 1070 1693 1463 1572 1629 1046 1843 1898 1205 1432 1919 55 956 65 0