View all code templates

Constrained Pit Limit Problem (CPIT)

Packing Scheduling

Problem

In the Constrained Pit Limit Problem (CPIT), we consider a set of blocks that can be extracted from a mining pit during several time periods. Extracting a block requires a certain amount of resources. For each type of resource, the sum of resources consumed over a period cannot exceed a certain limit. Each block must be extracted during the same period or during a later period than all its predecessors. The profit of a block’s extraction depends on the block and the period of extraction. Finally, the objective function is to maximize profits made from block extractions.

Principles learned

  • Add set decision variables to model the extraction made during each period
  • Retrieve the index of each block’s extraction period thanks to the ‘find‘ operator
  • Define a lambda function to sum the profit over each period

Data

The instances provided come from Espinoza et al. and are formatted as follows:

  • A .cpit file stores data associated with the Constrained Pit Limit Problem (CPIT):
    • The number of blocks
    • The number of periods
    • The number of resources
    • The discount rate (used to compute the profit of a block’s extraction)
    • For each resource and each period, bounds for the consumption of the resource over the period
    • For each block, its profit
    • For each block and each resource, the consumption of the resource by the extraction of the block (only written in the file if not null)
  • A .prec file stores each block’s predecessors.

Program

The Hexaly model for the Constrained Pit Limit problem (CPIT) uses set decision variables. Each set represents the blocks extracted during a period. We add a dummy period to model blocks that remain unextracted. Thanks to the ‘partition‘ operator, we ensure that each block is extracted at most once.

For a given type of resource, a lambda function applies the ‘sum’ operator over all extracted blocks to compute the total amount of resources consumed over a period. Note that the number of terms in this sum varies during the search, along with the size of the set. We can then constrain this quantity depending on the bounds defined for the problem.

Using the ‘find‘ operator, we can then retrieve the index of the period chosen to extract each block. This allows us to write the precedence constraints between blocks: each block must be extracted during the same period or during a later period than its predecessors.

The profit of a period is computed with a lambda function to apply the ‘sum’ operator over blocks extracted during that period. Once again, the number of terms in this sum varies during the search, along with the size of the set. We maximize profits over all periods.

Download
Execution
hexaly constrained_pit_limit.hxm inFileName=instances/newman1.cpit [solFileName=] [hxTimeLimit=]
use io;
use math;

// Get the name of the precedence file
function getPrecFileName(){
    if (inFileName == nil) inFileName = "instances/newman1.cpit";

    beginIndex = inFileName.indexOf("instances/") + 10; // "instances/" is 10 characters
    endIndex = inFileName.indexOf(".cpit");

    return inFileName.substring(0,beginIndex)+"prec/" 
                + inFileName.substring(beginIndex,endIndex-beginIndex) + ".prec";
}

// Read instance data 
function input() {
    if (inFileName == nil) inFileName = "instances/newman1.cpit";

    // getting information about the problem
    inFile = io.openRead(inFileName);

    inFile.readln(); // Name of the instance
    inFile.readln(); // Type of problem

    local line = inFile.readln(); // NBlocks
    nbBlocks = line.trim().split(" ")[1].toInt();

    line = inFile.readln(); // NPeriods
    nbPeriods = line.trim().split(" ")[1].toInt();

    line = inFile.readln(); // NResources
    nbResources = line.trim().split(" ")[1].toInt();

    line = inFile.readln(); // Discount Rate
    discountRate = line.trim().split(" ")[1].toDouble();

    // Resource Constraints Limits
    inFile.readln(); 
    // Resource Constraints can be <=, >= or both
    // We suppose all constraints have the same form
    resourceLB = false;
    resourceUB = false;

    for [r in 0...nbResources][t in 0...nbPeriods]{
        line = inFile.readln(); 
        local lineSplit = line.trim().split(" ");
        if (lineSplit.count()==5){
            resourceLowerBound[lineSplit[0].toInt()][lineSplit[1].toInt()]
                    = lineSplit[3].toInt();
            resourceUpperBound[lineSplit[0].toInt()][lineSplit[1].toInt()]
                    = lineSplit[4].toInt();
            resourceLB = true;
            resourceUB = true;
        }
        else{
            if (lineSplit[2] == "G"){
                resourceLowerBound[lineSplit[0].toInt()][lineSplit[1].toInt()]
                        = lineSplit[3].toInt();
                resourceLB = true;
            }
            else{
                resourceUpperBound[lineSplit[0].toInt()][lineSplit[1].toInt()]
                        = lineSplit[3].toInt();
                resourceUB = true;
            }
        }
        
    }

    // Objective Function
    line = inFile.readln(); 
    for [b in 0...nbBlocks]{
        line = inFile.readln();
        local lineSplit = line.trim().split(" ");
        profit[lineSplit[0].toInt()] = lineSplit[1].toDouble();
    }
    discountedProfit[t in 0...nbPeriods][b in 0...nbBlocks] = profit[b]/pow(1+discountRate,t);

    // Resource Constraints coefficients
    line = inFile.readln(); 
    // Some values are not defined and therefore equal 0
    // Here we index by resource r first, then the block index b
    for [r in 0...nbResources][b in 0...nbBlocks] resourceUse[r][b] = 0.0; 

    line = inFile.readln();
    while (line != "EOF"){
        local lineSplit = line.trim().split(" ");
        resourceUse[lineSplit[1].toInt()][lineSplit[0].toInt()] = lineSplit[2].toDouble();
        line = inFile.readln();
    }

    inFile.close();

    // Getting information about precedence
    inFile = io.openRead(getPrecFileName());

    predecessors = {};
    for [b in 0...nbBlocks]{
        line = inFile.readln();
        lineSplit = line.trim().split(" ");
        predecessors.add({});
        if (lineSplit[1].toInt()>0){
            for [p in 0...lineSplit[1].toInt()]{
                predecessors[lineSplit[0].toInt()].add(lineSplit[2+p].toInt());
            }
        }
    }

    inFile.close();
}

