1
$\begingroup$

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
    model.Add(banner2[0] == max_w - banner1[0])
    model.AddMultiplicationEquality(banner1_area, banner1)
    model.AddMultiplicationEquality(banner2_area, banner2)

    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
        model.AddBoolXOr((c1, c2))
        # if covered by banner 1
        model.Add(x < banner1[0]).OnlyEnforceIf(c1)
        model.Add(height <= banner1[1]).OnlyEnforceIf(c1)
        # if covered by banner 2 (offset by banner 1)
        model.Add(x >= banner1[0]).OnlyEnforceIf(c2)
        model.Add(height <= banner2[1]).OnlyEnforceIf(c2)

    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[0]), solver.Value(banner1[1]))
        print 'Banner 2: {}x{}'.format(solver.Value(banner2[0]), solver.Value(banner2[1]))
        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?

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

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.