Tag Archives: education

September 21, 2015

dividing up a large class into discussion sections using integer programming

By Laura Albert

I am team teaching a freshman course on engineering grand challenges with five other instructors. Each of the six instructors teaches a “theme” (mine is about systems, critical infrastructure, and logistics) to a subgroup of students. We must partition the students into six themes twice, since we repeat our themes in the second half of the semester with another group of students (we call these modules). To facilitate the assignments, students can submit a rank ordering of their top four choices. I was asked to use optimization to make the pairings. I thought about manually making the matches, but I could see that it would be a lot of work to redo the matchings if someone wanted to make some changes later on. So I put together a quick optimization model to do the work for me.

Here are the constraints:

  • Theme class sizes must be between 21 and 24 students
  • Each student should get one of their top two choices (this is not guaranteed)
  • Every student needs to be assigned to a theme in each module
  • Every student needs to be assigned to different themes across the two modules
  • Two groups of students are in first year interest groups (FIGs) and should all be assigned to the same first theme, regardless of preferences. This is a hard-but-flexible constraint (is that a thing?). These students needed to be assigned to the same theme, but I could choose any theme for them.

I had about two days to make the assignments and possibly field some requests to change the assignments. Integer programming was appealing because it would allow me to quickly make changes to the assignments and do a “what if” analysis. I could quickly see that it was going to be impossible to fill some of the themes based on student preferences. Luckily, some students did not submit preferences, so I could use these students to “pad” the assignments while maintaining a good solution. The objective function captures the quality of the assignments based on student preferences, so I would always have a feasible solution. I assigned weights for each student-theme pair as the objective function coefficients. I assigned the first choice theme a weight of 8, the second choice theme a weight of 4, a third choice theme a weight of 2, and a fourth choice theme a weight of 1. I assigned all other student-theme pairs a weight of zero. The goal was to mostly assign students to first and second preferred choices, so I chose weights that would “encourage” this. After solving the model I could easily check to see how many students were assigned to one of their top two matches (we promise to do this, if its possible).

The FIGs was a bit tricky. This constraint made it hard to eyeball a good solution and motivated the use of integer programming. I wanted to be able to manually test out different theme assignments for the FIGs and possibly have the flexibility to change the assignments really quickly if one of the instructors did or did not want a FIG. I manually selected themes for the FIG students by fixing variables and then optimized the assignment of everyone else. I could have treated the FIG assignments as a decision instead of an input.

Here are the parameters:

  • N = 138 students
  • T = 6 themes
  • M = 2 modules
  • w_{nt}: preference weight for student n and theme t (either 0, 1, 2, 4, or 8).

Here are the binary decision variables:

  • x_{ntm}: 1 if student n is assigned to theme t in module m.

The integer programming model is as follows.

maximize \sum_{n,t,m} w_{nt} x_{ntm}

subject to

21 \le \sum_n x_{ntm} \le 24, t=1,...,T,\ m=1,2

x_{nt1} + x_{nt2} \le 1, n=1,...,N, t=1,...,T

\sum_t x_{ntm} = 1,\ i=1,...,N,\ m=1,2

x_{ntm} \in \{0,1\}, n=1,...,N,\ t=1,...,T,\ m=1,2

The objective function maximizes the value of the assignments. The first constraint sets class sizes between 21 and 24. The second constraint ensures that a student is not assigned to the same theme across both modules. The third constraint ensures that each student is assigned to one of the themes in both modules. I do not require the model to assign students to one of their top two choices, and therefore, a feasible solution is always easy to find. However, I checked afterward to see if students got what they wanted (according to my results, they did!). What isn’t in this model is fixed variables associated with FIG student assignments, but that is straightforward to change.

The model was easy to set up except for setting the weights w_{nt} based on student preferences. This information came from a survey we conducted on the course management system. Downloading the data in a spreadsheet did not give us a flat file, so it took some extra parsing to get the right data. We would have needed to parse the survey data even if we made the assignments manually, so this was unavoidable. I would have liked to ensure diversity in teams somehow, but I did not have the data for this. Next time.

All in all, this was fun, and I would recommend the use of integer programming. It took me longer to write this post than to set up and solve the integer program to assign students to themes 🙂

 

 

