# Minimizing total number of banners used in the cover buildings problem modelled

I was watching a video about Google OR-Tools where they were solving this cover building problem from Codility challenges using constraint programming.

In short, you have a list of building heights, e.g. [3, 1, 4] and want to cover them with no more than two banners, minimizing the total area.

Using the package, this is the model and solution:

def cover_buildings(buildings=None):
max_h = max(buildings)
max_w = len(buildings)

model = cp_model.CpModel()
banner1 = (model.NewIntVar(1, max_w, 'banner1_w'), model.NewIntVar(1, max_h, 'banner1_h'))
banner2 = (model.NewIntVar(0, max_w, 'banner2_w'), model.NewIntVar(0, max_h, 'banner2_h'))
banner1_area = model.NewIntVar(1, max_w * max_h, 'banner1_area')
banner2_area = model.NewIntVar(0, max_w * max_h, 'banner2_area')
# tie banner 2 width to banner 1 width

covered_by_banner1 = []
for x, height in enumerate(buildings):
c1 = model.NewBoolVar('building{}({})_covered_by_banner1'.format(x, height))
c2 = model.NewBoolVar('building{}({})_covered_by_banner2'.format(x, height))
covered_by_banner1.append(c1)
# this building has to be covered by one or the other, but not both
# if covered by banner 1
# if covered by banner 2 (offset by banner 1)

model.Minimize(banner1_area + banner2_area)

solver = cp_model.CpSolver()

if solver.Solve(model) == cp_model.OPTIMAL:
print 'Banner 1: {}x{}'.format(solver.Value(banner1), solver.Value(banner1))
print 'Banner 2: {}x{}'.format(solver.Value(banner2), solver.Value(banner2))
print 'Total area: {}'.format(solver.Value(banner1_area) + solver.Value(banner2_area))
for x, height in enumerate(buildings):
covered_by_1 = solver.Value(covered_by_banner1[x])
print 'Building {}({}) covered by banner {}.'.format(x, height, '1' if covered_by_1 else '2')
print '-' * 90


However, for the case of [7, 7, 3, 7, 7] the solution is using two banners: 1x7 and 4x7. Which is also optimal because the total area is 35, like the problem at Codility describes. However, I wonder how could I also minimize the total number of banners used?

Bonus: how could I generalize this problem to use N numbers of banners as the minimization objective instead of hardcoding 2?

• Just replace all XXX1 and XXX2 by a look from 1 to N. This is a coding issue, not an OR-Tools one as Dec 9, 2021 at 15:37
• I don't understand what you're suggestion I should change. Dec 9, 2021 at 16:29