Main file for solving ITC-2007 (Track 3)

main.cpp

#include <iostream>
#include <unordered_set>
#include "header/openGA.hpp"
#include "header/faculty.h"

using namespace std;

Faculty* faculty = nullptr;
vector<vector<bool>> room_occupancy;
vector<vector<bool>> course_period_assigned;
vector<vector<int>> curriculum_period_lectures;
vector<unordered_map<int, vector<int>>> curriculum_day_lectures; // curriculum_day_lectures[g][day] = list of periods where curriculum g has a lecture on that day
unordered_map<unsigned, unordered_set<unsigned>> course_assigned_days; // course_assigned_days[course_id] = set of days where course_id has lectures
unordered_map<unsigned, vector<int>> course_assigned_rooms; // course_assigned_rooms[course_id] = list of rooms where course_id has lectures

struct MySolution {
    vector<int> permutation;  // event IDs in scheduling order

    string to_string() const {
        ostringstream oss;
        for (int e : permutation) oss << e << ",";
        return oss.str();
    }
};

struct MyMiddleCost {
    int hard_violations = 0;
    int soft_penalty = 0;
};

struct EventAssignment {
    int course_id;
    int lecture_idx;
    int period;  // period index
    int room_id;   // room index
};

typedef EA::Genetic<MySolution, MyMiddleCost> GA_Type;
typedef EA::GenerationType<MySolution, MyMiddleCost> Generation_Type;

void init_genes(MySolution& p, const function<double(void)> &rnd01) {
    int total_events = 0;
    for (unsigned i = 0; i < faculty->Courses(); ++i) {
        total_events += faculty->CourseVector(i).Lectures();
    }
    p.permutation.resize(total_events);
    iota(p.permutation.begin(), p.permutation.end(), 0);
    shuffle(p.permutation.begin(), p.permutation.end(), mt19937(random_device{}()));
}

bool is_feasible(const EventAssignment& assignment) {
    unsigned course_id = assignment.course_id;
    unsigned period = assignment.period;
    unsigned room_id = assignment.room_id;

    // Check if room is occupied
    if (room_occupancy[period][room_id]) return false;

    // Check if course is already assigned in that period
    if (course_period_assigned[course_id][period]) return false;

    // Check for curriculum conflicts
    for (unsigned g = 0; g < faculty->Curricula(); ++g) {
        if (faculty->CurriculumMember(course_id, g)) {
            if (curriculum_period_lectures[g][period] > 0) return false;
        }
    }

    // Check course availability
    if (!faculty->Available(course_id, period)) return false;  

    return true;
}

vector<EventAssignment> decode_individual(const MySolution& p) {
    vector<EventAssignment> assignments;

    int total_courses = faculty->Courses();
    int total_periods = faculty->Periods();
    int total_rooms = faculty->Rooms();
    int total_curricula = faculty->Curricula();

    curriculum_day_lectures.clear();
    course_assigned_days.clear();
    course_assigned_rooms.clear();

    room_occupancy.assign(total_periods, vector<bool>(total_rooms, false));
    course_period_assigned.assign(total_courses, vector<bool>(total_periods, false));
    curriculum_period_lectures.assign(total_curricula, vector<int>(total_periods, 0));
    curriculum_day_lectures.resize(total_curricula);

    int cumulative = 0;
    for (int event_id : p.permutation) {
        int course_id = 0, lecture_idx = 0;
        cumulative = 0;
        for (unsigned i = 0; i < total_courses; ++i) {
            int n_lectures = faculty->CourseVector(i).Lectures();
            if (event_id < cumulative + n_lectures) {
                course_id = i;
                lecture_idx = event_id - cumulative;
                break;
            }
            cumulative += n_lectures;
        }
        
        bool assigned = false;
        for (int period = 0; period < total_periods && !assigned; ++period) {
            for (int room_id = 1; room_id <= total_rooms && !assigned; ++room_id) {
                EventAssignment assign = {course_id, lecture_idx, period, room_id};
                
                if (is_feasible(assign)) {
                    assignments.push_back(assign);

                    room_occupancy[period][room_id] = true;
                    course_period_assigned[course_id][period] = true;

                    int day = period / faculty->PeriodsPerDay();
                    course_assigned_days[course_id].insert(day);
                    course_assigned_rooms[course_id].push_back(room_id);

                    for (unsigned g = 0; g < total_curricula; ++g) {
                        if (faculty->CurriculumMember(course_id, g)) {
                            curriculum_period_lectures[g][period]++;
                            curriculum_day_lectures[g][day].push_back(period);
                        }
                    }

                    assigned = true;
                } 
            }
        }
    }

    return assignments;
}