8 Comments   |  tags: , | posted in Uncategorized

October 24, 2013

my stochastic processes midterm: Wisconsin edition

By Laura Albert

Based on the curiosity over my cheese-related exam question on twitter, I have decided to post the midterm for my graduate level course on stochastic processes. My favorite questions are #1 and #2. I should note that #1 was inspired by actual leftover cheese that is packaged and sold at a discount at the Babock Dairy Store on campus (picture is below). If there is enough extra leftover cheese, it is poured into a bag, leading to cheese that has layers like an onion. It is apparently not cost-effective to repress the leftover cheese into a smooth brick of cheese. As someone who didn’t grow up wearing a foam cheese hat, I find that cheese production, quality control, and inventory is the right avenue for me to learn about cheese.

The Midterm

1. The dairy plant in Babcock Hall makes one batch of cheese six days per week. The amount of cheese (in pounds) left over after each batch is distributed according to an exponential distribution with parameter 1. Cheese production on each day is independent. The Babcock Dairy store will package and sell any leftover cheese in a batch (i.e., a day) that is more than 1 pound—a “cheese factory second.” Let Ei be the event that there is more than 1 pound of cheese available on day i, with i = 1, 2, 3, 4, 5, 6.

Therefore, Ei is a random variable:
Ei = 1 if there are cheese factory seconds for the type of cheese produced on day i and 0 otherwise (i.e., ignore how much cheese is leftover – we are instead interested in the binary outcome of whether cheese is leftover).

E = the total number of types of cheese factory seconds across the 6 day week.

a) Define E in terms of Ei.
b) What is the sample space for E?
c) What is the probability that there is at least a pound of leftover cheese on day 1?
d) What is the probability that four or more days in the week produce cheese factory seconds?

2. The Lightsaber Manufacturing Company (LMC) operates their manufacturing plant in a galaxy far, far away. They need to decide to how many lightsabers to stock for the next Jedi Convention, where they will sell lightsabers to Jedi apprentices. Due to the expense associated with interstellar travel, LMC will discard the unsold lightsabers after the convention. Lightsabers cost 413 galactic credits to produce and are sold for 795 galactic credits (the unit of currency in the Empire). If the demand for lightsabers follows an exponential distribution with an average of 75 lightsabers, how many lightsabers should the LMC bring to the Jedi Convention to maximize its profit?

3. A student has a hard time figuring out how to get started on homework for Stochastic Modeling Techniques. The student randomly selects one of 3 potential places to start a homework problem with equal probability. The first approach is not fruitful; the student will return to the starting point after 1 hour of work. The second approach will return the student to the starting point after 3 hours. The third will lead to the solution in 15 minutes (1/4 hour). The student is confused, so he/she always chooses from all 3 available approaches each time. What is the expected amount of time it takes this diligent student to solve the homework problem?

4. A mysterious illness called “badgerpox” has affected the local badger population near Madison. The exposure level (X) largely determines whether a badger contracts the disease (D). The probability distribution for the exposure level and the conditional probability of disease given the exposure level are given in the table below.

Exposure level (Xi) P(Xi) P(D | Xi)
10 0.7 0.001
100 0.15 0.005
1000 0.12 0.12
10000 0.03 0.78

Find:

(a) The conditional distribution P(Xi | D) for each value of Xi
(b) The probability that a badger contracts the disease P(D)
(c) The expected exposure level for badgers that have contracted the disease.

5. A student likes to come to ISyE 624 on time, which is possible as long as the student can travel from left to right in the diagram below. There are two paths to class; the student can pass through if and only if all components along its path are open. Due to construction, the probability that component i is open has probability pi, i = 1,2,3,4. Assume components are independent. If there is not a path to class, the student will arrive to class late, and the professor will be sad. What is the probability the student gets to class on time?

midterm1_prob1

6. The Wisconsin-Minnesota football rivalry dates back to 1890. The teams play once per year for the trophy of “Paul Bunyan’s Axe,” which replaced the first trophy (the “Slab of Bacon,” 1930-1943)*. The teams are unevenly matched, with Wisconsin winning 16 of the last 20 games. Let’s say that Wisconsin wins each game independently with probability 0.8. The teams play next on 11/23/13.

