python-3.xoptimizationor-toolsscipy-optimizemixed-integer-programming

How to solve a binary optimization problem with linear programming in ortools / cpmodel?


I'm trying to optimize a binary problem for a website of mine.

The data contains roughly 75 items and each of the items has a weight (between 50 and 1000) and a price attached to it. Here's a data snippet:

{"weighting":{
      "0":500,
      "1":50,
      "2":50,
      "3":50,
      "4":250,
      "5":1000
   },
   "price":{
      "0":4,
      "1":78,
      "2":75,
      "3":170,
      "4":5,
      "5":4
   }
}

I calculate the expected value of the whole data set with

exp_val = (w1 p1 + w2 p2 + ... + wn pn) / sum(w1 + w2 + ... wn)

with

sum(w1 + w2 + ... wn) = 23665 (considering all items)

So far so good, but now comes the tricky part. Not all items are desired, that is, they are worth less and / or have a high weighting which dilutes the pool I can draw from.

By "blocking" or removing up to 3 items I can draw from the remaining items only, and by doing so maximizing the expedted value function. The question is: Which items to remove? As the prices vary over time, I have to check the items to remove on a regular basis.

I have started by simply removing the items with the highest weights and the smallest price, but I'm sure this only represents a local optimum and there would be a more optimal strategy.

After checking some websites, it seems that Mixed-integer linear programming (MILP) or in particular BILP (binary ...) can solve my issue, and I found https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.milp.html but wasn't able to make it work, as I'm stuck translating my problem into code. Can anyone help me out?


Solution

  • Here's my solution:

    1. Make the results trackable

    In cpmodel from ortools you can do so by introducing a class with

    from ortools.sat.python import cp_model as cp 
    
    class VarArraySolutionPrinter(cp.CpSolverSolutionCallback):
    """Print intermediate solutions."""
    
    def __init__(self, variables):
        cp.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0
    
    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            print('%s=%i' % (v, self.Value(v)), end=' ')
        print()
    
    def solution_count(self):
        return self.__solution_count
    

    and than structure your code like this

    # ############################################
    # content of your objective function goes here
    # ############################################
    
    # solve the model
    solver = cp.CpSolver()
    status = solver.Solve(model)
    
    # https://developers.google.com/optimization/cp/cp_solver?hl=de
    # debugging
    solution_printer = VarArraySolutionPrinter([objective, xi_wi_pi, xi_wi])
    solver.parameters.enumerate_all_solutions = True
    
    # inspect the solution
    objective_function_value = solver.ObjectiveValue()
    solution_info = solver.SolutionInfo()
    status = solver.Solve(model, solution_printer)
    

    note that in

    solution_printer = VarArraySolutionPrinter([objective, xi_wi_pi, xi_wi])
    

    you want to add the variable names, i.e. using the third argument (str) when creating a variable:

    xi_wi = model.NewIntVar(0, 100, "xi_wi")
    

    2. Create the model

    With that out of the way I found that I didn't had to follow Jonis advice because cpmodel from ortool can handel binary variables itself. This code works for me:

    from ortools.sat.python import cp_model as cp
    
    # w_default = weighting
    # chaos = price
    data = {"w_default":{
      "0":500,
      "1":50,
      "2":50,
      "3":50,
      "4":250,
      "5":1000
    },
    "chaos":{
      "0":4,
      "1":78,
      "2":75,
      "3":170,
      "4":5,
      "5":4
       }
    }
    
    model = cp.CpModel()
    num_items = len(data["w_default"])
    
    # create boolean coefficients
    dv_select_items = {i: model.NewBoolVar("item_" + str(i)) for i in data["w_default"]}
    
    # constraint: remove exactly 3 items
    model.Add(sum(dv_select_items[i] for i in dv_select_items) == num_items - 3)
    
    # ##### numerator equation #####
    constant = 1000
    # x_i * w_i * p_i // sum of weightings * prices = 200.000 -> UB 500.000 to give some space?
    xi_wi_pi = model.NewIntVar(50000 * constant, 500000 * constant, "xi_wi_pi")
    model.Add(xi_wi_pi == sum(
        dv_select_items[i] * data["w_default"][i] * data["chaos"][i] * constant for i in dv_select_items))
    
    ##### denominator equation #####
    # xi_wi // sum of weightings 23665: 20665 with 3 blocked
    lb_weights = int(tot_weight * 0.75)
    xi_wi = model.NewIntVar(lb_weights, tot_weight, "xi_wi")
    model.Add(xi_wi == sum(dv_select_items[i] * data["w_default"][i] for i in dv_select_items))
    
    objective = model.NewIntVar(0, 100 * constant, "objective")
    model.AddDivisionEquality(objective, xi_wi_pi, xi_wi)
    
    # set target
    model.Maximize(objective)
    
    # solve the model
    solver = cp.CpSolver()
    status = solver.Solve(model)
    
    # https://developers.google.com/optimization/cp/cp_solver?hl=de
    # debugging
    solution_printer = VarArraySolutionPrinter([objective, xi_wi_pi, xi_wi])
    solver.parameters.enumerate_all_solutions = True
    
    # inspect the solution
    objective_function_value = solver.ObjectiveValue()
    solution_info = solver.SolutionInfo()
    status = solver.Solve(model, solution_printer)
    

    3. Scale the nominator because AddDivisionEquality round to integers

    You might be wondering why I have added a constant in the code (it doesn't work without it). This is because

    model.AddDivisionEquality(objective, xi_wi_pi, xi_wi)
    

    always rounds the result to an integer value and because the results are in the range of 8.something the objective function always returned 8. However, if you multiply the numerator with 1000, 8.3456 now becomes 8345 and 8.4334 becomes 8433 and thus can be evaluated correctly.

    Hope this helps anyone with a similar problem. Also, many thanks to Joni and Barthendu for pointing me in the right direction!