Operating Guide for Multiple Choice Integer Programming Code (MCIPC) James C. Bean Charles E. Noon Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 Technical Report 86-42 December 1986

Operating Guide for Multiple Choice Integer Programming Qode (MCIPC) James C. Bean Charles E. Noon Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109 The Multiple Choice Integer Programming Code (MCIPC) is a FORTRAN computer code for solving pure zero-one multiple choice integer programs. The multiple choice structure means that the variables are initially grouped into mutually exclusive sets with the constraint that exactly one variable in each set will be equal to 1 and all others equal to zero. The MCIPC takes advantage of this structure by exploring fewer branches and computing quick, strong bounds from a Lagrangian Alteration of the problem (see references). The program is not interactive in any way. Operation requires proper formulation, development of an input file, and program execution. The formulation requires the variables to be divided into mutually exclusive sets referred to as as Multiple Choice or MC sets. For each set, the formulation must contain the constraint that the sum of the variables of the set must equal 1. General constraints only in the form of inequalities may also be included. Details about the formulation are discussed in the next section with later sections describing the input format, program execution and the output. A sample problem provides formulation, input file and output file examples. This document contains no detail on the solution procedure. The user is referred to the technical references. FORMULATION The following represent program requirements for formulation. All 0/1 Variables: The code can only handle pure 0/1 integer problems. There is no easy way to formulate a mixed integer problem to be solved with this code. Mutually Exclusive Sets: The variables must be divided into an exhaustive, mutually exclusive collection of multiple choice sets. A feasible solution will choose only one variable in each set to be equal to 1, all others 0. If the problem contains sets which are not mutually exclusive, create duplicates of overlapping variables and include them in each of the overlapping sets. To ensure feasibility, add general constraints which set the duplicate variables equal to one another. Must Choose One of Set: The code implies the constraint that "exactly one" of the variables in each set must be set to 1. In many practical problems, the constraint 1

may be "at most one" in each set. In this case, the code requirement can be adhered to by simply adding a dummy variable with a cost coefficient of zero. General Constraints: All General Constraints must be of the greater-than-or-equal type. Any constraints which are < can be changed by multiplying each side by -1. Equality constraints can be replaced by a pair of inequalities (i.e., Ax = b is equivalent to Ax > b with Ax < b ). Minimization Objective: The codes automatically assumes the formulation is modeled as a minimization problem. If a problem is a maximization, simply change the signs of the objective function coefficients. Problem Size Limitations: As currently dimensioned, problems may have up to 100 sets of variables with 10 variables per set. These dimensions may be easily changed in the code, however, an upper limit of 1000 total variables may not be violated or changed easily. The current limit on the number of general constraints is 200. Variable Identification: The code does not record or output solutions using variable "names". A variable is described by its MC set number and its index within that set. The program reports a final solution by identifying the index of the variable chosen in each set. The following notation will be used in the formulation and in later sections, M - the number of MC sets. Ni - the number of variables of MC set i, i = 1,2,..., M. xij - the jth variable of the MC set i, i= 1,2,..., M; j = 1,2,..., Ni cij - the cost associated with the 3th variable of the MC set i. K - the number of General Constraints (not including the MC constraints). bk - the right hand side value of the kth constraint. aijk - the kth constraint coefficient for the jth variable of the MC set i. The problem Formulation can now be stated as, Minimize d1E CA-iECiji Subject to, (MC Constraints) E1 xi = 1 for i = 1,2,... M. (General Constraints) Ei E1,pRjXij > bk for k = 1,2,..., K. xii E {0, 1} for all i = 1,2,..., M and j = 1,2,..., Ni. 2

