<div class="notebook open-fullscreen"> <div class="nb-cell html" name="htm7"> <h1>CLPFD: Introduction to Solving Problems with Resource Constraints</h1> <small><em>Author: Paul Brown (<a href="https://twitter.com/PaulBrownMagic" target="_blank" title="Twitter">@paulbrownmagic</a>)</em></small> </div> <div class="nb-cell markdown" name="md1"> We'll consider **3** business cases of increasing complexity to demonstrate some useful applications of [`library(clpfd)`](http://eu.swi-prolog.org/pldoc/man?section=clpfd), with thanks to Markus Triska who developed the library. </div> <div class="nb-cell program" data-background="true" name="p3"> :- use_module(library(clpfd)). </div> <div class="nb-cell markdown" name="md4"> ## Scenario 1: Manufacturing Machine Parts We're producing two machine parts, A and B, each of which has to be processed on three machines: lathe, polisher and press. The times taken for each process, together with the maximum weekly number of hours the machines can be used for this work, is given below. </div> <div class="nb-cell html" name="htm1"> <style> .problem { margin-left: auto; margin-right: auto; } .problem, th, td { padding: 5px; } .problem { border: 1px #222 solid; } .bb { border-bottom: 2px #222 solid; } .problem th { text-align: center; } td { text-align: center; } .problem td { text-align: right; } </style> <table class="problem"> <colgroup> <col style="border-right: 1px black solid"> <col span="3"> <col style="border-left: 1px black solid"> </colgroup> <tbody><tr><th></th><th colspan="3">Time (hours) on</th><th></th></tr> <tr class="bb"><th>Part type</th><th>Lathe</th><th>Polisher</th><th>Press</th><th>Unit Profit</th> </tr><tr><td>A</td><td>0.1</td><td>0.2</td><td>0.4</td><td>$16</td></tr> <tr class="bb"><td>B</td><td>0.2</td><td>0.1</td><td>0.1</td><td>$25</td></tr> <tr><th>Available</th><td>160</td><td>120</td><td>150</td><td></td></tr> </tbody></table> </div> <div class="nb-cell markdown" name="md2"> We want to maximize our profit, given these constraints. The question then is how many of Part A and how many of Part B should we produce? We'll take this step-by-step to show how the description is transformed into a model and then code before being solved. ### Step 1: Write it in Mathematical *English* </div> <div class="nb-cell html" name="htm2"> <p> maximize <em>Profit of producing some number of A items and B items</em> </p> <p> subject to: </p><ul> <li><em>the number of Lathe hours ≤ 160</em></li> <li><em>the number of Polisher hours ≤ 120</em></li> <li><em>the number of Press hours ≤ 150</em></li> <li><em>can't produce negative quantities of A or B</em></li> </ul> <p></p> <h3>Step 2: Write it in Mathematical <strong>Notation</strong></h3> <pre>maximize z = 16a +25b (profit) subject to: 0.1a +0.2b ≤ 160 (lathe hours) 0.2a +0.1b ≤ 120 (polisher hours) 0.4a +0.1b ≤ 150 (press hours) a ≥ 0 (non-negative) b ≥ 0 (non-negative) </pre> <h3>Step 3: Convert to Code</h3> <p> This step should be relatively simple, but we threw a spanner into the works already. The CLP library we're using only works with integer values, and we've got some floats in our formulation. It's an easy fix though, we just multiply each constraint by 10: </p> <pre>maximize z = 16a +25b (profit) subject to: a +2b ≤ 1600 (lathe hours) 2a +b ≤ 1200 (polisher hours) 4a +b ≤ 1500 (press hours) a ≥ 0 (non-negative) b ≥ 0 (non-negative) </pre> <p> Now let's code it. First we'll put that straight into a query so you can see the constraints. Then we'll put it into a predicate to solve it and so it's easy to read. </p> </div> <div class="nb-cell query" name="q1"> Z #= 16*A + 25*B, A + 2*B #=< 1600, 2*A + B #=< 1200, 4*A + B #=< 1500, A #>= 0, B #>= 0. </div> <div class="nb-cell markdown" name="md3"> Running that query you'll see `A` is between 0 and 375, `B` is between 0 and 800, and `Z` is between 0 and 26000. That doesn't mean we can take the biggest of all those numbers and be done with it! Those are only some of the constraints, we now need to search the possible space for the solution with the maximum `Z`. We do this with the `labeling/2` predicate. The first argument is for options, most notable ones are `min/1`, `max/1`, to denote a variable to be minimized or maximized, but also `ff`, and `ffc`, with `leftmost` as the default that describe the strategy on the ordering of labeling the variables. The second argument to `labeling/2` is the variables, by default they are labeled from left to right, so use your intuition for sensible ordering. For this case I'll put A first as it has the smallest search space, I'll put Z last as it's value depends on A and B. For more on `labeling/2`, [check the docs](http://eu.swi-prolog.org/pldoc/man?section=clpfd-predicate-index). </div> <div class="nb-cell program" data-background="true" name="p4"> machine_parts_profit(A, B, Z) :- Z #= 16*A +25*B, % profit to maximize A +2*B #=< 1600, % lathe hours 2*A + B #=< 1200, % polisher hours 4*A + B #=< 1500, % press hours A #>= 0, % non-negative B #>= 0, % non-negative labeling([max(Z)], [A, B, Z]). </div> <div class="nb-cell query" data-chunk="5" data-tabled="true" name="q2"> time(once(machine_parts_profit(A, B, Profit))). </div> <div class="nb-cell markdown" name="md5"> So we should make 200 units of product A, 700 of product B, and a nice profit of £20,700. Not bad! The query is wrapped in a `time/1` predicate to encourage investigation. What happens when: - You put Z as the first variable to solve? (`labeling([maz(Z)], [Z, B, A])`) - You use `ff` or `ffc` in the labeling options? (`[max(Z), ff]`) - With different variable orderings? </div> <div class="nb-cell markdown" name="md6"> The query is also wrapped in a `once/1` predicate, this is to avoid the underlying query mechanism on SWISH from timing-out and throwing you back to this query when you're halfway down the page. If you remove `once/1`, you can also investigate if there are other optimal solutions, or near-optimal solutions. **But remember to stop the query when you're done!** I've set it to find an intial 5 solutions for you. --- *This investigation is rather important, in more complex queries this can be the difference between finding a solution or making a computer warm.* --- ## Scenario 2: Minimize Vitamin Spending We'll run through this one as a simple minimizing example, it also demonstrates reducing the search space via mathematical reduction and **we discover how to find essential missing upperbounds**. You've got 2 multi-vitamin products, neither of which supply your recommended daily allowance (we'll ignore over-dosing to our detriment). We want, each day, at least 50 units of vitamin 1, 100 of vitamin 2, 60 of vitamin 3 and 180 of vitamin 4. How should you mix the two multi-vitamins to achieve the desired RDA at the lowest cost? </div> <div class="nb-cell html" name="htm3"> <table class="problem"> <tbody><tr class="bb"><th></th><th>Product A</th><th>Product B</th></tr> <tr class="bb"><td>Cost</td><td>£3</td><td>£4</td></tr> <tr><td>Vitamin 1</td><td>5</td><td>25</td></tr> <tr><td>Vitamin 2</td><td>25</td><td>10</td></tr> <tr><td>Vitamin 3</td><td>10</td><td>10</td></tr> <tr class="bb"><td>Vitamin 4</td><td>30</td><td>36</td></tr> </tbody></table> <h3>Step 1: Mathematical <strong>English</strong></h3> <p> minimize <em>Cost of purchasing some number of A multi-vitamins and B multi-vitamins</em> </p> <p> subject to: </p><ul> <li><em>the amount of vitamin 1 ≥ 50</em></li> <li><em>the amount of vitamin 2 ≥ 100</em></li> <li><em>the amount of vitamin 3 ≥ 60</em></li> <li><em>the amount of vitamin 4 ≥ 180</em></li> <li><em>can't purchase negative quantities of A or B</em></li> </ul> <p></p> <h3>Step 2: Write it in Mathematical <strong>Notation</strong></h3> <pre>minimize z = 3a +4b (cost) subject to: 5a +25b ≥ 50 (vitamin 1) 25a +10b ≥ 100 (vitamin 2) 10a +10b ≥ 60 (vitamin 3) 30a +36b ≥ 180 (vitamin 4) a ≥ 0 (non-negative) b ≥ 0 (non-negative) </pre> <h3>Step 3: Convert to Code</h3> <p> When we're solving a CLP problem, we're searching a space. In this example it's easy to see common denominators across some of our constraints, so let's reduce that search space prior to turning it into code and feeding it to the solver. In <em>some</em> cases this extra effort will result in greater efficiency. </p> <pre>minimize z = 3a +4b (cost) subject to: a +5b ≥ 10 (vitamin 1) 5a +2b ≥ 20 (vitamin 2) a +b ≥ 6 (vitamin 3) 5a +6b ≥ 30 (vitamin 4) a ≥ 0 (non-negative) b ≥ 0 (non-negative) </pre> <p> We have a second <strong>big</strong> problem when converting to code. If we run this formulation, we'll get an "Arguments Insufficiently Instantiated" error because there's no upperbound on the values of a or b. For our solver to work we need to find some sensible upperbounds to place on these. </p> <hr> <em> You can try commenting out the relevant lines in the program below to see the error.</em> <hr> <p> So for product A, the most we could buy is if we bought no product B. We want the maximum number of A such that we get all of our RDAs, i.e. all constraints are satisfied: </p> <pre> A = max{50/5, 100/25, 60/10, 180/30} % This is RDA/'amount supplied' for each vitamin = max{10, 4, 6, 6} = 10 % i.e. We'd need to buy at least 10 for our RDA B = max{50/25, 100/10, 60/10, 180/36} = max{2, 10, 6, 5} = 10 </pre> <p> So we add these constraints to our code formulation: </p> <pre>minimize z = 3a +4b (cost) subject to: a +5b ≥ 10 (vitamin 1) 5a +2b ≥ 20 (vitamin 2) a +b ≥ 6 (vitamin 3) 5a +6b ≥ 30 (vitamin 4) a ≥ 0 (non-negative) b ≥ 0 (non-negative) a ≤ 10 (max-bound) b ≤ 10 (max-bound) </pre> </div> <div class="nb-cell program" data-background="true" name="p2"> multivitamin_cost(A, B, Z) :- Z #= 3*A +4*B, % cost A +5*B #>= 10, % vitamin 1 5*A +2*B #>= 20, % vitamin 2 A +B #>= 6, % vitamin 3 5*A +6*B #>= 30, % vitamin 4 A #>= 0, % non-negative B #>= 0, % non-negative A #=< 10, % max-bound B #=< 10, % max-bound labeling([min(Z)], [A, B, Z]). </div> <div class="nb-cell query" data-tabled="true" name="q3"> time(once(multivitamin_cost(A, B, Cost))). </div> <div class="nb-cell markdown" name="md7"> So we need to puchase 5 of A and 1 of B, which'll cost £19. Let's just hope they're both powders/liquids so we can mix them in a ratio of 5:1! --- ## Scenario 3: A Complex Biscuit Baker with Modelling Tricks In this scenario we'll go from an even more abstract story to **a model that will require the introduction of additional variables to solve**. Pat is a very popular biscuit baker who wants to maximize their profit. Their repertoire of biscuits includes: </div> <div class="nb-cell html" name="htm4"> <table class="problem"> <colgroup> <col style="border-right: 1px #222 solid"> <col style="border-right: 1px #222 solid"> </colgroup> <tbody><tr><th>Biscuit</th><th>Profit</th><th>Production time</th></tr> <tr class="bb"><td></td><td>(£/unit)</td><td>(hours/unit)</td></tr> <tr><td>Double Choc</td><td>10</td><td>1.0</td></tr> <tr><td>Choc-Chip</td><td>22</td><td>2.0</td></tr> <tr><td>Chocolate</td><td>35</td><td>3.7</td></tr> <tr><td>Ginger Snap</td><td>19</td><td>2.4</td></tr> <tr><td>Granola Snack</td><td>55</td><td>4.5</td></tr> <tr><td>Gingerbread Shapes</td><td>10</td><td>0.7</td></tr> <tr><td>Vanilla Whirl</td><td>115</td><td>9.5</td></tr> </tbody></table> </div> <div class="nb-cell markdown" name="md8"> Trouble is, if Pat decides to make the Double Choc cookies, there won't be enough chocolate to make either Choc-Chip or Chocolate cookies. Also, Ginger Snaps are so small that at least 10 need to be baked at a time so they don't hog the oven space. Furthermore, if Gingerbread Shapes are made that'll add an extra 80 hours to setup and reset the production line. Finally, if they make Vanilla Whirl's there's an additional cost of £2000 to get hold of that fresh, organic vanilla that those biscuits are so loved for. Pat, with staff, has 720 hours available in the coming week. ### Step 0-1: Simplify the Story Let's replace the names with variables and pull out the requirements. **Maximize**: Profit **Time Available**: 720 </div> <div class="nb-cell html" name="htm5"> <table> <colgroup> <col style="border-right: 1px #222 solid"> <col style="border-right: 1px #222 solid"> </colgroup> <tbody><tr><th>Biscuit</th><th>Profit</th><th>Production time</th></tr> <tr class="bb"><td></td><td>(£/unit)</td><td>(hours/unit)</td></tr> <tr><td>A</td><td>10</td><td>1.0</td></tr> <tr><td>B</td><td>22</td><td>2.0</td></tr> <tr><td>C</td><td>35</td><td>3.7</td></tr> <tr><td>D</td><td>19</td><td>2.4</td></tr> <tr><td>E</td><td>55</td><td>4.5</td></tr> <tr><td>F</td><td>10</td><td>0.7</td></tr> <tr><td>G</td><td>115</td><td>9.5</td></tr> </tbody></table> <p> <strong>Additional Requirements</strong> </p><ol> <li>If A produced then no B and C produced</li> <li>If D produced, at least 10 D</li> <li>If F produced, additional 80 hours, so available time is 720 - 80 = 640</li> <li>If G produced, additional fixed cost of £2000</li> </ol> <p></p> </div> <div class="nb-cell markdown" name="md9"> We've simplified this down to the point where we can start formulating this in mathematical notation. ### Step 2: Express in Mathematical Notation Let's ignore the additional requirements for the initial formulation, we can then tackle them one at a time. </div> <div class="nb-cell html" name="htm6"> <pre>maximize z = 10a +22b +35c +19d +55e +10f +115g subject to: a +2b +3.7c +2.4d +4.5e +0.7f +9.5g ≤ 720 (hours available) a ≥ 0 b ≥ 0 c ≥ 0 d ≥ 0 e ≥ 0 f ≥ 0 g ≥ 0 </pre> <p> First, let's get rid of those non-interger numbers through multiplying by 10: </p> <pre>maximize z = 10a +22b +35c +19d +55e +10f +115g subject to: 10a +20b +37c +24d +45e +7f +95g ≤ 7200 (hours available) a ≥ 0 b ≥ 0 c ≥ 0 d ≥ 0 e ≥ 0 f ≥ 0 g ≥ 0 </pre> <p> Now we can tackle those difficult modelling problems. </p> <h4>If G, additional cost of £2000</h4> <p> We need some way to know if G is being produced. We do this by introducing a variable such that: </p> <pre> ⎧ 1, if G produced DG = ⎨ ⎩ 0, otherwise </pre> <p> This will let us subtract <code>2000DG</code> from our objective function. We can define DG from the implication: </p> <pre> G > 0 → DG = 1 </pre> <p> Which we model as: </p> <pre> G ≤ MG x DG </pre> <p> Where MG is the maximum number of G possible to produce. We can obtain this number from the available hours constraint: <code>MG = ⌊720/9.5⌋ = 75</code>, hence: </p> <pre> G ≤ 75DG </pre> <p> This updates our model to: </p> <pre>maximize z = 10a +22b +35c +19d +55e +10f +115g -2000dg subject to: 10a +20b +37c +24d +45e +7f +95g ≤ 7200 (hours available) g ≤ 75dg (if g produced) a ≥ 0 b ≥ 0 c ≥ 0 d ≥ 0 e ≥ 0 f ≥ 0 g ≥ 0 dg ∈ {0, 1} </pre> <h4>If F, 80 hours used</h4> <p> Same idea as before, we'll introduce a <code>DF</code> variable, set to 0 or 1 to determine if F is being produced. In this case, the maximum number of F that can be produced with the available hours restriction is <code>⌊720/0.7⌋ = 1028</code>. We can then subtract <code>80DF</code> from our available hours constraint, remembering we've multiplied that all by 10. </p> <p> This updates our formulation to:</p> <pre>maximize z = 10a +22b +35c +19d +55e +10f +115g -2000dg subject to: 10a +20b +37c +24d +45e +7f +95g ≤ 7200 - 800df (hours available) f ≤ 1028df g ≤ 75dg a ≥ 0 b ≥ 0 c ≥ 0 d ≥ 0 e ≥ 0 f ≥ 0 g ≥ 0 df, dg ∈ {0, 1} </pre> <h4>If A, then no B and C</h4> <p> We're going to need a variable that determines if A is produced, we obtain this just like before. We can then use this to force the values of B and C to 0 if DA is 1. </p> <pre> ⎧ 1, if A produced DA = ⎨ ⎩ 0, otherwise A ≤ MA*DA B ≤ MB(1-DA) C ≤ MC(1-DC) MA = ⌊720/1⌋ = 720 MB = ⌊720/2⌋ = 360 MC = ⌊720/3.7⌋ = 194 A ≤ 720DA B ≤ 360(1-DA) C ≤ 194(1-DA) </pre> <p> We're using the little trick of <code>1-DA</code> to flip the value of DA from a 0 to a 1 or from a 1 to a 0. </p> <p> So if we make A, then DA will be 1, causing B and C to both be 0. If we don't make A, then DA can be 0, so B and C can also be anything up to their maximum possible quantities. </p> <p> This updates our formulation to: </p> <pre>maximize z = 10a +22b +35c +19d +55e +10f +115g -2000dg subject to: 10a +20b +37c +24d +45e +7f +95g ≤ 7200 - 800df (hours available) a ≤ 720da b ≤ 360(1-da) c ≤ 194(1-da) f ≤ 1028df g ≤ 75dg a ≥ 0 b ≥ 0 c ≥ 0 d ≥ 0 e ≥ 0 f ≥ 0 g ≥ 0 da, df, dg ∈ {0, 1} </pre> <h4>If D, at least 10 D</h4> <p> Saving the most complex till last. We start by introducing a <code>DD</code> variable that's 1 when D is produced and 0 otherwise. </p> <p> Previously we've combined this variable with the maximum produced to say <code>D ≤ MD*DD</code>, so if DD is 1, then D can be any number up to the maximum produced. </p> <p> Now we want to say, if it is produced, it must be above some minimum bound too. We can add this on thusly: <code> 10DD ≤ D ≤ MD*DD</code>. So we're saying if DD is 1, D is between 10 and its maximum. If DD is 0, then D is between 0 and 0, so its 0. </p> <p> Now all we need is the value of MD and we can add it into our formulation: </p> <pre>MD = ⌊720/2.4⌋ = 300 maximize z = 10a +22b +35c +19d +55e +10f +115g -2000dg subject to: 10a +20b +37c +24d +45e +7f +95g ≤ 7200 - 800df (hours available) a ≤ 720da b ≤ 360(1-da) c ≤ 194(1-da) d ≤ 300dd f ≤ 1028df g ≤ 75dg a ≥ 0 b ≥ 0 c ≥ 0 d ≥ 10dd (still non-negative if dd = 0) e ≥ 0 f ≥ 0 g ≥ 0 da, dd, df, dg ∈ {0, 1} </pre> </div> <div class="nb-cell markdown" name="md10"> ## Step 3: Code It </div> <div class="nb-cell program" data-background="true" name="p1"> baker_profit(A, B, C, D, E, F, G, Z) :- % Maximize Z Z #= 10*A +22*B +35*C +19*D +55*E +10*F +115*G -2000*DG, % Subject To 10*A +20*B +37*C +24*D +45*E +7*F +95*G #=< 7200 - 800*DF, % hours available A #=< 720*DA, B #=< 360*(1-DA), C #=< 194*(1-DA), D #=< 300*DD, F #=< 1028*DF, G #=< 75*DG, A #>= 0, B #>= 0, C #>= 0, D #>= 10*DD, % still non-negative if DD = 0 E #>= 0, F #>= 0, G #>= 0, DA in 0..1, DD in 0..1, DF in 0..1, DG in 0..1, labeling([max(Z), ff, bisect], [DA, DD, DF, DG, A, B, C, D, E, F, G, Z]). </div> <div class="nb-cell query" data-tabled="true" name="q4"> time(once(baker_profit(DoubleChoc, ChocChip, Chocolate, GingerSnap, GranolaSnack, GingerbreadShapes, VanillaWhirl, Profit))). </div> <div class="nb-cell markdown" name="md11"> That'll take a while to run, but the speed is much improved by using the `bisect` branching strategy (by about 100 seconds!). In the end, we find out that making Gingerbread Shapes is so profitable we might as well just do that. If you fancy an additional exercise, and lets face it, who wouldn't? May I suggest the additional restriction that at least 3 types of biscuit need to be made? You'll need a constraint that's something like: ``da + 2*(1-da) + dd + de + df + dg ≥ 3`` so you'll need to work out an additional `de` variable too. ## Conclusion I hope this has proven a useful introduction to using `library(clpfd)` for some typical purchasing/selling use cases that represent dealing with limited resources. The great thing with `library(clpfd)` is that the syntax is so closely related to the mathematical representation and it adds very little overhead. With `library(clpfd)` it's likely that you can read it and understand it if you're familiar with the mathematical notation, which can't be said for most other solvers. </div> </div>