This repository contains the instances and the experimental results of the research work entitled "Matheuristics for the Swath Segment Selection Problem" (by Roberto Cordone, Stefano Dalla Longa, Daniel Dissegna -- University of Milan).

In this README file, the research work is referred to as the "main manuscript".
The manuscript is currently under review, and its title may change in the future.

This file describes the repository structure as well as its content.

The repository contains this documentation file and three other files, whose content is described below.

================================================
File 'SSSP.mod'
================================================

- This AMPL model file contains the ILP formulation of the SSSP reported in the main manuscript, in AMPL format.

================================================
File 'SSSP_instances.zip'
================================================

- This archive file contains the 336 instances of the SSSP used in the main manuscript. 

  The generic name of each instance file is: [WEIGHT_TYPE]n[SIZE]a[MIN_WEIGHT]r[MIN_REWARD]d[CAPACITY]i01, where
  * [WEIGHT_TYPE] is either "dif" (independent weights) or "ide" (identical weights), referring to the segments that cover each shard
  * [SIZE] is the number of swaths of each type (ascending and descending) and the number of segments contained in each swath 
  * [MIN_WEIGHT] is the minimum segment weight (the maximum is 100)
  * [MIN_REWARD] is the minimum shard reward (the maximum is 100)
  * [CAPACITY] is the percent of the smallest total swath weight used to determine the swath capacities

  The content of each file provides the corresponding instance data in AMPL format:
  * "param NumSwaths :=" introduces the number of swaths, that are indexed from 1 to NumSwaths
  * "param NumSegments :=" introduces the number of segments, that are indexed from 1 to NumSegments
  * "param NumShards :=" introduces the number of shards, that are indexed from 1 to NumShards
  * "param r :=" introduces each shard index with its reward 
  * "param: w s_e h_e :=": introduces a table that associates each segment with its weight, its containing swath, and the shard it covers
  * "param b :=": introduces each swath index with its capacity 

================================================
File 'SSSP-VLNS-DetailedResults.csv'
================================================

- This comma-separated values file reports the detailed computational results obtained by the methods described in the main manuscript.

  The file consists of 337 rows (a header row and a row for each instance) and 23 columns: 
  * column A (labelled "Instance") reports the name of the instance
  * columns B and C (labelled "IndependentKP-LB" and "IndependentKP-CPU" in the first row) report the heuristic solution value (that is a lower bound) and the computational time in seconds for algorithm IndependentKP 
  * columns D and E (labelled "SequentialKP-LB" and "SequentialKP-CPU") report the same information for algorithm SequentialKP 
  * columns F and G (labelled "DoubleKP-LB" and "DoubleKP-CPU") report the same information for algorithm DoubleKP 
  * columns H and I (labelled "ReshuffledKP-LB" and "ReshuffledKP-CPU") report the same information for algorithm ReshuffledKP 
  * columns J and K (labelled "Diving-LB" and "Diving-CPU") report the same information for algorithm Diving
  * columns L and M (labelled "VLNS-30sec-LB" and "VLNS-30sec-CPU") report the same information for algorithm VLNS-30sec (the computational time refers only to VLNS: adding the times of the five initialisation procedures gives the overall time)
  * columns N and O (labelled "VLNS-180sec-LB" and "VLNS-180sec-CPU") report the same information for algorithm VLNS-180sec (the computational time refers only to VLNS: adding the times of the five initialisation procedures gives the overall time)
  * columns P and Q (labelled "VLNS-LagrBB-3300s-LB" and "VLNS-LagrBB-3300s-UB") report the lower and the upper bound computed by the Lagrangean branch-and-bound of the 2008 paper mentioned in the main manuscript, initialised with VLNS with a 30-second time limit and terminated after at most 3300 seconds overall 
  * columns R and S (labelled "LagrBB-2008-1h-LB" and "LagrBB-2008-1h-UB") report the same information for the Lagrangean branch-and-bound as reported in the 2008 paper (one hour was the time limit originally imposed, that corresponds to 3300 seconds on the machine used for the new experiments)
  * columns T and U (labelled "CPLEX-2008-1h-LB" and "CPLEX-2008-1h-UB") report the same information for CPLEX as reported in the 2008 paper 
  * columns V and W (labelled "BestKnown-LB" and "BestKnown-UB") report the overall best known lower and upper bound, obtained by combining the previously known ones with the newly obtained ones
        
The details of the methods, machine and software used to produce the results are reported in the main manuscript.