function model() {
    // Decision variable: periods[t] is the set of blocks extracted during period t
    // There is a dummy period for unextracted blocks
    periods[t in 0...nbPeriods+1] <- set(nbBlocks); 

    // Each block must be assigned to a period (or the dummy period)
    constraint partition(periods);

    // Resources used to extract at period t must be within defined bounds
    sumResourceConsumption[r in 0...nbResources][t in 0...nbPeriods] 
            <- sum(periods[t], b => resourceUse[r][b]);
    for [r in 0...nbResources][t in 0...nbPeriods]{
        if (resourceLB){
            constraint sumResourceConsumption[r][t] >= resourceLowerBound[r][t];
        }
        if (resourceUB){
            constraint sumResourceConsumption[r][t] <= resourceUpperBound[r][t];
        }
    }

    // A block can only be extracted if all its predecessors have been extracted
    blockExtractionPeriod[b in 0...nbBlocks] <- find(periods, b);
    for [b in 0...nbBlocks]{
        for [pred in predecessors[b]]{
            constraint blockExtractionPeriod[b] >= blockExtractionPeriod[pred];
        }
    }

    // Objective function: maximizing profit over extracted blocks
    objective <- sum[t in 0...nbPeriods](sum(periods[t], b => discountedProfit[t][b]));

    maximize objective;
}

function param() {
    if (hxTimeLimit == nil) hxTimeLimit = 60;
}

function output() {
    if (outFileName != nil) {
        outFile = io.openWrite(outFileName);
        outFile.println(objective.value);
        for [b in 0...nbBlocks]{
            if (blockExtractionPeriod[b].value < nbPeriods){
                outFile.println(b + " "+ blockExtractionPeriod[b].value);
            }
        }
        outFile.close();
    }
}
Execution (Windows)
set PYTHONPATH=%HX_HOME%\bin\python
python constrained_pit_limit.py instances\newman1.cpit
 
Execution (Linux)
export PYTHONPATH=/opt/hexaly_14_0/bin/python
python constrained_pit_limit.py instances/newman1.cpit
import hexaly.optimizer
import sys

def get_prec_file_name(instance_file):
    begin_index = instance_file.index("instances") + 10     # the size of "instances/" is 10
    end_index = instance_file.index(".cpit")
    return instance_file[0:begin_index] + "prec/" + \
            instance_file[begin_index:end_index] + ".prec"

def read_instance(instance_file):
    # Reading the first file containing constants of the problem
    with open(instance_file) as f:
        line = f.readline()     # Name of the instance
        line = f.readline()     # Type of problem
        line = f.readline().split(" ")  # Number of blocks
        nb_blocks = int(line[1])

        line = f.readline().split(" ")  # Number of periods
        nb_periods = int(line[1])

        line = f.readline().split(" ")  # Number of resources
        nb_resources = int(line[1])

        line = f.readline().split(" ")  # Discount rate
        discount_rate = float(line[1])

        # Resource Constraints Limits
        line = f.readline()  
        resource_LB,resource_UB = False, False
        resource_lower_bound = []
        resource_upper_bound = []
        for r in range(nb_resources):
            resource_lower_bound.append([])
            resource_upper_bound.append([])
            for t in range(nb_periods):
                line = f.readline().split(" ")
                if len(line) == 5:
                    resource_LB,resource_UB = True, True
                    resource_lower_bound[r].append(int(line[3]))
                    resource_upper_bound[r].append(int(line[4]))
                else:
                    if line[2] == "G":
                        resource_lower_bound[r].append(int(line[3]))
                        resource_LB = True
                    else: # line[2] == "L"
                        resource_upper_bound[r].append(int(line[3]))
                        resource_UB = True

        # Objective function
        line = f.readline()
        profit = [0 for b in range(nb_blocks)]
        for b in range(nb_blocks):
            line = f.readline().split(" ")
            profit[int(line[0])] = float(line[1])

        discounted_profit = [[profit[b]/pow(1+discount_rate,t) for b in range(nb_blocks)] \
                for t in range(nb_periods)]
        
        # Resource constraints coefficients
        # Some values are not defined and therefore equal 0
        # Here we index by resource r first, then the block index b
        line = f.readline()
        resource_use = [[0 for b in range(nb_blocks)] for r in range(nb_resources)]

        line = f.readline().split(" ")
        while line[0] != "EOF\n":
            resource_use[int(line[1])][int(line[0])] = float(line[2])
            line = f.readline().split(" ")
    
    # Reading the second file containing precedence relations
    with open(get_prec_file_name(instance_file)) as f:
        precedence = {}
        for b in range(nb_blocks):
            line = f.readline()[:-1].split(" ")
            if int(line[1]) > 0:
                precedence[int(line[0])] = [int(line[i]) for i in range(2,len(line))]
    
    return (nb_blocks, nb_periods, nb_resources, discount_rate, resource_LB, resource_UB, \
            resource_lower_bound, resource_upper_bound, discounted_profit, resource_use, precedence)

