# Category Archives: Constraint Programming

## Snapple Fact 804: How Many Ways to Make Change for a Dollar?

I went camping this past weekend (my first time) and my neighbor (who’s actually my neighbor in real life and was my neighbor at the camp site) was drinking a Snapple and read the following fact back to me:

Snapple Real Fact #804: There are 293 ways to make change for a dollar.

My first reaction was “Mmm…interesting”, but I couldn’t help wondering whether the Snapple folks did their math correctly. So after I got home and unpacked the car, I wrote a little Constraint Programming code in Comet to check this fact. It turns out that the number is indeed 293 if the following two things are allowed: (i) returning a 1-dollar coin in exchange for a dollar bill, and (ii) using half-dollar coins which, in my opinion, are rare these days. Here’s a list of the 292 ways that do not include using a 1-dollar coin which, in my opinion, isn’t really “giving change”.

If you’re wondering how many ways there are when you’re not allowed to use 1-dollar or half-dollar coins, the answer is 242. Here’s a list of all such possible ways.

Update: A friend asked me what the number would be if we considered the quarters from each of the 50 states as a different coin. In that case the number of possible ways increases to 515,184 (including the 1-dollar coin).

1 Comment

Filed under Constraint Programming, Modeling

## How Should Santa Pair Up His Reindeer?

It’s almost Christmas time and Santa is probably very busy with some last-minute preparations before his longer-than-7.5-million-kilometer trip around the world. One of the many things he has to worry about is how to pair up his reindeer in front of the sleigh. We all know that Rudolf goes right in front of everyone else because of his shiny nose, but what about his other eight four-legged friends? The traditional Christmas carols tell us that the reindeer are typically arranged in four pairs, front to back, as follows:

Dasher, Dancer

Prancer, Vixen

Comet, Cupid

Donner, Blitzen

Therefore, we are going to assume that this is an arrangement that works pretty well (after all it’s been working since 1823). As someone with a degree in a STEM field (he wouldn’t reveal which, though), Santa can’t stop thinking about this interesting question: “Are there other good ways to pair up my reindeer?” Before we can answer that question, we need to define what a “good” pairing of reindeer is. After working tirelessly on Christmas eve, Santa’s reindeer have all the other 364 days of the year to hang out and get to know each other. As in every group of friends who spend a lot of time together, some friendships become closer than others. So it’s reasonable to expect that Rudolf’s eight friends will have a favorite companion for side-by-side galloping, a second favorite, a third favorite, etc. In addition, there’s one more important detail when it comes to reindeer pairings, according to Mrs. Claus: some of them like to be on the left side (Dasher, Prancer, Comet, and Donner), while others prefer to ride on the right side in front of Santa’s sleigh (Dancer, Vixen, Cupid, and Blitzen). Before you mention that I should also consider that male reindeer would rather be side-by-side with female reindeer, there’s scientific evidence that all of Santa’s reindeer are female, so we don’t have to worry about that.

After a nice conversation in front of his cozy fireplace, Santa was kind enough to provide me with the following lists of pairing preferences for each of his reindeer; though he vehemently asked me not to show any of this to his furry friends. I’m counting on you, my readers, to keep these lists to yourselves! The names in each list are sorted in decreasing order of pairing preference. The lefties appear in blue, while the righties appear in red (any resemblance to US political parties is a mere coincidence):

Dasher: Dancer, Cupid, Vixen, Blitzen

Prancer: Vixen, Blitzen, Dancer, Cupid

Comet: Cupid, Dancer, Blitzen, Vixen

Donner: Blitzen, Vixen, Dancer, Cupid

Dancer: Prancer, Comet, Dasher, Donner

Vixen: Dasher, Donner, Prancer, Comet

Cupid: Prancer, Dasher, Comet, Donner

Blitzen: Comet, Prancer, Donner, Dasher

Note that if we were to adhere to the lefties’ first picks, we’d end up with the traditional line-up. We are now ready to define what a good pairing is: a pairing is good (a.k.a. stable) if no one has an incentive to change pairs. In other words, if A is paired up with B, and A prefers C to B, it so happens that C, who is paired up with D, prefers D to A. (Note: this problem is known in the literature as the stable marriage problem and it arises in real life, for example, in the context of the National Resident Matching Program, which pairs up medical residents with hospitals every year in the United States.) Obviously, the traditional pairing shown above satisfies these goodness/stability conditions, given the reindeer’s preferences.

What Santa would like to know is whether or not there are other good pairings in addition to the traditional one. If so, he can add some variety to his line-up and the reindeer won’t get so bored by galloping side-by-side with the same companion every year. How can we help Santa answer this question? Using Operations Research, of course! More precisely, Constraint Programming (CP).