PROGRAM INPUT The input file consists of three main parts; problem specifications, general constraint data, and objective function cost coefficients. The line numbers correspond to the sample input file provided on page 8 for reference. Careful attention should be given with respect to spacing since all input is formatted read. *The problem specifications make up the first four lines of the input file. Please note that the first column is blank for each. Line 1, " GUBS xxx": Specifies the number of Multiple Choice (a.k.a. GUBS) sets in the problem. "GUBS" is a keyword and xxx is the number of sets. Read FORMAT(1X,A4,3X,I3). Line 2, " ENDV xx xx xx....: Specifies the number of variables in each MC set. "ENDV" is a keyword and the "xx"s are the numbers in each of the M sets specified in Line 1. Read FORMAT(1X,A4,3X,100I3) Line 3, " NCON xxx": Specifies the number of General Constraints not including the MC constraints since they are implied. Read FORMAT(1X,A4,3X,I3). Line 4, " PCTG x.xx yyyy.y": Specifies the variable elimination cutoff and an initial upper bound. "PCTG" is a keyword. "x.xx" is a number greater than 0.00 and less than 1.00 called the variable elimination cutoff. One of the first steps of the solution procedure involves eliminating variables which should not be considered. This is done by first computing the difference between the initial upper and lower bounds of the problem. That difference is then multiplied by PCTG/(1 -PCTG) to determine a cost cutoff value. If the difference between a variable's cost and the lowest cost of the MC set exceeds this value then the high cost variable will be eliminated (a higher PCTG value W 0.90 may result in longer computation times but may yield better solutions, see Bean[1984] for details). "yyyy.y" is a known upper bound on the problem (if none exists, set it to a large number). Read FORMAT(1X,A4,3X,F6.4,3X,F7.0). *The General Constraint Data consists of the right-hand-side values and the non-zero left-hand-side constraint coefficients. Line 5, " RHSV: A necessary keyword indicating the Right-Hand-Side Values are to follow. FORMAT(1X,A4). Lines 6, 7, or as needed, " bl b2 b... ": These are the General Constraint set RHS values. (the formulation's b's ). The number of RHS values must be equal to the number of constraints indicated in Line 3. As mentioned earlier, the general constraints should not include the Multiple Choice constraints of the formulation. 3

The MC constraints are automatically added internally in the code. Also, it should be reminded that the general cosntraints can only be inequalities of the > type. FORMAT(8X,5F8.2). Line 8 or next line, " COEF": A necessary keyword indicating the general constraint coefficients are to follow. FORMAT(1X,A4). Lines 9-51, or next as needed, " i j aijk ": These lines describe the non-zero general constraint coefficients. Each line identifies the MC set (i), the index of the variable within the set (j), and that variable's coefficient (aij,). The coefficients are listed sequentially by constraint with the constraint groups separated by a 0 in the MC set (see example). Within each constraint group, the coefficients must be ordered first by MC set, then by index within the set. The line following the last coefficient of the last constraint must have a 0 in the MC set (line 51 of example). FORMAT(8X,2I3,F10.3). *The last component of the MCIPC input file contains the Objective Function Cost Coefficients. The code automatically assumes the problem is modeled as a minimization. Line 52 or next line, " COST": A necessary keyword indicating the non-zero Objective Function Coefficients are to follow. FORMAT(1X,A4). Lines 53-66 or next as needed, " i j ii ": These lines describe the non-zero objective function coefficients. Each line identifies the MC set (i), the index of the variable within the set (j), and that variable's objective coefficient (ci3). One word of caution, since the read is formatted to continue until the end of the file, make sure there are no blank lines after the last entry in the file. FORMAT(8X,2I3,F10.3). 4

PROGRAM EXECUTION The code is written in FORTRAN and has no interactive operation. The input file is read through Input/Output File 1 and the output is written to I/OF 6. -Before compilation, a few changes are necessary with respect to execution clocking. The code contains seven calls to a system specific TIME subroutine for clocking execution times. These calls will need to be changed according to your particular system or removed from the code. Two of the calls are located in the MAIN program, three calls are in subroutine BALAS, one call each in the subroutines OUT and VARRED. PROGRAM OUTPUT The program output consists of four main parts; some input data, variable elimination data, incumbent solution data, and final solution data. The line numbers correspond to the sample output file provided on page 9 for reference. * The first eight or so lines simply restate some of the input data. Line 1, " M=... X: The number of MC sets. Line 2, " END:...... X: This vector displays the number of variables per MC set. Line 3, "NCON=... ": The number of general constraints. Line 4, " PCTGE=... X: The variable elimination cutoff value. Line 5,... n: Restatement of input upper bound. Lines 6,7 " BO:......: These are the negative of the general constraint righthand-side values. Line 8, " COSTBD=... ": This value is the result of computations involving the upper bound and should be ignored. * The following four lines are produced during a Variable Elimination subroutine called VARRED. Line 9, " THE FOLLOWING OUTPUT IS PRODUCED BY VARRED ": Line 10, "PROBJ=...: This is the objective value of the linear programming relaxation of the original problem. Line 11, " DELTA=...: This value represents the maximum allowable difference between variable objective costs within a Multiple Choice set. A variable will be eliminated if the difference between its cost and the lowest cost of the set exceeds DELTA. See Bean[1984] for details. 5