def main(instance_name, output_file, time_limit):
    nb_blocks, nb_periods, nb_resources, discount_rate, resource_LB, resource_UB, \
            resource_lower_bound, resource_upper_bound, discounted_profit, resource_use_data, \
            precedence = read_instance(instance_name)

    with hexaly.optimizer.HexalyOptimizer() as optimizer:
        model = optimizer.model     # Declare the optimization model

        # Decision variables: period_vars[t] is the set of blocks extracted during period t
        # There is a dummy period for unextracted blocks
        period_vars = [model.set(nb_blocks) for t in range(nb_periods+1)]
        periods = model.array(period_vars)
        model.constraint(model.partition(periods))

        # Resources used to extract at period t must be within defined bounds
        resource_use = []
        for r in range(nb_resources):
            resource_use.append(model.array(resource_use_data[r]))
        consumption_lambda = [model.lambda_function(lambda b: resource_use[r][b]) \
                for r in range(nb_resources)]
        consumption_per_period = [[model.sum(period_vars[t],consumption_lambda[r]) \
                for t in range(nb_periods)]  for r in range(nb_resources)]

        for r in range(nb_resources):
            for t in range(nb_periods):
                if resource_LB:
                    model.constraint(consumption_per_period[r][t] >= resource_lower_bound[r][t])
                if resource_UB:
                    model.constraint(consumption_per_period[r][t] <= resource_upper_bound[r][t])

        # A block can only be extracted if all its predecessors have been extracted
        block_extraction_period = [model.find(periods, b) for b in range(nb_blocks)]
        for b in range(nb_blocks):
            if b in precedence.keys():
                for pred in precedence[b]:
                    model.constraint(block_extraction_period[b] >= block_extraction_period[pred])

        # Objective function: profit over extracted blocks
        profits = [model.array(discounted_profit[t]) for t in range(nb_periods)]
        profit_lambdas = [model.lambda_function(lambda b: profits[t][b]) for t in range(nb_periods)]
        profit_per_period = [model.sum(period_vars[t],profit_lambdas[t]) for t in range(nb_periods)]
        objective = model.sum(profit_per_period)

        # Maximizing the objective
        model.maximize(objective)

        model.close()

        # Parameterize
        optimizer.param.time_limit = time_limit

        optimizer.solve()

        # Write the solution in a file following the format:
        # - 1st line: value of the objective (as an integer)
        # - following lines: (if the block is extracted) block's number, period's number
        # - "EOF" to signal the end of the file
        if output_file is not None:
            with open(output_file, 'w') as f:
                f.write("%d\n" % int(objective.value))
                for b in range(nb_blocks):
                    if block_extraction_period[b].value < nb_periods:
                        f.write("{} {}\n".format(b, block_extraction_period[b].value))
                f.write("EOF")


if __name__ == '__main__':
    if len(sys.argv) < 2:
        print("Usage: python constrained_pit_limit.py instance_file \
            [output_file] [time_limit]")
        sys.exit(1)

    instance_file = sys.argv[1]
    output_file = sys.argv[2] if len(sys.argv) >= 3 else None
    time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 60
    main(instance_file, output_file, time_limit)
Compilation / Execution (Windows)
cl /EHsc constrained_pit_limit.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly140.lib
constrained_pit_limit instances\newman1.cpit
 
Compilation / Execution (Linux)
g++ constrained_pit_limit.cpp -I/opt/hexaly_14_0/include -lhexaly140 -lpthread -o constrained_pit_limit
./constrained_pit_limit instances/newman1.cpit
#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <vector>

using namespace hexaly;
using namespace std;

string getPrecFileName(const string& instanceFile){
    size_t posBegin = instanceFile.find("instances/") + 10;  // "instances/" is 10 characters
    size_t posEnd = instanceFile.find(".cpit");
    return instanceFile.substr(0,posBegin)+ "prec/" + 
                instanceFile.substr(posBegin,posEnd-posBegin) + ".prec";
}

class ConstrainedPitLimit {
private:
    // Data from the problem
    int nbBlocks;
    int nbPeriods;
    int nbResources;
    double discountRate;
    bool resourceLB;
    bool resourceUB;
    vector<vector<int>> resourceLowerBound;
    vector<vector<int>> resourceUpperBound;
    vector<double> profitData;
    vector<vector<double>> discountedProfitData;
    vector<vector<double>> resourceUseData;
    vector<vector<int>> precedence;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    vector<HxExpression> periodVars;

    // Intermediate expressions
    vector<vector<HxExpression>> sumResourceConsumption;
    vector<HxExpression> blockExtractionPeriod;