Constraint Programming is a modeling and solution paradigm for feasibility and optimization problems that allows one to represent complicated requirements (such as the stability condition above) in ways that are often easier and simpler than using traditional O.R. techniques such as Integer Programming. For example, indexing variables with variables and expressing logical constraints such as implications are a piece of cake in CP. Here’s a CP model written in the Comet language (not to be confused with Comet the reindeer) that answers Santa’s question. It essentially enforces the stability condition for every choice of A, B, C, and D.

The good news is that, in 3 milliseconds, that CP model finds all of the five different stable pairings. Here they are:

Update (1/1/2012): Here’s an AIMMS version of the CP model, kindly created and provided by Chris Kuip. Look for this reindeer example, including an accompanying graphical user interface, in an upcoming update to the set of examples in AIMMS.

I hope Santa reads this blog post before Christmas eve, but in case he doesn’t, please tell him to check this out if you run into him this holiday season. I’m sure his reindeer would appreciate a little change after 189 years.

## The Joy of Baking (Optimally)

‘Tis the season of baking all kinds of things: cookies, cakes, breads, brownies, pies, and my favorite Brazilian dessert “pudim de leite moça“, which is depicted below. Click here for the step-by-step recipe.

Many OR bloggers, such as Laura McLay and Anna Nagurney, actually enjoy baking, and they both have written posts on the subject (e.g. here and here). I happen to include myself in this group and, yes, I made the pudim shown above (using  my mom’s recipe).

My goal today is to approach the art of baking from an optimization point of view. Let’s say you have a long list of items to bake. Perhaps you’re hosting a mega party at your house, or you’re helping your local church or favorite charity with their holiday cooking. You have an oven that can only fit so much at a time (think of area, or volume). Each item to be baked occupies some space in the oven and needs to bake for a specific amount of time. In what order should you bake your items so that you finish as soon as possible? (Side note: it may not be obvious at first sight, but this is the same problem faced by a container port that needs to decide the order in which to unload cargo ships.)

In the OR world, this is a job scheduling problem with a cumulative machine. The jobs are the tasks to be performed (items to bake), the machine (or resource) is the oven. We say the oven is cumulative, as opposed to disjunctive, because it can deal with (bake) multiple items at a time. The unknowns in this optimization problem are the start times of each job (when to begin baking each item). The objective is to minimize the makespan, which is defined as the finish time of the last job (the time at which it’s OK to turn off the oven). Finally, this is a non-preemptive problem because, typically, once you start baking something, it stays in the oven until it’s done.

This problem occurs so often in practice that the Constraint Programming (CP) community created a global constraint to represent it. It’s called the cumulative constraint (what a surprise!). Here’s a reference. For example, let’s say that we have a $10$-cubic-foot (cf) oven and we need to bake five items. The baking times (in minutes) are $20$, $25$, $40$, $30$, and $30$. The space requirements in cf are, respectively, $6$, $4$, $5$, $6$, $4$. If the time at which we begin baking item $i$ is denoted by the variable $s_i$, we can write the following in a CP model:

$\mathrm{cumulative}([s_1,s_2,s_3,s_4,s_5],[20,25,40,30,30],[6,4,5,6,4],10)$

The above constraint makes sure that the start times $s_i$ are such that the capacity of the oven is never exceeded. To minimize the makespan, we have to minimize the maximum among $s_1+6$, $s_2+4$, $s_3+5$, $s_4+6$, and $s_5+4$.

It’s easy to incorporate some real-life details into this model. For example:

• Not every item will be ready to go into the oven at time zero. After all, you’re making them as you go. To take care of this, add a ready-time $r_i$ (i.e. a lower bound) to the appropriate variable: $r_i \leq s_i$.
• If a given item does not occupy the entire oven, but you still prefer to bake it alone, just artificially increase its space requirement $c_i$ to be equal to the oven’s capacity $C$.
• If you’re baking both savory and sweet things, you probably don’t want to mix them up in the oven. In that case, simply solve the problem twice.
• If, for some reason, item $i$ must be finished before item $j$ starts baking (e.g. they need different temperatures), just include the constraint $s_i + p_i \leq s_j$, where $p_i$ is the baking time of item $i$.

We could, of course, have approached this problem from an Integer Programming point of view. In that case, we’d have binary variables $x_{it}$ that are equal to 1 if you start baking item $i$ at time $t$, and equal to zero otherwise. For more details on this formulation, including model files and some pretty tough instances, take a look at the CuSPLIB web page.