Line 12, " NVAR=... ": The number of variables remaining after the variable elimination procedure. * For every intermediate Incumbent Solution, the subroutine OUT produces the following six lines of output. Line 13, THE FOLLOWING OUTPUT IS PRODUCED BY OUT: Line 14, NITR=... ": This is the cumulative number of branch and bound nodes explored before the new incumbent solution was reached. Line 15, " ITCNT=... ": This is the cumulative number of simplex algorithm pivots performed before the new incumbent solution was reached. Line 16, " CX= *...: This is the value of the newly found solution evaluated with the original problem objective costs. Line 17, " Z=... ": This is the value of the newly found solution evaluated with the Lagrangian adjusted objective costs. Line 18, " RATIO=... ": This value is computed by taking the difference between CX (Line 16) and the current lower bound, and then dividing by CX. It is an upper bound on how far the solution value is from the optimal. In the example problem, the current solution is at most 9.24 percent from the optimal. Line 19, " LOC VECTOR FROM SUBROUTINE OUT:...... ": This vector represents the newly found incumbent solution. The ith vector component is the index of the variable equal to 1 in the ith MC set. For the example problem, the variables Xi4, zX2, a31, z43, and xsz are set equal to 1 and all others equal to 0. *The Final Solution data is presented in the last nine linest of the output file by the subroutine BOUND. Most of the data is defined the same as above. The " ERROR= " value (line 24) is the same type bound on the optimal as RATIO (line 18), only sometimes stronger. The final "LOC VECTOR... " (line 27) represents the final solution of the problem in the same fashion as Line 19. 6

SAMPLE PROBLEM The following is an example problem with 5 MC sets and 6 general constraints. The input and output files for this problem are included in the next sections. MINIMIZE 26.0x11 + 7.0X21 + 4.4X31 + 11.9X41 + 14.5Z51 - 12.6X12 + 0.3z22 + 6.4a32 - 4.7z42 + 11.2X52 + 10.7xi3 + 3.8X14 + 4.2X2s + 8.8X43 Subject to, Multiple Choice Constraints Xll X21 X31 X41 X51 + + + + + X12 X22 X32 X42 X52 + X13 + X23 + 214 = 1 - 1 1 1 - 1 + x43 General Constraints (1) (2) (3) 2.9xni + 2.5X212 + 1.Ozs + 3.3z14 + 4.2221 + 1.0222 + 3.2223 + 4.1z31 + 1.5X32 + 3.0241 + 2.7X42 + 5.3x43 + 3.2z51 + 2.6Xs2 > Zll + 213 + 221 + 222 + 231 > X32 + X42 + X51 + X52 > 15.90 1 1 (4) -- 12 - aX22 - 32 - X:51 X:42 X52 -1 (5) 2X13 + 221 + z22 + x32 + 245 3 1 (6) + x13 + 251 > 1 xij E {0,1} for all i = 1,2,...,5 and j = 1,2,..., N. Ni = [4 3 2 3 2] 7

{*** column no. ***} ***** SAMPLE INPUT ***** 12345678901234567890123456789012345678901234567890 { **** comments **** } line no. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52.. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. GUBS ENDV NCON PCTG RHSV COEF 5 4 3 2 6 0.80 15.90 1.00 3 2 60.0 1.00 { the number of MC sets} { number of variables in each set} { number of general constraints} { var. elim. cutoff, upper bound } { necessary keyword } { general constraints righthand side vector} ( keyword } 1.00 -1.00 1.00 1 1 1 1 2 2 2 3 3 4 4 4 5 5 0 1 1 2 2 3 0 3 4 5 5 0 1 2 3 4 5 5 0 1 2 2 3 4 0 1 3 5 0 COST 1 1 1 1 2 2 2 3 3 4 4 4 5 5 1 2.900 2 2.500 3 1.000 4 3.300 1 4.200 2 1.000 3 3.200 1 4.100 2 1.500 1 3.000 2 2.700 3 5.300 1 3.200 2 2.600 1 1.000 3 1.000 1 1.000 2 1.000 1 1.000 2 1.000 2 1.000 1 1.000 2 1.000 { these are the general constraint non-zero coefficients, they MUST be in increasing MC set order, then by increasing index } { a zero separates constraints } 2 2 2 2 1 2 -1.000 -1.000 -1.000 -1.000 -1.000 -1.000 3 2.000 1 1.000 2 1.000 2 1.000 3 2.000 1 1.000 1 1.000 1 1.000 { necessary keyword } 1 26.000 2 -12.600 3 10.700 4 3.800 1 7.000 2 0.300 3 4.200 1 4.400 2 6.400 1 11.900 2 -4.700 3 8.800 1 14.500 2 11.200 { non-zero objective coefficients } (last line}

