HomeTechniques and TipsEvolver and RISKOptimizerAdjustable Cell Matrix of Ones and Zeroes

14.11. Adjustable Cell Matrix of Ones and Zeroes

Applies to:
Evolver 5.x–7.x
RISKOptimizer in @RISK 5.x–7.x Industrial Edition

My adjustable cells are a square matrix of 200 rows and 200 columns. Each row must have one 1 and the rest 0, and the same for each column. (Perhaps each row represents an object and each column represents a recipient.) I could make each row a Budget group, and constrain the column totals to equal 1, but that still leaves me with 40,000 adjustable cells. Is there a better way?

Yes, you can reformulate this as a permutation problem. You have exactly one 1 in each row, so it's just a question of which column the 1 for that row gets placed in. You need only 200 adjustable cells, one per row of your existing matrix model. Each permutation of these values represents one solution that meets the constraints, and all possible permutations give all solutions that meet the constraints. Use the Order method for that group of 200 adjustable cells.

What's nice about this is that you don't have to specify any constraints. Just set the initial values of those 200 adjustable cells to 1, 2, 3, 4, ... 200. The Order method takes the starting values and rearranges them for every trial, so there will never be an invalid trial. Every trial will have one 1 per row and one 1 per column. It's much faster to generate only valid trials than to generate a lot of trials, test each one against constraints, and throw out the invalid trials. With this structure, both the OptQuest engine and the Genetic Algorithm will generate only valid trials. (OptQuest won't generate a given order more than once; the Genetic Algorithm may, because it uses backtracking.)

How do you interpret the optimum set of adjustable cells at the end of optimization? Suppose cell 55 contains the value 187. That means that object 55 is assigned to recipient 187, or in other words row 55 contains a 1 in column 187, and all the other cells in row 55 and column 187 are 0.

My problem is similar, but I have a rectangular matrix, not a square one. Can I use the Order method if I have 200 rows and 60 columns? Each row must still have only one 1, but each column can have multiple 1's.

You still have a number of adjustable cells equal to the number of rows, and each adjustable cell still contains the column number where that row's only 1 appears. But you can't use the Order method because you don't know in advance which columns will have multiple 1's in them.

Instead, use the Grouping method. Start with each of the 200 adjustable cells (one per row) containing a number from 1 to 60 (the number of columns). It doesn't matter how many of each number you have in the adjustable cells, but each number from 1 to 60 must occur at least once, and each adjustable cells must contain a number: no blanks or zeroes. During optimization, each trial will use only numbers 1 to 60, but in addition to the order the frequencies will vary. You'll interpret the final result the same way as above.

You don't need any explicit constraints with the Grouping method, because they're implicit in the method itself. But one option is important. If you check (tick) "All Groups Must Be Used", on the same screen where you select the Grouping method, then each number from 1 to 60 will occur at least once — every trial will have one or more 1's in each column.  If you don't select "All Groups Must Be Used", then each number 1 to 60 can occur any number of times, including none. If you have more complicated constraints — for example, rows 8 and 127 must be assigned to the same column — you may be able to use the Schedule method.

Last edited: 2015-07-23

This page was: Helpful | Not Helpful