    // Objective
    HxExpression objective;
public :
    // Read instance data
    void readInstance(const string& instanceFile){
        ifstream infile;
        infile.exceptions(ifstream::failbit | ifstream::badbit);

        string tmp; 

        // Reading the first file
        infile.open(instanceFile);

        infile >> tmp; // NAME:
        infile >> tmp; // Name of the problem
        infile >> tmp; // TYPE:
        infile >> tmp; // CPIT

        infile >> tmp; // NBLOCKS:
        infile >> nbBlocks;

        infile >> tmp; // NPERIODS:
        infile >> nbPeriods;

        infile >> tmp; // NRESOURCE_SIDE_CONSTRAINTS:
        infile >> nbResources;

        infile >> tmp; // DISCOUNT_RATE:
        infile >> discountRate;

        infile >> tmp; // RESOURCE_CONSTRAINT_LIMITS:
        resourceLowerBound.resize(nbResources);
        resourceUpperBound.resize(nbResources);

        // Resource Constraints can be <=, >= or both
        // We suppose all constraints have the same form
        resourceLB = false;
        resourceUB = false;
        for (int it=0; it<nbResources*nbPeriods; it++){
            int r,t;
            infile >> r; // resource index
            infile >> t; // period index
            infile >> tmp; // type of constraint

            if (tmp == "L"){
                if (resourceUpperBound[r].size() == 0){
                    resourceUpperBound[r].resize(nbPeriods);
                    resourceUB = true;
                }
                infile >> resourceUpperBound[r][t];                
            }else{
                if (tmp == "I"){
                    if (resourceLowerBound[r].size() == 0){
                        resourceLowerBound[r].resize(nbPeriods);
                        resourceUpperBound[r].resize(nbPeriods);
                        resourceLB = true;
                        resourceUB = true;
                    }
                    infile >> resourceLowerBound[r][t];
                    infile >> resourceUpperBound[r][t];
                }else{ // tmp == "G"
                    if (resourceLowerBound[r].size() == 0){
                        resourceLowerBound[r].resize(nbPeriods);
                        resourceLB = true;
                    }
                    infile >> resourceLowerBound[r][t];
                }
            }
        }

        infile >> tmp; // Objective Function
        profitData.resize(nbBlocks);
        for (int b=0; b<nbBlocks; b++){
            infile >> tmp; // index
            infile >> profitData[stoi(tmp)];
        }

        discountedProfitData.resize(nbPeriods);
        for (int t=0; t<nbPeriods; t++){
            discountedProfitData[t].resize(nbBlocks);
            double discountFactor = pow(1+discountRate,t);
            for (int b=0; b<nbBlocks; b++){
                discountedProfitData[t][b] = profitData[b]/discountFactor;
            }
        }
 
        infile >> tmp; // Resource Constraints coefficients
        resourceUseData.resize(nbResources);
        // Some values are not defined and therefore equal 0
        // Here we index by resource r first, then the block index b
        for (int r=0; r<nbResources; r++){
            for (int b=0; b<nbBlocks; b++){
                resourceUseData[r].push_back(0.0);
            }
        }
 
        infile >> tmp; // if not "EOF" then it is the block index
        while(tmp != "EOF"){
            int r;
            infile >> r;
            infile >> resourceUseData[r][stoi(tmp)];
            infile >> tmp;
        }

        infile.close();

        // Reading the second file
        infile.open(getPrecFileName(instanceFile));

        precedence.resize(nbBlocks);

        for (int it=0; it<nbBlocks; it++){
            int b, nbOfPredecessors;
            infile >> b;
            infile >> nbOfPredecessors;
            for (int pred=0; pred<nbOfPredecessors; pred++){
                int newPredecessor;
                infile >> newPredecessor;
                precedence[b].push_back(newPredecessor);
            }
        }

        infile.close();
    }

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

        // Decision variable: periods[t] is the set of blocks extracted during period t
        // There is a dummy period for unextracted blocks
        periodVars.resize(nbPeriods+1);
        HxExpression periods = model.array();
        for (int t=0; t<nbPeriods+1; t++){
            periodVars[t] = model.setVar(nbBlocks);
            periods.addOperand(periodVars[t]);
        }
        model.constraint(model.partition(periods));
             
        // Create Hexaly array to be able to access them with "at" operators
        vector<HxExpression> resourceUse = vector<HxExpression>(nbResources);
        for (int r=0; r<nbResources; r++){
            resourceUse[r] = model.array(resourceUseData[r].begin(),resourceUseData[r].end());
        }

        // Resources used to extract at period t must be within defined bounds
        vector<HxExpression> consumptionLambda = {};
        sumResourceConsumption.resize(nbResources);
        for (int r=0; r<nbResources; r++){
            consumptionLambda.push_back(model.lambdaFunction([&](HxExpression b) 
                    { return resourceUse[r][b]; }));
            sumResourceConsumption[r].resize(nbPeriods);
            for (int t=0; t<nbPeriods; t++){
                sumResourceConsumption[r][t] = model.sum(periodVars[t], consumptionLambda[r]);
                if (resourceLB){
                    model.constraint(sumResourceConsumption[r][t] >= resourceLowerBound[r][t]);
                }
                if (resourceUB){
                    model.constraint(sumResourceConsumption[r][t] <= resourceUpperBound[r][t]);
                }
            }
        }

