Bin-packing problem: struggling to add constraint such that all items packed in bin MUST have same delivery destination

[blaffster]

As the title suggests, I am using OR-Tools to tackle a bin-packing problem. I would like to require that all orders packed into a given truck have the same delivery destination. The following is my attempt at implementing this, which doesn't seem to be working:

data['trucks'] = [0, 1, 2, 3, ...]
data['orders'] = [0, 1, 2, 3, ...]
data['delivery_county_id'] = [8, 8, 8, 1, 3, 2, ...]

from itertools import groupby

# Checks if all elements of list are equal
def all_equal(iterable):
    g = groupby(iterable)
    return next(g, True) and not next(g, False)

for j in data['trucks']:
    solver.Add( all_equal ( [ x[(i, j)] * data['delivery_county_id'][i] for i in data['orders'] if x[(i, j)] == 1 ] ) == True )

Strangely, I am not getting any errors when I execute the code, but my constraint is not being obeyed. I'm not sure why that is. Any assistance or suggestions would be profoundly appreciated!

[jmarca]

First, which solver. I assume CPSat.

From a quick look, my guess is that you are not doing what you think you are doing, with the call to all_equal returning next() and next().

I have very bad luck using clever constructs and iterators and the like from python when creating constraints. It is much safer in my opinion to be explicit.

Second, What is x[(i, j)]?

You can't really expect much meaningful help if you don't include a bit more from your program.

But I'll take a guess. If those are just python variables (as I suspect from the phrase if x[(i, j)] == 1), then you aren't really constraining anything. The constraints in the solver need to apply to variables created in solver-land, using calls like NewIntVar, etc.

And if those are IntVars, then you can't really call "==" in python-land and expect a meaningful result. The == operator in python land tests for equality outside of the context of the solver. What you want is to be testing for equality inside solver-land, not outside.

I think you should look at channeling constraints in the help, so that you can set up boolean variables (NewBoolVar type things) that map your notion of "these are equal" (true) or these are not equal (false) into solver-land, and then you can set up constraints that use those BoolVars as conditions.

But again I'm just guessing that this is your problem. Maybe I'm misreading.

[Mizux]

for 5. we means if x[(i, j)] == 1 is evaluated at the construction of the model when python interpreter "read" the line but at this time x[(i, j)] doesn't have its value (it.s just an IntVar object) which will be fixed once the solver has solved your problem aka chicken-egg problem.
and For inside/outside python land I guess jmarca want to talk about the python == operator (aka __eq__()) (i.e. in the python land )vs the solver.MakeEquality() object (in the CP-SAT solver land).

[blaffster]

Thank you for your response! I'm a little confused, though. Shouldn't the other constraints I've implemented run into the same problems? Those constraints use both x[(i, j)] and the <= operator, and they're all working fine. Why is the == operator different?

Also, just wondering if you have any thoughts on how you would tackle the problem?

Thank you :)

[Mizux]

long story: in other call site you are using it solver.Add( x[...] <= ... ) so actually x[...] <= ... will generate a LinearExpr object wich is then passed to the solver.Add() method as it, on the contrary in the previous message you used it in a if statement so this LinearExpr is implicitly converted to a boolean value (always true IIRC).

i.e. you can't write:

if LinearExpr(...) : ...

or

if x[...] <= ... : ...

since in both case it will be reduced to:

if True: ...

ps: you can look at

or-tools/ortools/sat/python/cp_model.py

Lines 405 to 444 in c1fe194

	def __eq__(self, arg):
	if arg is None:
	return False
	if cmh.is_integral(arg):
	arg = cmh.assert_is_int64(arg)
	return BoundedLinearExpression(self, [arg, arg])
	else:
	return BoundedLinearExpression(self - arg, [0, 0])
	def __ge__(self, arg):
	if cmh.is_integral(arg):
	arg = cmh.assert_is_int64(arg)
	return BoundedLinearExpression(self, [arg, INT_MAX])
	else:
	return BoundedLinearExpression(self - arg, [0, INT_MAX])
	def __le__(self, arg):
	if cmh.is_integral(arg):
	arg = cmh.assert_is_int64(arg)
	return BoundedLinearExpression(self, [INT_MIN, arg])
	else:
	return BoundedLinearExpression(self - arg, [INT_MIN, 0])
	def __lt__(self, arg):
	if cmh.is_integral(arg):
	arg = cmh.assert_is_int64(arg)
	if arg == INT_MIN:
	raise ArithmeticError('< INT_MIN is not supported')
	return BoundedLinearExpression(self, [INT_MIN, arg - 1])
	else:
	return BoundedLinearExpression(self - arg, [INT_MIN, -1])
	def __gt__(self, arg):
	if cmh.is_integral(arg):
	arg = cmh.assert_is_int64(arg)
	if arg == INT_MAX:
	raise ArithmeticError('> INT_MAX is not supported')
	return BoundedLinearExpression(self, [arg + 1, INT_MAX])
	else:
	return BoundedLinearExpression(self - arg, [1, INT_MAX])

for internal machinery

[jmarca]

That's why in my response I think about it as Python-land and Solver-land.

Inside the Solver's constructs (Solver.Add(), etc) the other solver constructs behave as expected (== and your IntVars), but in Python-land their Solver-land definitions lose their meaning.

[blaffster]

Thanks for all your response! The solution offered on Stack Overflow actually solves my problem perfectly!

[lperron]

I would recommend:

1. using CP-SAT
2. looking at https://github.com/google/or-tools/blob/stable/ortools/sat/docs/channeling.md for the first and the second example.

[blaffster]

Thanks for the response! I will definitely look into your above points, but am just wondering why my implementation isn't working. Could you possibly clarify for me why that is? And perhaps suggest how you would tackle the issue? I would be most grateful.

Thanks :)

[JustinOstrowsky]

This was a solution to a similar problem that was much discussed in the discord. They were trying to limit items in each bin to one port. No idea if it works.

Also see here. https://groups.google.com/g/or-tools-discuss/c/G1i4Ja4EMQk/m/f7c78WAXEwAJ
I am not sure I fully understand the question but this may help.

# z[p, b] = 1 if port p is in bin j.
z = {}
for p in set(data["ports"]):
    for b in data["bins"]:
        z[(p, b)] = solver.BoolVar(f"z[{p}, {b}]")

# Link z with the items in each bin;
for p in set(data["ports"]):
    for b in data["bins"]:
        solver.Add(
            z[p, b] * 1000000
            >= sum(x[i, b] for i in data["items"] if data["ports"][i] == p)
        )

# Constrain each bin where all items in that bin much have the same port.
for b in data["bins"]:
    solver.Add(sum(z[(p, b)] for p in set(data["ports"])) <= 1)

[blaffster]

Thanks for your response! The solution offered on Stack Overflow actually solves my problem perfectly!

[JustinOstrowsky]

Thanks for your response! The solution offered on Stack Overflow actually solves my problem perfectly!

are you able to share the relevant code?