7.1. A mining problem. A mining operation has identified an area where the ore is rich enough to excavate. The excavation proceeds in distinct blocks from the surface down- ward. (Digging a hole is one of the few jobs in the world where you start at the top.) The problem is sketched in its two-dimensional form with numbered blocks in the following figure. In practice, a three-dimensional problem would be solved, but the problem is pre sented to illustrate a point, and the two-dimensional problem version is sufficient for this purpose 6 Because of the angle of slip, block 5 cannot be mined unless both blocks I and 2 are mined. Similar relations hold for the rest of the blocks in the arrangement. By the use of bore holes, the mining company has estimated the ore content in each of the Integer Programming and Its Applications Chap. 7 blocks. From this information, a profit or loss can be associated with each block. The profit or loss is the value of the refined ore less the cost of removal of that block and the cost of refining it (beneficiation). We let P profit or loss associated with block j; and x,1,0;it is 1 if block j is removed and 0 otherwise This is a case where there are two formulations of the problem. One formulation is integer-friendly; the other is integer-unfriendly. The second formulation, the integer- unfriendly one, is obtained by summing pairs of the constraints from the first formula tion. The first formulation, it turns out, is more than integer-friendly. The matrix of the constraint set is unimodular. but there is no need for you to prove this. Formulate this zero-one programming problem both ways and explain by a simple example why the integer-unfriendly version is integer-unfriendly. You may leave your formulation in non-standard form to explain integer friendliness/unfriendliness 10 7.1. A mining problem. A mining operation has identified an area where the ore is rich enough to excavate. The excavation proceeds in distinct blocks from the surface down- ward. (Digging a hole is one of the few jobs in the world where you start at the top.) The problem is sketched in its two-dimensional form with numbered blocks in the following figure. In practice, a three-dimensional problem would be solved, but the problem is pre sented to illustrate a point, and the two-dimensional problem version is sufficient for this purpose 6 Because of the angle of slip, block 5 cannot be mined unless both blocks I and 2 are mined. Similar relations hold for the rest of the blocks in the arrangement. By the use of bore holes, the mining company has estimated the ore content in each of the Integer Programming and Its Applications Chap. 7 blocks. From this information, a profit or loss can be associated with each block. The profit or loss is the value of the refined ore less the cost of removal of that block and the cost of refining it (beneficiation). We let P profit or loss associated with block j; and x,1,0;it is 1 if block j is removed and 0 otherwise This is a case where there are two formulations of the problem. One formulation is integer-friendly; the other is integer-unfriendly. The second formulation, the integer- unfriendly one, is obtained by summing pairs of the constraints from the first formula tion. The first formulation, it turns out, is more than integer-friendly. The matrix of the constraint set is unimodular. but there is no need for you to prove this. Formulate this zero-one programming problem both ways and explain by a simple example why the integer-unfriendly version is integer-unfriendly. You may leave your formulation in non-standard form to explain integer friendliness/unfriendliness 10