        // A block can only be extracted if all its predecessors have been extracted
        blockExtractionPeriod.resize(nbBlocks);
        for (int b=0; b<nbBlocks; b++){
            blockExtractionPeriod[b] = model.find(periods,b);
        }
        for (int b=0; b<nbBlocks; b++){
            for(int pred: precedence[b]){
                model.constraint(blockExtractionPeriod[b] >= blockExtractionPeriod[pred]);
            }
        }

        // Objective function: profit over extracted blocks
        vector<HxExpression> profits;
        vector<HxExpression> profitLambdas;
        objective = model.sum();
        for (int t=0; t<nbPeriods; t++){
            profits.push_back(model.array(discountedProfitData[t].begin(),discountedProfitData[t].end()));
            profitLambdas.push_back(model.lambdaFunction([&](HxExpression b){ return profits[t][b]; }));
            objective.addOperand(model.sum(periodVars[t],profitLambdas[t]));
        }
        model.maximize(objective);

        model.close();

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

        optimizer.solve();
    }

    // Write the solution in a file following the format:
    //  * - 1st line: value of the objective (as an integer)
    //  * - following lines: (if the block is extracted) block's number, period's number
    //  * - "EOF" to signal the end of the file 
    void writeSolution(const string& fileName) {
        ofstream outfile;
        outfile.exceptions(ofstream::failbit | ofstream::badbit);
        outfile.open(fileName.c_str());
        outfile << int(objective.getDoubleValue()) << endl;
        for (int b = 0; b < nbBlocks; b++){
            if (blockExtractionPeriod[b].getIntValue() < nbPeriods){
                outfile << b  << " " << blockExtractionPeriod[b].getIntValue() << endl;
            }
            
        }
        outfile << "EOF";
        outfile.close();
    }
};

