Group Seat Reservation Knapsack Problem (GSR-KP)

# Copyright (c) Hexaly. Permission is hereby granted to use, copy,
# and modify this code for applications developed with Hexaly.
import hexaly.optimizer
import sys

if len(sys.argv) < 2:
    print("Usage: python group_seat_reservation_kp.py inputFile [outputFile] [timeLimit]")
    sys.exit(1)

def read_integers(filename):
    with open(filename) as f:
        return [int(elem) for elem in f.read().split()]

with hexaly.optimizer.HexalyOptimizer() as optimizer:
    # Read instance data
    file_it = iter(read_integers(sys.argv[1]))

    nbRequests = int(next(file_it))
    nbStations = int(next(file_it))
    nbSeats = int(next(file_it))

    nbStationsRequest = [0] * nbRequests
    nbSeatsRequest = [0] * nbRequests
    firstStationRequest = [0] * nbRequests
    for i in range(nbRequests):
        nbStationsRequest[i] = int(next(file_it))
        nbSeatsRequest[i] = int(next(file_it))
        firstStationRequest[i] = int(next(file_it))
        int(next(file_it))  # skip value
        int(next(file_it))  # skip value

    # Requests that share at least one station
    sharingStation = [[] for _ in range(nbRequests)]
    for i in range(nbRequests):
        for j in range(i + 1, nbRequests):
            if (firstStationRequest[i] < firstStationRequest[j] + nbStationsRequest[j]
                    and firstStationRequest[i] + nbStationsRequest[i] > firstStationRequest[j]):
                sharingStation[i].append(j)

    # Declare the optimization model
    model = optimizer.model

    # OptionalInterval: requestSelected[i] represents the seats occupied by the reservation i
    requestSelected = [model.optional_interval(0, nbSeats) for _ in range(nbRequests)]

    # If request i is selected then we allocate the corresponding number of seats
    for i in range(nbRequests):
        model.constraint(
                model.iif(
                model.presence(requestSelected[i]),
                model.length(requestSelected[i]) == nbSeatsRequest[i],
                True))

    # If two requests overlap on any station segment, they must not use the same seats
    for i in range(nbRequests):
        for j in sharingStation[i]:
            model.constraint(model.iif(
                    model.and_(model.presence(requestSelected[i]),
                    model.presence(requestSelected[j])),
                    model.or_(requestSelected[j] < requestSelected[i],
                    requestSelected[i] < requestSelected[j]),
                    True))

    # Compute the utilization of the train
    utilization = model.sum([model.presence(requestSelected[i])
            * nbSeatsRequest[i]
            * nbStationsRequest[i]
            for i in range(nbRequests)])

    # Objective: Maximize the utilization of the train
    model.maximize(utilization)

    model.close()

    # Parameterize the optimizer
    if len(sys.argv) >= 4:
        optimizer.param.time_limit = int(sys.argv[3])
    else:
        optimizer.param.time_limit = 5

    # Stop the search if the upper threshold is reached
    optimizer.param.set_objective_threshold(0, nbSeats * nbStations)

    optimizer.solve()

    # Write the solution in a file using the following format:
    #  - 1st line: total utilization of the train
    #  - For each selected request: which seats are occupied
    if len(sys.argv) >= 3:
        with open(sys.argv[2], "w") as f:
            f.write("%d\n" % utilization.value)
            for i in range(nbRequests):
                seats = requestSelected[i].value
                if not seats.is_void():
                    f.write(str(i) + ": [" + str(seats.start())
                            + "..." + str(seats.end() - 1) + "]\n")

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>

using namespace hexaly;
using namespace std;

class GroupSeatReservationKP {
public:
    // Number of requests
    int nbRequests;
    // Number of stations
    int nbStations;
    // Number of seats
    int nbSeats;

    // Number of stations travelled in each request
    vector<int> nbStationsRequest;
    // Number of seats needed by each request
    vector<int> nbSeatsRequest;
    // First station of each request
    vector<int> firstStationRequest;

    // Requests that share at least one station
    vector<vector<int>> sharingStation;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;
    // Decision Variables: requestSelected[i] represents the seats occupied by the reservation i
    vector<HxExpression> requestSelected;

    // Objective
    HxExpression utilization;

