main.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <sstream>
#include "gurobi_c++.h"

using namespace std;

vector<vector<int>> read_input_file(char *input_file_name, int &number_of_employees, int &min_employees_per_group,
                                    int &max_employees_per_group);

void print_edge_labels(vector<vector<int>> edge_labels);

int main(int argc, char *argv[]) {
    //
    // Read problem parameters
    //
    int number_of_employees = 0;
    int min_employees_per_group = 0;
    int max_employees_per_group = 0;
    vector<vector<int>> edge_labels = read_input_file(argv[1], number_of_employees, min_employees_per_group,
                                                      max_employees_per_group);
    int number_of_groups = stoi(argv[2]);


    //
    // Configure problem model
    //
    GRBEnv environment = GRBEnv();
    GRBModel model = GRBModel(environment);
    model.set(GRB_StringAttr_ModelName, "Problema de Formação de Equipes");
    model.set(GRB_IntAttr_ModelSense, GRB_MAXIMIZE);

    //
    // Variables and objective function
    //
    vector<vector<vector<GRBVar>>> are_employees_in_group(number_of_employees);

    for (int i = 0; i < number_of_employees; i++) {
        vector<vector<GRBVar>> is_employee_j_in_group(number_of_employees);
        are_employees_in_group[i] = is_employee_j_in_group;

        for (int j = 0; j < number_of_employees; j++) {
            vector<GRBVar> is_edge_in_group_k(number_of_groups);
            are_employees_in_group[i][j] = is_edge_in_group_k;

            for (int k = 0; k < number_of_groups; k++) {
                stringstream variable_name;
                variable_name << "X_" << i + 1 << "_" << j + 1 << "_" << k;
                are_employees_in_group[i][j][k] = model.addVar(0.0, 1.0, (edge_labels[i][j] - 1) / 2, GRB_BINARY,
                                                               variable_name.str());
            }
        }
    }


    model.update();


    //
    // Minimum and maximum number of employees per group
    //
    for (int k = 0; k < number_of_groups; k++) {
        GRBLinExpr employees_per_group;

        for (int i = 0; i < number_of_employees; i++) {
            employees_per_group += are_employees_in_group[i][i][k];
        }

        model.addConstr(employees_per_group >= min_employees_per_group);
        model.addConstr(employees_per_group <= max_employees_per_group);
    }


    //
    // Each employee must belong to exactly one group
    //
    for (int i = 0; i < number_of_employees; i++) {
        GRBLinExpr number_of_groups_per_employee;

        for (int k = 0; k < number_of_groups; k++) {
            number_of_groups_per_employee += are_employees_in_group[i][i][k];
        }

        model.addConstr(number_of_groups_per_employee == 1);
    }


    //
    // If an employee is in a group, its edge is also in the group
    //
    for (int i = 0; i < number_of_employees; i++) {
        for (int j = 0; j < number_of_employees; j++) {
            for (int k = 0; k < number_of_groups; k++) {
//                model.addConstr(are_employees_in_group[i][j][k] <=
//                                are_employees_in_group[i][i][k] + are_employees_in_group[j][j][k]);
//                model.addConstr(are_employees_in_group[i][j][k] >=
//                                are_employees_in_group[i][i][k]);
//                model.addConstr(are_employees_in_group[i][j][k] >=
//                                are_employees_in_group[j][j][k]);
                model.addConstr(are_employees_in_group[i][j][k] == are_employees_in_group[j][i][k]);
            }
        }
    }

    model.optimize();


    //
    // Solution
    //
    cout << endl << model.get(GRB_DoubleAttr_ObjVal) << endl;

    for (int i = 0; i < number_of_employees; i++) {
        for (int k = 0; k < number_of_groups; k++) {
            // If this is true, then vertex i is in group k
            if (are_employees_in_group[i][i][k].get(GRB_DoubleAttr_X) > 0.999) {
                cout << "v_" << i + 1 << " -> " << k << endl;
            }
        }
    }

    return 0;
}

vector<vector<int>> read_input_file(char *input_file_name, int &number_of_employees, int &min_employees_per_group,
                                    int &max_employees_per_group) {
    ifstream input_file(input_file_name);

    // Ignore header
    string ignored_line;
    getline(input_file, ignored_line);

    // Read parameters
    input_file >> number_of_employees;
    input_file >> min_employees_per_group;
    input_file >> max_employees_per_group;

    // Ignore blank line
    getline(input_file, ignored_line);

    // Read edge labels
    vector<vector<int>> edge_labels(number_of_employees);

    for (int i = 0; i < number_of_employees; i++) {
        vector<int> line(number_of_employees);
        edge_labels[i] = line;

        for (int j = 0; j < number_of_employees; j++) {
            input_file >> edge_labels[i][j];
        }
    }

    return edge_labels;
}

void print_edge_labels(vector<vector<int>> edge_labels) {
    for (int i = 0; i < edge_labels.size(); i++) {
        vector<int> line = edge_labels[i];

        for (int j = 0; j < line.size(); j++) {
            cout << setw(5) << line[j];
        }

        cout << endl;
    }
}