generate a constrained latin square

[Sam28041977]

Dear Everybody,

I want to create a 5x8 matrix with random integer numbers with a large number of constraints.

I want something like a latin square respecting a some constraints.

One of the possible candidates is:

                      Area1  Area2  Area3 Area4  Area5  Area6  Area7 Area8

  Subject 1          1         2           3             4          5        6             7         8

  Subject 2          1         3           2             5          4        7             8         6

  Subject 3          1         4           5             3          2        8             6         7

  Subject 4          5         1           4             2          6        3             7         8

  Subject 5          2         1           3             4          7        5             8         6

Let Nij be the number of time that the number i=1 appears in the area j=1

The constraints are:

1. 2<=n11<=3
2. 2<=n12<=3
3. 1<=n23<=2, 1<=n24 <=2, 0<=n21 <=1, 0<=n22 <=1, 0<=n25 <=1,0<=n26 <=1
4. 1<=n33<=2, 1<=n34 <=2, 0<=n31 <=1, 0<=n32 <=1, 0<=n35 <=1,0<=n36 <=1
5. 1<=n43<=2, 1<=n44 <=2, 0<=n41 <=1, 0<=n42 <=1, 0<=n45 <=1,0<=n46 <=1
6. 1<=n53 <=2,1<=n54 <=2, 0<=n51 <=1, 0<=n52 <=1, 0<=n55 <=1, 0<=n56<=1
7. 0<=n65<=1, 0<=n66 <=1, 0<=n75 <=1, 0<=n76 <=1, 0<=n85<=1,  0<=n86 <=1
8. 1<=n67<=2, 1<=n68 <=2, 1<=n77 <=2, 1<=n78 <=2, 1<=n87 <=2, 1<=n88 <=2
9. n13=n14= n15= n16= n17= n18=0
10. n27=n28= n37 = n38= n47 = n48= n57 = n58=0
11. n61= n62= n63= n64= 0
12. n71= n72= n73= n74= 0
13. n81= n82= n83= n84= 0

I am looking for more than one solution.

The solution will allow me getting a partial balance according to my maximum number of subjects of 5.

I tried one solution but it is unacceptable time consuming approach:

1- generate a high number of latin square

2- Use the proc surveyselect to extract blocks of eight subjects respecting all the constraints

The number of possibilities are very high and the probability to get a block of subjects respecting all the conditions is very low.

Thanks in advance for all the help you can provide me.

Samir

[Rick_SAS]

Is there a context for this problem? For example, this seems to have some features that are similar to constructing a Williams design for randomized assignment of patients in crossover clinical trials.

Have you considered posing this as a linear programming problem?  SAS/IML has the LP subroutine (or use SAS/OR software, if you have that licensed). 

If someone told me to solve this problem, the first thing I'd do is cut the size in half. For example, I'd try to solve the problem with 2 subjects and 3 or 4 areas.  I would have an easier time explaining the problem to others, and I would expect to learn lots of useful information by solving the simplified problem.

[Sam28041977]

Dear Dr Wicklin,

Thanks a lot for your quick answer.

You right, the design looks like a cross-over design.

Ttreatment comparisons are done within subject.

The period factor is substituted by an area factor.

The difference in this design, is that my constraints are not only balance constrainsts. I have external constraints that make for example that treatment 1 should be tested only on area 1 or 2.

I think that SAS/IML is the most adequate way

I have a sas IML licence but no SAS/OR licence.

I will try to learn more about the LP subroutine.

It will be great if you can tell me more about the solution you suggest me.

Many thanks.

[Sam28041977]

I want just add one precision.

I am looking for partial balance over my block of five subjects.

I don't know if we can get this balance by cutting the size of the matrix in half.

Brs

[Rick_SAS]

I can't suggest anything else because I don't understand the question. It is too complicated. However, others on this forum know more about experimental designs/Latin Squares and might have additional ideas.

[IanWakeling · Accepted solution]

I think I can see what Samir would like, so I may be able to help.  There are a lot of constraints for a relatively small problem, so one approach would be to enumerate all possible solutions that meet the constraints and then pick from them at random. I think this is feasible, but it may involve less programming to implement an iterative improvement search algorithm to search for a single solution found at random.  I have created an algorithm that starts from a randomly chosen design (5 random permuations of 1 to 😎 and then seeks to swap samples within subject rows to improve the balance. The key to this is choosing a suitable criterion to optimize.  I have converted the constraints into the matrix t which puts the 8 samples in the rows, and the 8 areas in the columns, and the entries give the midpoint of the range of allowed frequencies permitted by your list of constraints.  So the entry of 1.5 in cell (2,3) indicates that sample 2 is allowed in area 3 either once or twice.  Any design can now be evaluated in the following way, first its sample x area frequency matrix is calculated (the module afreq does this), then the matrix t can be subtracted from it to form a difference matrix. If the design matches all the constraints, then the difference matrix will be zero wherever t contains a zero, and all other entries with contain the value -0.5 or +0.5.  As there are 38 non-zero entries in t, all constraints are matched when the sum of the squares of the difference matrix is 38 * 0.5 * 0.5 = 9.5.  Any design that does not match the constraints must have a sum of squares higher than this.

Using the above, it is then relatively simple to design a search algorithm that keeps going until an example design is found with a minimum criterion of 9.5.  My IML program is attached.

I have never tried using LP solutions for these types of design problem, so I would be interested to know how difficult or easy this might be.

[Sam28041977]

Dear Ian,

The way you formulated the problem is simply wonderfull!

I cannot thank you enough for the help you provide me.

The program output is exactly what I want.

Best regards,

Samir