    void readInstance(const string& fileName) {
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);
        infile.open(fileName.c_str());

        infile >> nbRequests;
        infile >> nbStations;
        infile >> nbSeats;

        nbStationsRequest.resize(nbRequests);
        nbSeatsRequest.resize(nbRequests);
        firstStationRequest.resize(nbRequests);

        for (int i = 0; i < nbRequests; i++) {
            infile >> nbStationsRequest[i];
            infile >> nbSeatsRequest[i];
            infile >> firstStationRequest[i];
            int skip;
            infile >> skip; // skip value
            infile >> skip; // skip value
        }

        // Requests that share at least one station
        sharingStation.resize(nbRequests);
        for (int i = 0; i < nbRequests; i++) {
            for (int j = i + 1; j < nbRequests; j++) {
                if (firstStationRequest[i] < firstStationRequest[j] + nbStationsRequest[j]
                    	&& firstStationRequest[i] + nbStationsRequest[i] > firstStationRequest[j]) {
                    sharingStation[i].push_back(j);
                }
            }
        }
    }

    void solve(int limit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // OptionalInterval: requestSelected[i] represents the seats occupied by the reservation i
        requestSelected.resize(nbRequests);
        for (int i = 0; i < nbRequests; i++) {
            requestSelected[i] = model.optionalIntervalVar(0, nbSeats);
        }

        // If request i is selected then we allocate the corresponding number of seats
        for (int i = 0; i < nbRequests; i++) {
            model.constraint(model.iif(model.presence(requestSelected[i]),
            		model.length(requestSelected[i]) == nbSeatsRequest[i],
                	true));
        }

        // If two requests overlap on any station segment, they must not use the same seats
        for (int i = 0; i < nbRequests; i++) {
            for (auto j : sharingStation[i]) {
                model.constraint(model.iif(model.presence(requestSelected[i])
                		&& model.presence(requestSelected[j]),
                		requestSelected[j] < requestSelected[i]
                		|| requestSelected[i] < requestSelected[j],
                		true));
            }
        }

        // Compute the utilization of the train
        utilization = model.sum();
        for (int i = 0; i < nbRequests; i++) {
            utilization.addOperand(model.presence(requestSelected[i]) * nbSeatsRequest[i]
            		* nbStationsRequest[i]);
        }

        // Maximize the utilization of the train
        model.maximize(utilization);

        model.close();

        // Parametrize the optimizer
        optimizer.getParam().setTimeLimit(limit);

        // Stop the search if the UPPER threshold is reached
        optimizer.getParam().setObjectiveThreshold(0, (hxint)(nbSeats * nbStations));

        optimizer.solve();
    }

    /* Write the solution in a file using the following format:
            - 1st line: total utilization of the train
            - For each selected request: which seats are occupied */
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());
        outfile << utilization.getValue() << "\n";
        for (int i = 0; i < nbRequests; i++) {
            HxInterval seats = requestSelected[i].getIntervalValue();
            if (!seats.isVoid()) {
                outfile << i << ": [" << seats.getStart() << "..." << seats.getEnd() - 1 << "]\n";
            }
        }
        outfile.close();
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: group_seat_reservation_kp inputFile [outputFile] [timeLimit]" << endl;
        return 1;
    }
    const char* instanceFile = argv[1];
    const char* solFile = argc > 2 ? argv[2] : NULL;
    const char* strTimeLimit = argc > 3 ? argv[3] : "5";

    try {
        GroupSeatReservationKP model;
        model.readInstance(instanceFile);
        model.solve(atoi(strTimeLimit));
        if (solFile != NULL)
            model.writeSolution(solFile);
        return 0;
    } catch (const exception &e) {
        cerr << "An error occurred: " << e.what() << endl;
        return 1;
    }
}

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
using System;
using System.Collections.Generic;
using System.IO;
using Hexaly.Optimizer;

public class GroupSeatReservationKP : IDisposable
{
    // Data from the problem
    private int nbRequests;
    private int nbStations;
    private int nbSeats;
    private int[] nbStationsRequest;
    private int[] nbSeatsRequest;
    private int[] firstStationRequest;
    private List<int>[] sharingStation;

    // Hexaly Optimizer
    private readonly HexalyOptimizer optimizer;

