Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

🔒 This topic is **solved** and **locked**.
Need further help from the community? Please
sign in and ask a **new** question.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

Posted 02-21-2014 09:17 AM
(1598 views)

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:

- 2<=n11<=3
- 2<=n12<=3
- 1<=n23<=2, 1<=n24 <=2, 0<=n21 <=1, 0<=n22 <=1, 0<=n25 <=1,0<=n26 <=1
- 1<=n33<=2, 1<=n34 <=2, 0<=n31 <=1, 0<=n32 <=1, 0<=n35 <=1,0<=n36 <=1
- 1<=n43<=2, 1<=n44 <=2, 0<=n41 <=1, 0<=n42 <=1, 0<=n45 <=1,0<=n46 <=1
- 1<=n53 <=2,1<=n54 <=2, 0<=n51 <=1, 0<=n52 <=1, 0<=n55 <=1, 0<=n56<=1
- 0<=n65<=1, 0<=n66 <=1, 0<=n75 <=1, 0<=n76 <=1, 0<=n85<=1, 0<=n86 <=1
- 1<=n67<=2, 1<=n68 <=2, 1<=n77 <=2, 1<=n78 <=2, 1<=n87 <=2, 1<=n88 <=2
- n13=n14= n15= n16= n17= n18=0
- n27=n28= n37 = n38= n47 = n48= n57 = n58=0
- n61= n62= n63= n64= 0
- n71= n72= n73= n74= 0
- 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

1 ACCEPTED SOLUTION

Accepted Solutions

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

6 REPLIES 6

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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.

- Mark as New
- Bookmark
- Subscribe
- Mute
- RSS Feed
- Permalink
- Report Inappropriate Content

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

**Don't miss out on SAS Innovate - Register now for the FREE Livestream!**

Can't make it to Vegas? No problem! Watch our general sessions LIVE or on-demand starting April 17th. Hear from SAS execs, best-selling author Adam Grant, Hot Ones host Sean Evans, top tech journalist Kara Swisher, AI expert Cassie Kozyrkov, and the mind-blowing dance crew iLuminate! Plus, get access to over 20 breakout sessions.

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.