int cal_soft_penalty(const EventAssignment&  assignment) {
    int pen = 0;

    int course_id = assignment.course_id;
    int period = assignment.period;
    int room_id = assignment.room_id;
    int day = period / faculty->PeriodsPerDay();

    // Soft: Room Capacity violation
    if (faculty->RoomVector(room_id).Capacity() < faculty->CourseVector(course_id).Students()) pen += 100;

    // Soft: Curriculum Compactness (prefer adjacent lectures in the same day)
    for (unsigned g = 0; g < faculty->Curricula(); ++g) {
        if (faculty->CurriculumMember(course_id, g)) {
            const auto& day_periods = curriculum_day_lectures[g][day];
            bool has_adjacent = false;
            for (int p : day_periods) {
                if (abs(p - period) == 1) {
                    has_adjacent = true;
                    break;
                }
            }
            if (!has_adjacent && !day_periods.empty()) pen += 50; 
        }
    }

    // Soft: Room Stability (prefer same room for the same course)
    if (!course_assigned_rooms[course_id].empty() && find(course_assigned_rooms[course_id].begin(), course_assigned_rooms[course_id].end(), room_id) == course_assigned_rooms[course_id].end()) pen += 20;

    // Soft: Minimum working days (prefer new day only if not yet used)
    if (!course_assigned_days[course_id].count(day)) pen += 10;

    return pen;
}

bool eval_solution(const MySolution& p, MyMiddleCost& c) {
    auto assignments = decode_individual(p);

    int hard_violations = 0, soft_penalty = 0;
    for (const auto& assign : assignments) {
        if (!is_feasible(assign)) {
            ++hard_violations;
        }
        soft_penalty += cal_soft_penalty(assign);
    }

    c.hard_violations = hard_violations;
    c.soft_penalty = soft_penalty;

    return hard_violations == 0;  // reject infeasible individuals
}

double calculate_SO_total_fitness(const GA_Type::thisChromosomeType &X) {
    // Combine penalties. Hard constraint violations are penalized heavily.
    return X.middle_costs.hard_violations * 10000 + X.middle_costs.soft_penalty;
}

MySolution crossover(const MySolution& p1, const MySolution& p2, const function<double(void)> &rnd01) {
    int n = p1.permutation.size();
    int cut1 = int(rnd01() * n);
    int cut2 = int(rnd01() * n);
    if (cut1 > cut2) swap(cut1, cut2);

    MySolution child;
    child.permutation.resize(n, -1);

    copy(p1.permutation.begin() + cut1, p1.permutation.begin() + cut2, child.permutation.begin() + cut1);

    int curr = cut2;
    for (int i = 0; i < n; ++i) {
        int val = p2.permutation[(cut2 + i) % n];
        if (find(child.permutation.begin(), child.permutation.end(), val) == child.permutation.end()) {
            child.permutation[curr % n] = val;
            ++curr;
        }
    }
    return child;
}

MySolution mutate(const MySolution& base, const function<double(void)> &rnd01, double) {
    MySolution mutated = base;
    int n = mutated.permutation.size();
    int i = int(rnd01() * n);
    int j = int(rnd01() * n);
    swap(mutated.permutation[i], mutated.permutation[j]);
    return mutated;
}

void SO_report_generation(int generation_number, const EA::GenerationType<MySolution,MyMiddleCost> &last_gen, const MySolution& best_genes) {
    ofstream outfile("output/my_sol00.out");
    if (!outfile) {
        cerr << "Failed to open output file.\n";
    }

    auto final_assignments = decode_individual(best_genes);
    for (const auto& a : final_assignments) {
        int day = a.period / faculty->PeriodsPerDay();
        int day_period = a.period % faculty->PeriodsPerDay();
        outfile << faculty->CourseVector(a.course_id).Name() << " " << faculty->RoomVector(a.room_id).Name() << " " << day << " " << day_period << "\n";
    }
    outfile.close();

    cout << "Generation " << generation_number << ": Best = " << last_gen.best_total_cost << endl;
}

int main(int argc, char* argv[]) {
    if (argc != 2) {
        cerr << "Usage: " << argv[0] << " <input_file>" << endl;
        return 1;
    }
    
    faculty = new Faculty(argv[1]);
    
    GA_Type ga;
    ga.problem_mode = EA::GA_MODE::SOGA;

    ga.population = 30;
    ga.generation_max = 100;
    ga.elite_count = 10;
    ga.crossover_fraction = 0.8;
    ga.mutation_rate = 0.1;

    ga.init_genes = init_genes;
    ga.eval_solution = eval_solution;
    ga.mutate = mutate;
    ga.crossover = crossover;
    ga.calculate_SO_total_fitness = calculate_SO_total_fitness;
    ga.SO_report_generation = SO_report_generation;
    
    ga.solve();

    delete faculty;

    return 0;
}