    // Decision variable: requestSelected[i] represents the seats occupied by the reservation i
    private HxExpression[] requestSelected;

    // Objective
    private HxExpression utilization;

    public GroupSeatReservationKP()
    {
        optimizer = new HexalyOptimizer();
    }

    public void Dispose()
    {
        if (optimizer != null)
            optimizer.Dispose();
    }

    /* Read instance data */
    public static string[] ReadNextLine(StreamReader input)
    {
        return input.ReadLine().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
    }

    private void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            nbRequests = int.Parse(input.ReadLine());
            string[] splitted = ReadNextLine(input);

            nbStations = int.Parse(splitted[0]);
            nbSeats = int.Parse(splitted[1]);

            nbStationsRequest = new int[nbRequests];
            nbSeatsRequest = new int[nbRequests];
            firstStationRequest = new int[nbRequests];
            for (int i = 0; i < nbRequests; i++)
            {
                splitted = ReadNextLine(input);
                nbStationsRequest[i] = int.Parse(splitted[0]);
                nbSeatsRequest[i] = int.Parse(splitted[1]);
                firstStationRequest[i] = int.Parse(splitted[2]);
            }

            // Requests that share at least one station
            sharingStation = new List<int>[nbRequests];
            for (int i = 0; i < nbRequests; i++)
            {
                sharingStation[i] = new List<int>();
                for (int j = i + 1; j < nbRequests; j++)
                {
                    if (firstStationRequest[i] < firstStationRequest[j] + nbStationsRequest[j]
                            && firstStationRequest[i] + nbStationsRequest[i] > firstStationRequest[j])
                    {
                        sharingStation[i].Add(j);
                    }

                }
            }
        }
    }

    private void Solve(int timeLimit)
    {
        // Declare the optimization model
        HxModel model = optimizer.GetModel();

        // OptionalInterval: requestSelected[i] represents the seats occupied by the reservation i
        requestSelected = new HxExpression[nbRequests];
        // Declare decisions
        for (int i = 0; i < nbRequests; i++)
        {
            requestSelected[i] = model.OptionalInterval(0, nbSeats);
        }

        // If request i is selected then we allocate the corresponding number of seats
        for (int i = 0; i < nbRequests; i++)
        {
            model.Constraint(model.If(
                    model.Presence(requestSelected[i]),
                    model.Eq(model.Length(requestSelected[i]), nbSeatsRequest[i]),
                    1));
        }

        // If two requests overlap on any station segment, they must not use the same seats
        for (int i = 0; i < nbRequests; i++)
        {
            foreach (int j in sharingStation[i])
            {
                model.Constraint(model.If(
                        model.And(model.Presence(requestSelected[i]), model.Presence(requestSelected[j])),
                        model.Or(requestSelected[j] < requestSelected[i], requestSelected[j] > requestSelected[i]),
                        1));
            }
        }

        // Compute the utilization of the train
        utilization = model.Sum();
        for (int i = 0; i < nbRequests; i++)
        {
            utilization.AddOperand(
                    model.Presence(requestSelected[i]) * nbSeatsRequest[i] * nbStationsRequest[i]);
        }
        // Objective: Maximize utilization
        model.Maximize(utilization);

        model.Close();

        // Parameterize the optimizer
        optimizer.GetParam().SetTimeLimit(timeLimit);

        // Stop the search if the upper threshold is reached
        optimizer.GetParam().SetObjectiveThreshold(0, nbSeats * nbStations);

        optimizer.Solve();
    }

    /* Write the solution in a file using the following format:
        - 1st line: total utilization of the train
        - For each selected request: which seats are occupied */
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(utilization.GetValue());

            for (int i = 0; i < nbRequests; i++)
            {
                HxInterval seats = requestSelected[i].GetIntervalValue();
                if (!seats.IsVoid())
                {
                    output.WriteLine(i + ": [" + seats.Start().ToString()
                            + "..." + (seats.End() - 1).ToString() + "]");
                }
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: GroupSeatReservationKP instanceFile [outputFile] [timeLimit]");
            Environment.Exit(1);
        }

        string instanceFile = args[0];
        string outputFile = args.Length > 1 ? args[1] : null;
        string strTimeLimit = args.Length > 2 ? args[2] : "60";

        using (GroupSeatReservationKP model = new GroupSeatReservationKP())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}

// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
import java.io.*;
import java.util.*;

import com.hexaly.optimizer.*;

public class GroupSeatReservationKP {
    // Data from the problem
    private int nbRequests;
    private int nbStations;
    private int nbSeats;
    private int[] nbStationsRequest;
    private int[] nbSeatsRequest;
    private int[] firstStationRequest;
    private List<List<Integer>> sharingStation;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Decision variable: requestSelected[i] represents the seats occupied by the
    // reservation i
    private HxExpression[] requestSelected;

    // Objective
    private HxExpression utilization;

    private GroupSeatReservationKP(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    /* Read instance data */
    private void readInstance(String fileName) throws IOException {
        try (Scanner input = new Scanner(new File(fileName))) {
            input.useLocale(Locale.ROOT);
            nbRequests = input.nextInt();
            nbStations = input.nextInt();
            nbSeats = input.nextInt();

            nbStationsRequest = new int[nbRequests];
            nbSeatsRequest = new int[nbRequests];
            firstStationRequest = new int[nbRequests];
            for (int i = 0; i < nbRequests; i++) {
                nbStationsRequest[i] = input.nextInt();
                nbSeatsRequest[i] = input.nextInt();
                firstStationRequest[i] = input.nextInt();
                input.nextInt(); // skip
                input.nextInt(); // skip
            }
            // Requests that share at least one station
            sharingStation = new ArrayList<>();
            for (int i = 0; i < nbRequests; i++) {
                sharingStation.add(new ArrayList<>());
                for (int j = i + 1; j < nbRequests; j++) {
                    if (firstStationRequest[i] < firstStationRequest[j] + nbStationsRequest[j]
                            && firstStationRequest[i] + nbStationsRequest[i] > firstStationRequest[j]) {
                        sharingStation.get(i).add(j);
                    }
                }
            }
        }
    }

    private void solve(int timeLimit) {
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // OptionalInterval: requestSelected[i] represents the seats occupied by the
        // reservation i
        requestSelected = new HxExpression[nbRequests];
        // Declare decisions
        for (int i = 0; i < nbRequests; i++) {
            requestSelected[i] = model.optionalIntervalVar(0, nbSeats);
        }

        // If request i is selected then we allocate the corresponding number of seats
        for (int i = 0; i < nbRequests; i++) {
            model.constraint(model.iif(model.presence(requestSelected[i]),
                    model.eq(model.length(requestSelected[i]), nbSeatsRequest[i]), 1));
        }

        // If two requests overlap on any station segment, they must not use the same
        // seats
        for (int i = 0; i < nbRequests; i++) {
            for (int j : sharingStation.get(i)) {
                model.constraint(
                        model.iif(model.and(model.presence(requestSelected[i]), model.presence(requestSelected[j])),
                        model.or(model.lt(requestSelected[j], requestSelected[i]),
                        model.gt(requestSelected[j], requestSelected[i])),
                        1));
            }
        }

        // Compute the utilization of the train
        utilization = model.sum();
        for (int i = 0; i < nbRequests; i++) {
            utilization.addOperand(
                    model.prod(model.presence(requestSelected[i]), nbStationsRequest[i] * nbSeatsRequest[i]));
        }

        // Objective: Maximize utilization
        model.maximize(utilization);

        model.close();

        // Parameterize the optimizer
        optimizer.getParam().setTimeLimit(timeLimit);
        // Stop the search if the upper threshold is reached
        optimizer.getParam().setObjectiveThreshold(0, nbSeats * nbStations);

        optimizer.solve();
    }

    /*
     * Write the solution in a file using the following format:
     * - 1st line: total utilization of the train
     * - For each selected request: which seats are occupied
     */
    private void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(fileName)) {
            output.println(utilization.getValue());
            for (int i = 0; i < nbRequests; i++) {
                HxInterval seats = requestSelected[i].getIntervalValue();
                if (!seats.isVoid()) {
                    output.println(i + ": [" + seats.getStart() + "..." + (seats.getEnd() - 1) + "]");
                }
            }
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: java GroupSeatReservationKP inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }
        String instanceFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "5";
        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            GroupSeatReservationKP model = new GroupSeatReservationKP(optimizer);
            model.readInstance(instanceFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch (Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}