In the spirit of holiday baking, I will close with some pictures of past baking jobs ran on my house’s machine (a.k.a. oven). Enjoy! :-)

Key Lime Pie

Sparkling Ginger Chip Cookies (recipe here)

## Let’s Join O.R. Forces to Crack the 17×17 Challenge

I recently came across this post by bit-player, which refers to this post by William Gasarch, on a very interesting feasibility problem: given an $m \times n$ grid, assign one of $c$ colors to each position on the grid so that no rectangle ends up with the same color in all of its vertices (see the original post for applications of this problem). Many results are known for different values of $m$, $n$, and $c$, but the challenge (which comes with a reward of US\$289) is to decide whether a feasible solution exists when $m=n=17$ and $c = 4$.

Apparently, some attempts have been made to use Integer Programming (IP) to solve this problem:

SAT-solvers and IP-programs have been used but have not worked— however, I don’t think they were tried that seriously.

By writing this post, I hope to get enough O.R. people excited to brainstorm together in search of a solution. Given this is a feasibility problem, another method of choice here would be Constraint Programming (more on that later).

I decided to begin with the first IP formulation that came to mind. I didn’t expect it to close the deal, but I wanted to see how far it would take me. Here it is: let the binary variable $x_{ijt}$ equal 1 if the cell in row $i$ and column $j$ receives color $t$. There are two groups of constraints.

Every cell must have a color:

$\sum_{t=1}^c x_{ijt} = 1, \enspace \forall \; i,j$

Every rectangle can have at most 3 vertices with the same color:

$x_{ijt} + x_{i+a,jt} + x_{i,j+b,t} + x_{i+a,j+b,t} \leq 3, \enspace \forall \; i,j,a,b,t$

where

$1 \leq i \leq m-1$, $1 \leq j \leq n-1$, $1 \leq a \leq m-i$, and $1 \leq b \leq n-j$.

The objective function does not matter (in theory), but my limited experiments indicate that it’s better to minimize the sum of all $x_{ijt}$ than it is to maximize it. Gasarch also provides this diagram with a rectangle-free subset of size 74 for a 17 x 17 grid. I then added constraints of the form $x_{ij1}=1$ for every cell $(i,j)$ with an “R” in the diagram. This may be too restrictive, since it’s not clear to me whether a feasible solution to the 17 x 17 grid must contain that diagram as a subset. If that’s true, the latter constraints help with symmetry breaking and also substantially reduce the problem size. To reduce some of the color symmetry in the problem, I also arbitrarily chose cell (1,1) to contain color 2, i.e. $x_{112}=1$. Note that this still allows colors 3 and 4 to be swapped. I could have set $x_{123}=1$, but that would mean taking a risk.

Finally, for the 17 x 17 grid, it is suspected that each line and each row will have three colors used four times and one color used five times, hence, I also included the following constraints:

$4 \leq \sum_{j=1}^n x_{ijt} \leq 5, \enspace \forall \; i,t$

$4 \leq \sum_{i=1}^m x_{ijt} \leq 5, \enspace \forall \; j,t$

Once again, if my understanding is correct, there’s no formal proof that the above constraints are valid.

Here’s a ZIMPL model that can be used to  generate the .LP files and here’s the 17 x 17 LP. I set CPLEX’s MIP emphasis to 4 (look for hidden feasible solutions) and first ran a 14 x 14 as a warm-up. CPLEX 12.1 finds a feasible solution in under 5 seconds (I substituted 1 for 4 in the color usage constraints above). I stopped the 15 x 15 problem after 12 fruitless hours of search, so 14 x 14 is apparently the largest of the easy instances.

I started the 17 x 17 run last Thursday. The initial IP has 1156 variables and 74,620 constraints. Pre-processing reduces that to 642 variables and 15,775 constraints. After approximately 122 hours and 77,000 nodes on a dual-core machine (3.79 GHz), no solution was found.

Now it’s time for smarter ideas. Here are a few candidates:

1) Try a column-generation approach. It’s easy to find solutions for 8×8 and 9×9 grids, which will appear as sub-grids of a 17×17 solution. So it may be possible to write a set partitioning formulation (with side constraints) that has the 8×8 and 9×9 solutions as variables.

2) Try a meta-heuristic approach (e.g. simulated annealing). This problem is probably one of those for which an almost-feasible solution (like this one) can be very far from a feasible solution.

3) Try constraint programming. I think the main difficulty here will be finding a good variable and value selection heuristic. I started building a Comet model for the problem using the global constraint cardinality; here it is. It still does not include the constraints that fix the color of the rectangle free subset provided by Gasarch, but those are very easy to add (see the code that is commented out).

Let me know what your thoughts and hunches are!