Set cover / Weighted Maximum Cover exact algorithm

    https://en.wikipedia.org/wiki/Maximum_coverage_problem

def setcover_ilp(candidate_sets_dict, items=None, set_weights=None, item_values=None, max_weight=None, verbose=False):
    """
    Set cover / Weighted Maximum Cover exact algorithm

    https://en.wikipedia.org/wiki/Maximum_coverage_problem
    """
    import utool as ut
    import pulp
    if items is None:
        items = ut.flatten(candidate_sets_dict.values())
    if set_weights is None:
        set_weights = {i: 1 for i in candidate_sets_dict.keys()}
    if item_values is None:
        item_values = {e: 1 for e in items}

    if max_weight is None:
        max_weight = sum(ut.take(set_weights, candidate_sets_dict.keys()))

    if False:
        # This is true set coer
        # Formulate integer program
        prob = pulp.LpProblem("Set Cover", pulp.LpMinimize)
        # Solution variable indicates if set it chosen or not
        set_indices = candidate_sets_dict.keys()
        x = pulp.LpVariable.dicts(name='x', indexs=set_indices,
                                  lowBound=0, upBound=1, cat=pulp.LpInteger)
        # minimize the number of sets
        prob.objective = sum(x[i] for i in set_indices)
        # subject to
        for e in items:
            # each element is covered
            containing_sets = [i for i in set_indices if e in candidate_sets_dict[i]]
            prob.add(sum(x[i] for i in containing_sets) >= 1)
        # Solve using with solver like CPLEX, GLPK, or SCIP.
        #pulp.CPLEX().solve(prob)
        pulp.PULP_CBC_CMD().solve(prob)
        # Read solution
        solution_keys = [i for i in set_indices if x[i].varValue]
        solution_cover = {i: candidate_sets_dict[i] for i in solution_keys}
        # Print summary
        if verbose:
            print(prob)
            print('OPT:')
            print('\n'.join(['    %s = %s' % (x[i].name, x[i].varValue) for i in set_indices]))
            print('solution_cover = %r' % (solution_cover,))
    else:
        prob = pulp.LpProblem("Maximum Cover", pulp.LpMaximize)
        # Solution variable indicates if set it chosen or not
        item_indicies = items
        set_indices = candidate_sets_dict.keys()
        x = pulp.LpVariable.dicts(name='x', indexs=set_indices,
                                  lowBound=0, upBound=1, cat=pulp.LpInteger)
        y = pulp.LpVariable.dicts(name='y', indexs=item_indicies,
                                  lowBound=0, upBound=1, cat=pulp.LpInteger)
        r = pulp.LpVariable.dicts(name='r', indexs=item_indicies)
        # maximize the value of the covered items
        primary_objective = sum(item_values[e] * y[e] for e in item_indicies)
        # minimize the number of sets used (make sure it does not influence the chosen primary objective)
        # This is only possible when values are non-negative
        # TODO: minimize redundency
        min_influence = min(item_values.values())
        secondary_weight = min_influence / (1.1 * len(set_indices))
        secondary_objective = (sum(-x[i] for i in set_indices)) * secondary_weight
        #
        prob.objective = primary_objective + secondary_objective
        # subject to
        # no more than the maximum weight
        prob.add(sum(x[i] * set_weights[i] for i in set_indices) <= max_weight)
        # If an item is chosen than at least one set containing it is chosen
        for e in item_indicies:
            containing_sets = [i for i in set_indices if e in candidate_sets_dict[i]]
            if len(containing_sets) > 0:
                prob.add(sum(x[i] for i in containing_sets) >= y[e])
                # record number of times each item is covered
                prob.add(sum(x[i] for i in containing_sets) == r[e])
        # Solve using with solver like CPLEX, GLPK, or SCIP.
        #pulp.CPLEX().solve(prob)
        pulp.PULP_CBC_CMD().solve(prob)
        # Read solution
        solution_keys = [i for i in set_indices if x[i].varValue]
        solution_cover = {i: candidate_sets_dict[i] for i in solution_keys}
        # Print summary
        if verbose:
            print(prob)
            print('OPT:')
            print('\n'.join(['    %s = %s' % (x[i].name, x[i].varValue) for i in set_indices]))
            print('\n'.join(['    %s = %s' % (y[i].name, y[i].varValue) for i in item_indicies]))
            print('solution_cover = %r' % (solution_cover,))
    return solution_cover