int main(int argc, char** argv) {
    if (argc < 2) {
        cerr << "Usage: constrained_pit_limit 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] : "60";

    try{
        ConstrainedPitLimit 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;
    }
}
Compilation / Execution (Windows)
copy %HX_HOME%\bin\Hexaly.NET.dll .
csc ConstrainedPitLimit.cs /reference:Hexaly.NET.dll
ConstrainedPitLimit instances\newman1.cpit
using System;
using System.IO;
using System.Collections.Generic;
using System.Globalization;
using Hexaly.Optimizer;

public class ConstrainedPitLimit : IDisposable
{
    // Data from the problem
    public int nbBlocks;
    public int nbPeriods;
    public int nbResources;
    public float discountRate;
    public bool resourceLB;
    public bool resourceUB;
    public int[][] resourceLowerBound;
    public int[][] resourceUpperBound;
    public float[] profitData;
    public double[][] discountedProfitData;
    public float[][] resourceUseData;
    public List<int>[] precedence;

    // Hexaly Optimizer
    HexalyOptimizer optimizer;

    // Decision variables
    HxExpression[] periodVars;

    // Intermediate expressions
    HxExpression[][] sumResourceConsumption;
    HxExpression[] blockExtractionPeriod;

    // Objective
    HxExpression objective;

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

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

    // Get the name of the precedence file
    string getPrecFileName(string instanceFile) {
        int beginIndex = instanceFile.IndexOf("instances/") + 10; // "instances/" is 10 characters
        int endIndex = instanceFile.IndexOf(".cpit");

        return instanceFile.Substring(0, beginIndex) + "prec/" +
                instanceFile.Substring(beginIndex, endIndex - beginIndex) + ".prec";
    }

    // Read instance data
    void ReadInstance(string instanceFile)
    {
        // Reading the first file
        using (StreamReader input = new StreamReader(instanceFile))
        {
            string[] line;
            input.ReadLine(); // Name
            input.ReadLine(); // Type of problem

            line = input.ReadLine().Split(new[] { ' ' }); // NBlocks
            nbBlocks = int.Parse(line[1]);

            line = input.ReadLine().Split(new[] { ' ' }); // NPeriods
            nbPeriods = int.Parse(line[1]);

            line = input.ReadLine().Split(new[] { ' ' }); // NResources
            nbResources = int.Parse(line[1]);

            line = input.ReadLine().Split(new[] { ' ' }); // Discount Rate
            discountRate = float.Parse(line[1], CultureInfo.InvariantCulture);

            // Resource Constraints Limits
            input.ReadLine();
            // Resource Constraints can be <=, >= or both
            // we suppose all constraints have the same form
            resourceLB = false;
            resourceUB = false;
            resourceLowerBound = new int[nbResources][];
            resourceUpperBound = new int[nbResources][];
            for (int r = 0; r < nbResources; r++)
            {
                resourceLowerBound[r] = new int[nbPeriods];
                resourceUpperBound[r] = new int[nbPeriods];
                for (int t = 0; t < nbPeriods; t++)
                {
                    line = input.ReadLine().Split(new[] { ' ' });

                    if (line[2] == "I")
                    {
                        resourceLB = true;
                        resourceUB = true;
                        resourceLowerBound[int.Parse(line[0])][int.Parse(line[1])]
                                = int.Parse(line[3]);
                        resourceUpperBound[int.Parse(line[0])][int.Parse(line[1])]
                                = int.Parse(line[4]);
                    }
                    else
                    {
                        if (line[2] == "G")
                        {
                            resourceLB = true;
                            resourceLowerBound[r][t] = int.Parse(line[3]);
                        }
                        else // line[2] == "L"
                        {
                            resourceUB = true;
                            resourceUpperBound[r][t] = int.Parse(line[3]);
                        }
                    }
                }
            }


            // Objective Function
            input.ReadLine();
            profitData = new float[nbBlocks];
            for (int b = 0; b < nbBlocks; b++)
            {
                line = input.ReadLine().Split(new[] { ' ' });
                profitData[b] = float.Parse(line[1], CultureInfo.InvariantCulture);
            }

            discountedProfitData = new double[nbPeriods][];
            for (int t = 0; t < nbPeriods; t++)
            {
                discountedProfitData[t] = new double[nbBlocks];
                double discountFactor = Math.Pow(1 + discountRate, t);
                for (int b = 0; b < nbBlocks; b++)
                {
                    discountedProfitData[t][b] = profitData[b] / discountFactor;
                }
            }

            // Resource Constraints coefficients
            input.ReadLine();
            // Some values are not defined and therefore equal 0
            // Here we index by resource r first, then the block index b
            resourceUseData = new float[nbResources][];
            for (int r = 0; r < nbResources; r++)
            {
                resourceUseData[r] = new float[nbBlocks];
                for (int b = 0; b < nbBlocks; b++)
                {
                    resourceUseData[r][b] = 0;
                }
            }

            line = input.ReadLine().Split(new[] { ' ' });
            while (line[0] != "EOF")
            {
                int b = int.Parse(line[0]);
                int r = int.Parse(line[1]);
                resourceUseData[r][b] = float.Parse(line[2], CultureInfo.InvariantCulture);
                line = input.ReadLine().Split(new[] { ' ' });
            }
        }

        // Reading the second file
        using (StreamReader input = new StreamReader(getPrecFileName(instanceFile)))
        {
            string[] line;
            precedence = new List<int>[nbBlocks];
            for (int b = 0; b < nbBlocks; b++)
            {
                line = input.ReadLine().Split(new[] { ' ' });
                if (int.Parse(line[1]) > 0)
                {
                    precedence[b] = new List<int>();
                    for (int pred = 0; pred < int.Parse(line[1]); pred++)
                    {
                        precedence[b].Add(int.Parse(line[pred + 2]));
                    }
                }

            }
        }
    }

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

        // Decision variable: periods[t] is the set of blocks extracted during period t
        // There is a dummy period for unextracted blocks
        periodVars = new HxExpression[nbPeriods + 1];
        HxExpression periods = model.Array();
        for (int t = 0; t < nbPeriods + 1; t++)
        {
            periodVars[t] = model.Set(nbBlocks);
            periods.AddOperand(periodVars[t]);
        }
        model.Constraint(model.Partition(periods));

        // Create Hexaly array to be able to access them with "at" operators
        HxExpression[] resourceUse = new HxExpression[nbResources];
        for (int r = 0; r < nbResources; r++)
        {
            resourceUse[r] = model.Array(resourceUseData[r]);
        }

        // Resources used to extract at period t must be within defined bounds
        HxExpression[] consumptionLambda = new HxExpression[nbResources];
        sumResourceConsumption = new HxExpression[nbResources][];
        for (int r = 0; r < nbResources; r++)
        {
            consumptionLambda[r] = model.LambdaFunction(b =>
            {
                return resourceUse[r][b];
            });
            sumResourceConsumption[r] = new HxExpression[nbPeriods];
            for (int t = 0; t < nbPeriods; t++)
            {
                sumResourceConsumption[r][t] = model.Sum(periodVars[t], consumptionLambda[r]);
                if (resourceLB)
                {
                    model.Constraint(sumResourceConsumption[r][t] >= resourceLowerBound[r][t]);
                }
                if (resourceUB)
                {
                    model.Constraint(sumResourceConsumption[r][t] <= resourceUpperBound[r][t]);
                }
            }
        }

        // A block can only be extracted if all its predecessors have been extracted
        blockExtractionPeriod = new HxExpression[nbBlocks];
        for (int b = 0; b < nbBlocks; b++)
        {
            blockExtractionPeriod[b] = model.Find(periods, b);
        }
        for (int b = 0; b < nbBlocks; b++)
        {
            if (precedence[b] != null)
            {
                foreach (int pred in precedence[b])
                {
                    model.Constraint(blockExtractionPeriod[b] >= blockExtractionPeriod[pred]);
                }
            }
        }

        // Objective function: profit over extracted blocks
        HxExpression[] profits = new HxExpression[nbPeriods];
        HxExpression[] profitLambdas = new HxExpression[nbPeriods];
        objective = model.Sum();
        for (int t = 0; t < nbPeriods; t++)
        {
            profits[t] = model.Array(discountedProfitData[t]);
            profitLambdas[t] = model.LambdaFunction(b =>
            {
                return profits[t][b];
            });
            objective.AddOperand(model.Sum(periodVars[t], profitLambdas[t]));
        }
        model.Maximize(objective);

        model.Close();

        // Parametrize the optimizer
        optimizer.GetParam().SetTimeLimit(limit);

        optimizer.Solve();
    }

    // Write the solution in a file following the format:
    //  * - 1st line: value of the objective (as an integer)
    //  * - following lines: (if the block is extracted) block's number, period's number
    //  * - "EOF" to signal the end of the file 
    void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            output.WriteLine(Math.Round(objective.GetDoubleValue()));
            for (int b = 0; b < nbBlocks; b++)
            {
                if (blockExtractionPeriod[b].GetIntValue() < nbPeriods)
                {
                    output.Write(b);
                    output.Write(' ');
                    output.WriteLine(blockExtractionPeriod[b].GetIntValue());
                }
            }
            output.WriteLine("EOF");
        }
    }
    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: ConstrainedPitLimit inputFile [solFile] [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 (ConstrainedPitLimit model = new ConstrainedPitLimit())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}
