google-research

1
// Copyright 2023 The Authors.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15
#include "two_pass_algorithm_with_conditioned_matroid.h"
16

17
#include <algorithm>
18
#include <iostream>
19
#include <map>
20
#include <memory>
21
#include <string>
22
#include <utility>
23
#include <vector>
24

25
#include "better_greedy_algorithm.h"
26
#include "conditioned_matroid.h"
27
#include "fairness_constraint.h"
28
#include "matroid_intersection.h"
29
#include "uniform_matroid.h"
30
#include "utilities.h"
31

32
void TwoPassAlgorithmWithConditionedMatroid::Init(
33
    const SubmodularFunction& sub_func_f, const FairnessConstraint& fairness,
34
    const Matroid& matroid) {
35
  Algorithm::Init(sub_func_f, fairness, matroid);
36
  bounds_ = fairness.GetBounds();
37
  universe_elements_.clear();
38
}
39

40
void TwoPassAlgorithmWithConditionedMatroid::Insert(int element) {
41
  universe_elements_.push_back(element);
42
}
43

44
void TwoPassAlgorithmWithConditionedMatroid::GreedyFirstPass() {
45
  matroid_->Reset();
46
  fairness_->Reset();
47
  sub_func_f_->Reset();
48
  BetterGreedyAlgorithm greedy(true);
49
  greedy.Init(*sub_func_f_, *fairness_, *matroid_);
50
  for (const int element : universe_elements_) {
51
    greedy.Insert(element);
52
  }
53
  double solution_value = greedy.GetSolutionValue();
54
  std::cout << "Solution value after greedy first pass: " << solution_value <<
55
      std::endl;
56
  first_round_solution_ = greedy.GetSolutionVector();
57
}
58

59
void TwoPassAlgorithmWithConditionedMatroid::FirstPass() {
60
  per_color_solutions_ =
61
      std::vector<std::vector<int>>(bounds_.size(), std::vector<int>());
62
  std::vector<std::unique_ptr<Matroid>> per_color_matroids;
63
  matroid_->Reset();
64
  per_color_matroids.reserve(bounds_.size());
65
  for (int i = 0; i < bounds_.size(); i++) {
66
    per_color_matroids.push_back(matroid_->Clone());
67
  }
68
  for (const int element : universe_elements_) {
69
    int color = fairness_->GetColor(element);
70
    if (per_color_matroids[color]->CanAdd(element)) {
71
      // && per_color_solutions_[color].size() < bounds_[color].first) {
72
      per_color_matroids[color]->Add(element);
73
      per_color_solutions_[color].push_back(element);
74
    }
75
  }
76
}
77

78
void TwoPassAlgorithmWithConditionedMatroid::FindFeasibleSolution() {
79
  std::vector<int> all_colors_solution;
80
  for (const auto& solution : per_color_solutions_) {
81
    all_colors_solution.insert(all_colors_solution.end(), solution.begin(),
82
                               solution.end());
83
  }
84
  matroid_->Reset();
85
  fairness_->Reset();
86
  MaxIntersection(matroid_.get(), fairness_->LowerBoundsToMatroid().get(),
87
                  all_colors_solution);
88
  first_round_solution_ = matroid_->GetCurrent();
89
}
90

91
void TwoPassAlgorithmWithConditionedMatroid::DivideSolution() {
92
  lower_bound_solutions_.clear();
93
  lower_bound_solutions_.push_back(std::vector<int>());
94
  lower_bound_solutions_.push_back(std::vector<int>());
95
  std::vector<int> num_picked_per_color(bounds_.size(), 0);
96
  for (const auto& element : first_round_solution_) {
97
    lower_bound_solutions_
98
        [(num_picked_per_color[fairness_->GetColor(element)]++) % 2]
99
            .push_back(element);
100
  }
101
}
102

103
std::vector<int> TwoPassAlgorithmWithConditionedMatroid::SecondPass(
104
    std::vector<int> start_solution) {
105
  matroid_->Reset();
106
  fairness_->Reset();
107
  sub_func_f_->Reset();
108
  weights_.clear();
109

110
  ConditionedMatroid condmatroid(*matroid_, start_solution);
111

112
  std::unique_ptr<Matroid> color_mat = fairness_->UpperBoundsToMatroid();
113
  color_mat->Reset();
114
  SubMaxIntersection(&condmatroid, color_mat.get(), sub_func_f_.get(), {},
115
                     universe_elements_);
116

117
  std::vector<int> current_sol = color_mat->GetCurrent();
118
  std::vector<int> start_solution_not_chosen;
119
  for (int el : start_solution) {
120
    if (!color_mat->InCurrent(el)) {
121
      start_solution_not_chosen.push_back(el);
122
    }
123
  }
124

125
  // find the best subset of start_solution to add by
126
  // max {F(S U S_current) : S subset of S_start, S U S_current in I^C}.
127
  UniformMatroid dummy_mat(1'000'000'000);
128
  ConditionedMatroid cond_fairness(*color_mat, current_sol);
129
  // sub_func_f_ already has current sol.
130
  // dummy_mat has nothing.
131
  // cond_fairness also has nothing (it's reset when created).
132
  SubMaxIntersection(&dummy_mat, &cond_fairness, sub_func_f_.get(), {},
133
                     start_solution_not_chosen);
134

135
  return append(current_sol, cond_fairness.GetCurrent());
136
}
137

138
double TwoPassAlgorithmWithConditionedMatroid::GetSolutionValue() {
139
  GreedyFirstPass();
140
  std::pair<std::vector<int>, double> answer[2];
141
  for (int i = 0; i < 2; ++i) {
142
    answer[i].first = SecondPass(lower_bound_solutions_[i]);
143
    answer[i].second =
144
        sub_func_f_->ObjectiveAndIncreaseOracleCall(answer[i].first);
145
  }
146

147
  final_solution_ =
148
      answer[0].second > answer[1].second ? answer[0].first : answer[1].first;
149
  return std::max(answer[0].second, answer[1].second);
150
}
151

152
std::vector<int> TwoPassAlgorithmWithConditionedMatroid::GetSolutionVector() {
153
  return final_solution_;
154
}
155

156
std::string TwoPassAlgorithmWithConditionedMatroid::GetAlgorithmName() const {
157
  return "Two pass algorithm (with CM)";
158
}
159