Posts

Section 6 Problem 2 - Beautiful - Shipping Balls in a Box - Minimize the Surface Area (that's material)

Reduce it to 2D - it's circles inside a rectangle - now minimize the perimeter. A lovely problem. When you ship the balls, you pay for material - who cares about the volume - you want to minimize the area of the material only. In the 3D case, the height is set by the largest. What about the W and L? That nicely, naturally, reduces to the 2D case.. Intuitively, it's about maximizing area while minimizing perimeter. If the balls (there are three) aren't all touching each other and the edges, you're wasting space. I guess you could just set this up with variables (positions of the three circles) and parameters (circle sizes) and let the optimizer handle it. You just need constraints that keep any two circles' centers r1 + r2 apart. (They can touch, but not overlap)
1 comment
Read more

Section 6 - Eg 1 - Walkway of Fixed Width Given Finite Material - Intro to NLP

That is, there is a space of given dimensions. Now, build a walkway around it such that the space (linear) between the empty-space-edge and the walkway is constant and using only the available material to build the walkway. Sounds like something we might have done in differential calculus class ages ago. But, what makes this one different is that the Objective function involves w*l = meaning - it's non-linear. He's good at solving optimization problems, but a very poor (undisciplined) coder. Doesn't think twice about sprinkling magic constants throughout the code :( !pip install pyomo !wget -N -q "https://ampl.com/dl/open/ipopt/ipopt-linux64.zip" !unzip -o -q ipopt-linux64 Solver = SolverFactory( 'ipopt', executable = '/content/ipopt') OK, the code nails it easily, and that's when (checking the width thing), I realized that this one can be done on the back of an envelope.  And, then, I saw that it can't be - because he (they, maybe? Poler a...
Post a Comment
Read more

Section 5 Challenge Problem: Traveling Salesman

Winston and Goldberg 2004 Pg 532 You *have* to visit all cities (demand). What order will minimized the cost (total distance)? Solve it using integer programming. You're give the table of distances between cities. Set up the problem so you don't return to Ci immediately after leaving Ci. And also, a workaround for sub-tours - 3-4-3 (started from 3 and only visited 4) is not acceptable. 3-4-1-2-5-3 is acceptable (though may not be lowest cost). I didn't follow the lesson, but, this is probably so well known that, if you had to do it, you could just use chatGPT to knock it out..
Post a Comment
Read more

Section 5 Problem 2 - Minimizing Cost of the Production Plan, from Operations Research Problems: Statements and Solutions by Poler and Diaz-Madronero

Here, you are told how many you will be ABLE to sell (you can produce fewer than that number). No mention of profit. Keep the operation running at the lowest cost! Also uses cplex (why? go figure :) ('cplex_direct') (branch and bound methods) Mentions tee = true in .solve()
Post a Comment
Read more

Integer Programming (Section 5) Introduces a Nice (Big "em") Coding Trick

You have a decision variable that can take a range of natural number values - including 0.  It's the number of items you decide to produce. You want to maximize profit. The catch is, there a fixed cost associated with the decision to produce an item at all. If you make 0 of it and make that decision, then you don't rent the machinery for it. Else, add a fixed cost. How do you add this to your constraints and your objective (cost) function that you're trying to maximize? Z = whatever + sum( Fi * yi) And then, xi <= M*yi where M is just some large number - this introduces the coupling between x and y that you'd otherwise only get with an if statement.. Really? y is (0,1) whole - only two possible values. What you are trying to do is ensure the optimizer doesn't set y to 0 by introducing the coupling. Now, with a non-zero xi, yi has to be 1. Choosing Mi? Pick the largest value xi can attain - given the known parameter values. here, we starting using domain = pyo.Int...
Post a Comment
Read more

Solvers used

Image
GLPK solver: !apt-get install -y -qq glpk-utils CPLEX solver !pip install cplex -q IPOPT solver !wget -N -q "https://ampl.com/dl/open/ipopt/ipopt-linux64.zip" !unzip -o -q ipopt-linux64 COUENNE solver !wget -N -q "https://ampl.com/dl/open/couenne/couenne-linux64.zip" !unzip -o -q couenne-linux64 BONMIN solver !wget -N -q "https://ampl.com/dl/open/bonmin/bonmin-linux64.zip" !unzip -o -q bonmin-linux64  
Post a Comment
Read more

Challenge 1 - LP - Powerco (3 Plants, 4 Cities)

from Winston, Goldberg 2004, Pg 127. Nice one! There are three power-plants and four cities. Each city's demand MUST be met. There is a limit to how much each power-plant CAN supply. There are costs associated with supply to a certain city from a certain power-plant. Find out what the supply breakup should be. There is an elegant way and an inelegant way. Inelegant way - use Set only - which means you need to spell out C1, C2, etc.. in a dict. And then you  model.S1 = pyo.Var(model.i, within=pyo.NonNegativeReals) S1 = model.S1 model.S2 = pyo.Var(model.i, within=pyo.NonNegativeReals) S2 = model.S2 model.S3 = pyo.Var(model.i, within=pyo.NonNegativeReals) S3 = model.S3 # To view final solution: indices = list (model.i) for var in [model.S1, model.S2, model.S3]:     row = [ f " {pyo.value(var[i]) :.2f } " for i in indices]     print ( " " .join(row)) Elegant way: use RangeSet and then you specify the row and column variable names and maintain the weights (used ...
Post a Comment
Read more