![\"\"](\"https:\/\/www.danielpradilla.info\/blog\/wp-content\/uploads\/2017\/06\/grocery_bag_brown_bag.jpg\")
<\/p>\n<\/p>\n
<\/p>\n
Over the last couple of months I’ve been getting my feet wet with linear programming and mathematical optimisation. I got a sense of how it all worked from this Discrete Optimisation course in Coursera<\/a> and googling around I discovered that there are a ton of tools out there to help you solve optimisation problems. Makes sense, why would you want to implement a solving algorithm from scratch when some of the best minds in the history of mankind have already given it a shot?<\/p>\n Solvers, as these tools are often called, can reach the hundreds of thousands of dollars and they are worth every penny! But since I wanted to play with one without forking up the dough, I narrowed my search down to open-source options.<\/p>\n Hans Mittelmann from the Arizona State University performs regular automated benchmarks on different mathematical optimisation tools. He publishes the benchmarks at http:\/\/plato.asu.edu\/bench.html<\/a>. Following what I read in the results, I picked Google Optimization Tools (OR-Tools)<\/a> because it performed fairly well and well, because if you’re looking for a sinister tool to model and solve hard problems in the human world, you can rarely go wrong with Google.<\/p>\n GLOP has C++ and Python APIs. I’m better at Python and I expected to quickly put together a web front-end for this, so I picked the latter one.<\/p>\n You can get the full code here<\/a>.<\/p>\n <\/p>\n I picked a variation of the knapsack problem<\/a>: a grocery-shopping example in which you try to maximise the number of calories you can buy with a limited budget. I got the problem from this blog post:<\/p>\n http:\/\/www.jasq.org\/just-another-scala-quant\/new-agey-interviews-at-the-grocery-startup<\/a><\/p>\n Basically: You walk into a grocery store with a grocery bag and some cash, to buy groceries for a week. You need to follow these rules:<\/p>\n 1. Your bag can hold ten pounds. These are the groceries you can by and their price per pound:<\/p>\n <\/p>\n Follow the instructions at\u00a0https:\/\/developers.google.com\/optimization\/introduction\/installing<\/a>. You will need Python and Python setuptools<\/a> installed in your machine.<\/p>\n <\/p>\n We can split the coding of the problem into 6 elements:<\/p>\n We tell or-tools that we are attempting to solve a linear programming problem. We create a solver variable that is going to contain all the necessary items to solve the problem.<\/p>\n <\/p>\n We are going to send our table of possible groceries, calories and prices as a nested list:<\/p>\n <\/p>\n We need 5 decision variables which contain how many pounds of each product you are going to buy. Instead of creating 5 variables, we can create a list of size 5 (the size of the food list). Each item in the list will contain a decision variable.<\/p>\n Each decision variable will be created with a call to the NumVar method of the solver variable, passing the minimum amount of groceries we can buy, the maximum (infinity), and a unique name for the variable (contained in the previously-defined food list).<\/p>\n They pythonic<\/em> way of writing\u00a0that loop is using a list comprehension<\/a>. However I’m using the loop for readability.<\/p>\n <\/p>\n This is where most of the magic happens. We will create one constraint per “rule” specified in the problem description.<\/p>\n In linear programming each constraint is specified in terms of addition of the decision variables:<\/p>\n In the knapsack problem, the conversion is pretty straightforward. In some other cases, you have to re-think and re-model your problem in these terms.<\/p>\n We will create a list of 3 constraints, calling Constraint(lower bound, upper bound) for each one, and then walk the variables list and call SetCoefficient for each of the variables.<\/p>\n Note that the 4th rule of the problem, “You must purchase at least 4 ounces of each grocery item,” is already coded in the variables definition.<\/p>\n <\/p>\n Similar to the constraint definition, the goal function is specified in terms of addition of the decision variables:<\/p>\n If we wish to minimize cost, we walk our variable list, get the price from the food list, and set the objective.<\/p>\n Say we wanted to maximize calories intake. We would do the same, but taking the calories value from the food list, and setting a maximization goal<\/p>\n <\/p>\n After all these configuration steps, we just call the solve method against the solver variable and print out a solution if we find it.<\/p>\n <\/p>\n You can get the full code here<\/a>.<\/p>\n <\/p>\n We got a solution, but you need to know a little bit of python to run this program, change its inputs or read the solution. Wouldn’t it be nice to have some sort of user-friendly UI? This will be the subject of future posts.<\/p>\nTL;DR. Just gimme the code<\/h2>\n
The Problem<\/h2>\n
\n2. You have $100
\n3. You need about 2000 calories a day, so a weekly shopping trip is about 14,000 calories.
\n4. You must purchase at least 4 ounces of each grocery item.<\/p>\nHam: 650 cals,\u00a0 $4\r\nLettuce: 70 cals,\u00a0 $1.5\r\nCheese: 1670 cals,\u00a0 $5\r\nTuna: 830 cals,\u00a0$20\r\nBread: 1300 cals,\u00a0 $1.20<\/pre>\n
Installing OR-Tools<\/h2>\n
Coding the problem<\/h2>\n
1. Identify the problem<\/h3>\n
\r\nfrom ortools.linear_solver import pywraplp\r\nsolver = pywraplp.Solver('SolveSimpleSystem',pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)\r\n<\/pre>\n2. Ingest the input<\/h3>\n
\r\nfood = [['ham',650, 4],\r\n ['lettuce',70,1.5],\r\n ['cheese',1670,5],\r\n ['tuna',830,20],\r\n ['bread',1300,1.20]]\r\n<\/pre>\n
3. Configure the decision variables<\/h3>\n
\r\n #food is a list of groceries, calories and prices\r\n variable_list = [[]] * len(food)\r\n for i in range(0, len(food)):\r\n #you must buy at least minShop of each\r\n variable_list[i] = solver.NumVar(minShop, solver.infinity(), str(food[i][0]))\r\n<\/pre>\n
\r\n #same thing but with comprehension\r\n variable_list=[solver.NumVar(minShop, solver.infinity(), str(food[i][0])) for i in range(0, len(food))]\r\n<\/pre>\n
4. Configure the constraints<\/h3>\n
lower bound <= var1+var2+var3 <=upper bound<\/pre>\n
\r\n #Define the constraints \r\n constraint_list=[]\r\n #Constraint 1: totalWeight<maxWeight\r\n #ham + lettuce + cheese + tuna + bread <= maxWeight\r\n constraint_list.append(solver.Constraint(0, maxWeight))\r\n for i in range(0, len(food)):\r\n constraint_list[0].SetCoefficient(variable_list[i],1)\r\n\r\n #Constraint 2: totalPrice<=maxCost \r\n constraint_list.append(solver.Constraint(0, maxCost)) \r\n for i in range(0, len(food)): \r\n constraint_list[1].SetCoefficient(variable_list[i],food[i][2]) \r\n\r\n #Constraint 3: totalCalories>=minCals\r\n constraint_list.append(solver.Constraint(minCals, minCals + 100))\r\n for i in range(0, len(food)):\r\n constraint_list[2].SetCoefficient(variable_list[i],food[i][1])\r\n<\/pre>\n
5. Configure the objective function<\/h3>\n
goal = Maximize\/Minimize (var1+var2+var3)<\/pre>\n
\r\n for i in range(0, len(variable_list[)):\r\n objective.SetCoefficient(variable_list[i], food[i][2])\r\n objective.SetMinimization()\r\n<\/pre>\n
\r\n# Define our objective: maximizing calories\r\nfor i in range(0, len(food)):\r\n objective.SetCoefficient(variable_list[i], food[i][1])\r\nobjective.SetMaximization()\r\n<\/pre>\n
6. Solve!<\/h3>\n
\r\n result_status = solve(solver)\r\n\r\n if result_status == solver.OPTIMAL:\r\n print('Successful solve.')\r\n # The problem has an optimal solution.\r\n print(('Problem solved in %f milliseconds' % solver.wall_time()))\r\n # The objective value of the solution.\r\n print(('Optimal objective value = %f' % solver.Objective().Value()))\r\n # The value of each variable in the solution.\r\n var_sum=0\r\n for variable in variable_list:\r\n print(('%s = %f' % (variable.name(), variable.solution_value())))\r\n var_sum+=variable.solution_value()\r\n print(('Variable sum = %f' % var_sum));\r\n\r\n print('Advanced usage:')\r\n print(('Problem solved in %d iterations' % solver.iterations()))\r\n\r\n for variable in variable_list:\r\n print(('%s: reduced cost = %f' % (variable.name(), variable.reduced_cost())))\r\n \r\n activities = solver.ComputeConstraintActivities()\r\n for i, constraint in enumerate(constraint_list):\r\n print(('constraint %d: dual value = %f\\n'\r\n ' activity = %f' %\r\n (i, constraint.dual_value(), activities[constraint.index()])))\r\n\r\n elif result_status == solver.INFEASIBLE:\r\n print('No solution found.')\r\n elif result_status == solver.POSSIBLE_OVERFLOW:\r\n print('Some inputs are too large and may cause an integer overflow.')\r\n\r\n<\/pre>\nNext steps<\/h2>\n