***** SAMPLE OUTPUT ***** line no. 1. M= 5 2. END: 4 3 2 3 2 3. NCON= 6 4. PCTGE=0.8000 5. 60. 6. BO: -15.90 -1.00 7. BO: -1.00 8. COSTBD= 196.20 9. THE FOLLOWING OUTPUT 10. PROBJ= 32.40 11. DELTA= 129.60 12. NVAR= 14 {**** comments ****} { number of MC (GUB) sets ) { number of variables in each set } { number of general constraints } { variable elimination cutoff } { input upper bound } ( negative of RHS vector { ignore ) -1.00 1.00 -1.00 IS PRODUCED BY VARRED { variable elim. output } { LP relax objective value } { max allowable difference in a MC set's costs } { no. of variables after variable elim. } 13. 14. 15. 16. 17. 18. 19. THE FOLLOWING OUTPUT IS PRODUCED BY OUT NITR= 0 ITCNT= 14 CX= 35.70 Z= 32.40 RATIO= 0.0924 LOC VECTOR FROM SUBROUTINE OUT: 4 3 1 { new incumbent output } { cum. total no. of BB nodes } { cum. total no. of LP iterations ) { value of solution w/ original costs } { value of solution w/ altered costs } { computed as (CX-lower bound)/CX ) 3 1 { incumbent solution vector } 20. 21. 22. 23. 24. 25. 26. 27. 28. THE FOLLOWING OUTPUT IS PRODUCED BY BOUND CX= 35.70 Z= 32.40 PROBJ= 32.40 ERROR=0.0924 NITR= 0 ITCNT= 14 LOC VECTOR: 4 3 1 3 1 END OF BOUND OUTPUT { final solution output } { value of solution w/ original costs } { value of solution w/ altered costs } { LP relax objective value } { bound on difference from optimal } { cum. total no. of BB nodes } { cum. total no. of LP iterations } { final solution vector }

REFERENCES Technical J.C. Bean, "A Lagrangian Algorithm for the Multiple Choice Integer Program," Operations Research, Vol. 32, 1984, pp. 1185-1193. J.C. Bean, "A Branch and Bound Algorithm for the Multiple Choice Integer Program," Department of Industrial and Operations Engineering, The University of Michigan, Technical Report 82-1, February 1982. J.C. Bean, "A Lagrangian Algorithm for the Multiple Choice Integer Program," Department of Industrial and Operations Engineering, The University of Michigan, Technical Report 82-14, September 1982. J.C. Bean, "An Additive Algorithm for the Multiple Choice Integer Program," Ph.D. Dissertation, Stanford University, October 1980. Applications J.C. Bean and M. Bean, "An Integer Programming Approach to Reference Staff Scheduling," Information Processing and Management, Vol. 21, 1985, pp. 459-464. J.C. Bean, J.R. Birge, J. Mittenthal and C.E. Noon, "An Adaptive Approach to Real Time Scheduling," Department of Industrial and Operations Engineering, The University of Michigan, Technical Report 84-18, October 1984. J.C. Bean, J.R. Birge, J.Mittenthal and C.E. Noon, "Match-Up Scheduling with Multiple Resources, Release Dates and Disruptions," Department of Industrial and Operations Engineering, The University of Michigan, Technical Report 86-37, September 1986. J.C. Bean, C.E. Noon and G.J. Salton, "Asset Divestiture at Homart Development Company," to appear in Interfaces. 8