2D Bin Packing

[Anderson Faria]

Hello,

I've been trying for a couple days to create a 2d bin packing for educational purposes. I'm using Python 3 and OR-Tools for PY using the KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER method in solver.
I've tried to use many codes as example, including some I got here in the forum. I've searched everywhere for some guidance on this but couldn't proceed further.
My problem is that it treats each dimension as one restriction, this means when I insert several boxes into a 10x2 container it fits boxes until either sum of box.x complete the 10 restrction or box.y complete the 2 restriction.
ex:


In the above image you can see there's plenty room for inserting more boxes up but algorithm doesn't handle those cases.

I've seen some other examples using GLOP_LINEAR_PROGRAMMING instead:

from __future__ import print_function

import sys

from ortools.linear_solver import pywraplp

def main():

  solver = pywraplp.Solver('LinearExample',

                           pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

  

  # data

  capacity = [150, 150, 200, 400]

  value = [96, 76, 56, 11, 86, 10, 66, 86, 83, 12, 9, 81]

  nb_items = len(value)

  nb_resources = len(capacity)

  items = list(range(nb_items))

  resources = list(range(nb_resources))

  

  # Assign variable:

  assign={}

  for r in resources:

      assign[r] = [solver.IntVar(0, 1, 'Assign[%r][%d]' % (r, j)) for j in items]

  

  # objective: minimize number of trucks:

  z = solver.Sum((value[i] * assign[r][i]) for i in items for r in resources)

  

  ### constraints ###

  # Assign:

  for j in items:

      solver.Add(solver.Sum(assign[r][j] for r in resources)  == 1)

  for r in resources:

      solver.Add(solver.Sum(value[j] * assign[r][j] for j in items) <= capacity[r])

  ## Objective:

  objective = solver.Maximize(z)

  # solution and search

  solver.Solve()

  print('z: ', int(solver.Objective().Value()))

  print('walltime  :', solver.WallTime(), 'ms')

  print(assign)

if __name__ == '__main__':

  main()

but I don't think this is correct as well since he tries to minimize the number of trucks but use solver.maximize, and most importantly it does not assign items to trucks in a way to reduce the number of trucks.

I just need something very simple, 2d that allocate items, without rotating or anything like that, I'm following this instructions but I'm not sure how to insert such constraints in knapsack since examples differ too much. (in the above code the guy is just inserting constraints through solver.add but in the diet example we can see another form of declaration.

constraints = [0] * len(nutrients)

  for i in range(0, len(nutrients)):

    constraints[i] = solver.Constraint(nutrients[i][1], solver.infinity())

    for j in range(0, len(data)):

      constraints[i].SetCoefficient(food[j], data[j][i+3])

Also, knapsacks in just for 1 container right?


By the way, this is what I'm trying to achieve:

[Laurent Perron]

Please use the CP-SAT solver with the no_overlap_2d constraint.

The knapsack solver only implements what is called vector bin packing, that is it just sum capacities, it does not enforce any geometrical property.

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Anderson Faria]

Thanks Laurrent, I was already checking CP-SAT because I had this same thought that knapsack was too limited for what I'm trying to achieve.

I got the Python example and inserted the restriction, is this the correct way?

from __future__ import absolute_import
from __future__ import division
from __future__ import print_function


from ortools.sat.python import cp_model




# You need to subclass the cp_model.CpSolverSolutionCallback class.
class VarArrayAndObjectiveSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""


    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0


    def on_solution_callback(self):
        print('Solution %i' % self.__solution_count)
        print('  objective value = %i' % self.ObjectiveValue())
        for v in self.__variables:
            print('  %s = %i' % (v, self.Value(v)), end=' ')
        print()
        self.__solution_count += 1


    def solution_count(self):
        return self.__solution_count




def SolveAndPrintIntermediateSolutionsSampleSat():
    """Showcases printing intermediate solutions found during search."""
    # Creates the model.
    model = cp_model.CpModel()
    model.AddNoOverlap2D()


    # Creates the variables.
    num_vals = 3
    x = model.NewIntVar(0, num_vals - 1, 'x')
    y = model.NewIntVar(0, num_vals - 1, 'y')
    z = model.NewIntVar(0, num_vals - 1, 'z')


    # Creates the constraints.
    model.Add(x != y)


    model.Minimize(x + 2 * y + 3 * z)


    # Creates a solver and solves.
    solver = cp_model.CpSolver()
    solution_printer = VarArrayAndObjectiveSolutionPrinter([x, y, z])
    status = solver.SolveWithSolutionCallback(model, solution_printer)


    print('Status = %s' % solver.StatusName(status))
    print('Number of solutions found: %i' % solution_printer.solution_count())




SolveAndPrintIntermediateSolutionsSampleSat()

Also, how do I insert sums?

solver.Add(solver.Sum(assign[r][j] for r in resources)  == 1)

solver.Sum((value[i] * assign[r][i]) for i in items for r in resources)

Each example uses a different way to implement the same thing, it's really confusing :/

[Anderson Faria]

Please, I would gladly accept any example on how to insert sum in a constraint or objective function.

[Laurent Perron]

model.Add(sum(assign[r][j] for r in resources)  == 1)

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

Le mer. 27 mars 2019 à 22:40, Anderson Faria <anderson.b...@gmail.com> a écrit :

Please, I would gladly accept any example on how to insert sum in a constraint or objective function.

--