Compilation / Execution (Windows)
javac ConstrainedPitLimit.java -cp %HX_HOME%\bin\hexaly.jar
java -cp %HX_HOME%\bin\hexaly.jar;. ConstrainedPitLimit instances\newman1.cpit
Compilation / Execution (Linux)
javac ConstrainedPitLimit.java -cp /opt/hexaly_14_0/bin/hexaly.jar
java -cp /opt/hexaly_14_0/bin/hexaly.jar:. ConstrainedPitLimit instances/newman1.cpit
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class ConstrainedPitLimit {
    
    // Data from the problem
    int nbBlocks;
    int nbPeriods;
    int nbResources;
    double discountRate;
    boolean resourceLB;
    boolean resourceUB;
    int[][] resourceLowerBound;
    int[][] resourceUpperBound;
    double[] profitData;
    double[][] discountedProfitData;
    double[][] resourceUseData;
    ArrayList<ArrayList<Integer>> precedence;

    // Hexaly Optimizer
    private final HexalyOptimizer optimizer;

    // Decision variables
    private HxExpression[] periodVars;

    // Intermediate expressions
    private HxExpression[][] sumResourceConsumption;
    private HxExpression[] blockExtractionPeriod;

    // Objective
    private HxExpression objective;

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

    // Get the name of the precedence file
    private String getPrecFileName(String instanceFile){
        int beginIndex = instanceFile.indexOf("instances/") + 10; // "instances/" is 10 characters
        int endIndex = instanceFile.indexOf(".cpit");

        return instanceFile.substring(0, beginIndex) + "prec/" + 
                    instanceFile.substring(beginIndex, endIndex) + ".prec";
    }

    // Read instance data
    private void readInstance(String instanceFile) throws IOException {
        // Reading the first file
        try (Scanner input = new Scanner(new File(instanceFile))) {
            input.useLocale(Locale.ROOT);

            String line;
            String[] lineSplit;

            input.nextLine(); // Name 
            input.nextLine(); // Type of problem

            line = input.nextLine(); // NBlocks
            nbBlocks = Integer.parseInt(line.split(" ")[1]);

            line = input.nextLine(); // NPeriods
            nbPeriods = Integer.parseInt(line.split(" ")[1]);

            line = input.nextLine(); // NResources
            nbResources = Integer.parseInt(line.split(" ")[1]);

            line = input.nextLine(); // Discount Rate
            discountRate = Double.parseDouble(line.split(" ")[1]);

            // Resource Constraints Limits
            input.nextLine();
            // Resource Constraints can be <=, >= or both
            // we suppose all constraints have the same form
            resourceLB = false;
            resourceUB = false;
            resourceLowerBound = new int[nbResources][nbPeriods];
            resourceUpperBound = new int[nbResources][nbPeriods];
            for (int it = 0; it < nbResources*nbPeriods; it++){
                line = input.nextLine();
                lineSplit = line.split(" ");
                int r = Integer.parseInt(lineSplit[0]);
                int t = Integer.parseInt(lineSplit[1]);
                if (lineSplit.length == 5){
                    resourceLB = true;
                    resourceUB = true;
                    resourceLowerBound[r][t] = Integer.parseInt(lineSplit[3]);
                    resourceUpperBound[r][t] = Integer.parseInt(lineSplit[4]); 
                }else{
                    if (lineSplit[2] == "G"){
                        resourceLB = true;
                        resourceLowerBound[r][t] = Integer.parseInt(lineSplit[3]);
                    }else{ // lineSplit[2] == "L"
                        resourceUB = true;
                        resourceUpperBound[r][t] = Integer.parseInt(lineSplit[3]);
                    }
                }
            }

            // Objective Function
            input.nextLine();
            profitData = new double[nbBlocks];
            for (int b = 0; b < nbBlocks; b++){
                line = input.nextLine();
                profitData[b] =  Double.parseDouble(line.split(" ")[1]);
            }

            discountedProfitData = new double[nbPeriods][nbBlocks];
            for (int t = 0; t < nbPeriods; t++){
                double discountFactor = Math.pow(1+discountRate,t);
                for (int b = 0; b < nbBlocks; b++){
                    discountedProfitData[t][b] = profitData[b]/discountFactor;
                }
            }

            // Resource Constraints coefficients
            line = input.nextLine();
            // Some values are not defined and therefore equal 0
            // Here we index by resource r first, then the block index b
            resourceUseData = new double[nbResources][nbBlocks];
            for (int r = 0; r < nbResources; r++){
                for (int b = 0; b < nbBlocks; b++){
                    resourceUseData[r][b] = 0;
                }
            }

            line = input.nextLine();
            lineSplit = line.split(" ");
            while(!lineSplit[0].equals("EOF")){                
                resourceUseData[Integer.parseInt(lineSplit[1])][Integer.parseInt(lineSplit[0])]
                        = Double.parseDouble(lineSplit[2]);
                line = input.nextLine();
                lineSplit = line.split(" ");
            }
        }
        // Reading the second file
        try (Scanner input = new Scanner(new File(getPrecFileName(instanceFile)))) {
            input.useLocale(Locale.ROOT);

            String line;
            String[] lineSplit;

            precedence = new ArrayList<ArrayList<Integer>>(nbBlocks);
            for (int b = 0; b < nbBlocks; b++){
                precedence.add(b, new ArrayList<Integer>());
                line = input.nextLine();
                lineSplit = line.split(" ");
                for (int pred = 0; pred < Integer.parseInt(lineSplit[1]); pred++){
                    precedence.get(Integer.parseInt(lineSplit[0])).add(
                            Integer.parseInt(lineSplit[2+pred]));
                }
            }
        }
    }
    
    private void solve(int limit){
        // Declare the optimization model
        HxModel model = optimizer.getModel();

        // Decision variable: periods[t] is the set of blocks extracted during period t
        // There is a dummy period for unextracted blocks
        periodVars = new HxExpression[nbPeriods+1];
        HxExpression periods = model.array();
        for (int t = 0; t < nbPeriods + 1; t++){
            periodVars[t] = model.setVar(nbBlocks);
            periods.addOperand(periodVars[t]);
        }
        model.constraint(model.partition(periods));

        // Create Hexaly array to be able to access them with "at" operators
        HxExpression[] resourceUse = new HxExpression[nbResources];
        for (int r = 0; r < nbResources; r++){
            resourceUse[r] = model.array(resourceUseData[r]);
        }

        // Resources used to extract at period t must be within defined bounds
        sumResourceConsumption = new HxExpression[nbResources][nbPeriods];
        HxExpression[] consumptionLambda = new HxExpression[nbResources];
        for (int r = 0; r < nbResources; r++){
            HxExpression resourceUseR = resourceUse[r];
            consumptionLambda[r] = model.lambdaFunction(b -> model.at(resourceUseR,b));
            for (int t = 0; t < nbPeriods; t++){
                sumResourceConsumption[r][t] = model.sum(periodVars[t], consumptionLambda[r]);
                if (resourceLB){
                    model.constraint(
                            model.geq(sumResourceConsumption[r][t], resourceLowerBound[r][t]));
                }
                if (resourceUB){
                    model.constraint(
                            model.leq(sumResourceConsumption[r][t], resourceUpperBound[r][t]));
                }
            }
        }

        // A block can only be extracted if all its predecessors have been extracted
        blockExtractionPeriod = new HxExpression[nbBlocks];
        for (int b = 0; b < nbBlocks; b++){
            blockExtractionPeriod[b] = model.find(periods, b);
        }
        for (int b = 0; b < nbBlocks; b++){
            ArrayList<Integer> predecessors_b = precedence.get(b);
            for (int pred : predecessors_b){
                model.constraint(model.leq(blockExtractionPeriod[pred],blockExtractionPeriod[b]));
            }
        }

        // Objective function: profit over extracted blocks
        HxExpression[] profits = new HxExpression[nbPeriods];
        HxExpression[] profitLambdas = new HxExpression[nbPeriods];
        objective = model.sum();
        for (int t = 0; t < nbPeriods; t++){
            profits[t] = model.array(discountedProfitData[t]);
            HxExpression profitT = profits[t];
            profitLambdas[t] = model.lambdaFunction(b -> model.at(profitT,b));
            objective.addOperand(model.sum(periodVars[t], profitLambdas[t]));
        }
        model.maximize(objective);

        model.close();

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

        optimizer.solve();
    }

    // Write the solution in a file following the format:
    //  * - 1st line: value of the objective (as an integer)
    //  * - following lines: (if the block is extracted) block's number, period's number
    //  * - "EOF" to signal the end of the file
    void writeSolution(String fileName) throws IOException {
        try (PrintWriter output = new PrintWriter(new FileWriter(fileName))) {
            output.println((int)objective.getDoubleValue());
            for (int b = 0; b < nbBlocks; b++){
                if (blockExtractionPeriod[b].getIntValue() < nbPeriods){
                    output.print(b);
                    output.print(" ");
                    output.println(blockExtractionPeriod[b].getIntValue());
                }
            }
            output.println("EOF");
        }
    }

     public static void main(String[] args) {
        if (args.length < 1) {
            System.err.println("Usage: ConstrainedPitLimit 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] : "60";

        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            ConstrainedPitLimit model = new ConstrainedPitLimit(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);
        }
        
    }
}

Explore templates

Discover the ease of use and performance of Hexaly