(a) What is the expected number of games/years until Wisconsin loses next?
(b) What is the expected number of games/years until Wisconsin loses 2 games in a row?
(c) What is the probability that it Wisconsin loses for the 3rd time in the 5th game in the series?

* I didn’t make that up!

20131024-104034.jpg

Leave a comment   |  tags: , , , | posted in Uncategorized

January 2, 2013

before MOOCs, there were MOTVCs

By Laura Albert

Massively open online courses (MOOCs) are a hot topic in higher ed. I was surprised to learn that massively open courses are not a recent trend. Over the holiday break, I learned about my family’s participation in the precursor to MOOCs: massively open TV courses (MOTVCs).

First, a little back story. Both of my grandparents met during college, where they were both economics majors at different universities. My grandfather is a member of the greatest generation: he took a break from college to serve in the Navy during World War II, and he and my grandmother married soon thereafter. My great-grandfather’s blessing on their marriage was conditional on my grandmother graduating from college. He wanted her to receive her B.S. degree and not just an M.R.S degree.

My grandparents had seven children, an amazing feat in itself. As a stay-at-home mother, my grandmother got the bug to go back to college and to eventually start a career. Going back to college was not an option at the time.

Starting in 1956, the (now) local PBS affiliate WTTW experimented with TV college courses for credit [Link]. My grandmother took part in the new form of education. She watched lectures on TV and took tests at a local university:

Working in conjunction with Chicago’s Board of Education in 1956, WTTW became the first station in the country to televise college courses for credit via its TV College. Chicago-area students were now able to enroll at one of the participating junior colleges and attend classes at home in front of their television sets. Having access to a full junior-college curriculum, within five years approximately 15,000 students had enrolled for credit. A decade later, TV College’s yearly report noted that 80,000 people had enrolled for credit with an overall viewership estimated at 10,000 per broadcast.

I found some differing information on another web site, that claims that the courses started in 1951 and “served” 200,000 students. My grandparents didn’t have a TV until 1952, so the 1956 date rings true. But perhaps there were precursors to the 1956 WTTW courses.

Eventually, my grandmother went back to college to finish her degree (in psychology, I think) in a traditional classroom setting. She became a grade school teacher.

MOOCs and MOTVCs were similar in that the courses were free and available to all, and they were sponsored by existing universities and junior colleges. MOTVCs could yield college credit, and MOOCs seem to be moving in that direction (although there is some debate about that). Currently, MOOCs give a certificate of completion, not college credit. I could not find out about how much taking an exam for a MOTVC cost, but it was likely the rate for a regular junior college course (cheap in 1956).

There are a few other differences. MOTVCs had a smaller course catalog (there were only so many stations in 1956, the pre-cable era), so it was not possible to earn an entire degree via TV. It may have been possible to get something like an Associates degree on TV over the course of a few years. Degrees may be possible in the future with MOOCs, although I think it is unlikely (different universities offer different courses, and they probably could not be cobbled together to yield a degree). And MOTVCs served only those in the Chicagoland area who were free during the day time (not high school students and others who worked during the day), so they did not scale in the same way as MOOCs and did not serve as diverse of an student body.

I haven’t seen anything on the lessons that MOTVCs could give us about how to price and “count” completed MOOC courses, but it seems like there are some important lessons there.

Do you know anyone who took a MOTVC?

6 Comments   |  tags: | posted in Uncategorized

September 13, 2011

science vs. swimsuit competitions

By Laura Albert

Last month, ABC aired a science and technology program on prime time. It was called FIRST — Science is Rock and Roll, and it was about robotics built by K12 kids. I don’t remember seeing another science special on a major network during prime time. It was a terrific coup for science education in the US. However, it only aired because will.i.am’s gumption: he bought the airtime from ABC to make the robotics special happen.

Contrast that with the events of last night. The Miss Universe beauty competition appeared on NBC in prime time. A rock star’s resourcefulness wasn’t even required for the beauty competition to air. Reliable sources tell me that there was a swimsuit competition (is it not the year 2011?)

One step forward and one step back. It reminds me of something I saw on twitter last year:

“40 years ago we risked it big to put a man on the moon. 10 years ago we added ‘Hot coffee’ disclaimers on coffee cups.”

 

4 Comments   |  tags: , , , | posted in Uncategorized