Benchmarks Source Code

benchmark_tools

Module containing tools for benchmarking IITCHS MILP problem performance.

The module contains the following classes:

BenchmarkOptionsGenerator: Class for storing configurations options
for benchmarking.

named_tuple_iterator: Similar to itertools.product, but returns an
iterator that yields named tuples. Also maintains an internal count of how many items it has left.

sized_product_iter: Similar to itertools.product, but maintains an
internal count of how many items it has left.

Author: James Usevitch (james.usevitch@ll.mit.edu) Created: Aug 2021

class BenchmarkOptionsGenerator[source]

Bases: object

Class used for setting up problem instance generation for IITCHS benchmarking.

All options are in the form of lists, e.g.

[configuration_1, configuration_2]

Each configuration may be an object or another list.

The function [INSERT HERE] produces an iterable that generates tuples of all possible combinations of configurations. These tuples can be passed to benchmarking functions to set up and run the optimization problems in parallel.

For example, given two options

option1, option2,

each having configurations

option1: [[config_1_1], [config_1_2]] option2: [[config_2_1], [config_2_2]],

the iterator returns tuples of the form

([config_1_1], [config_2_1]), ([config_1_1], [config_2_2]), ([config_1_2],[config_2_1]), ([config_1_2], [config_2_2])

Generating the actual problem instances from, e.g., configuration ranges for a particular value is left up to the benchmarking functions running in parallel (? TBD)

Note

If you only want one configuration to be tested for a particular option, simply make the (outer) list have length one, e.g.

option_1 = [configuration]

Conventions:

Anything appended with “_range_list” is in the form [[min, max],…]. It is meant to present
a list of ranges from which samples can be drawn for a configuration value.

agent_latin_iterator(random_generator=None, repetitions=1)[source]: Creates a latin iterator for Agent options only.

create_iterator()[source]: Creates iterator returning namedtuples with all possible combination of solver options.

create_latin_file_generator(seed=None)[source]: Creates a file generator that directly generates problem .mps / .lp files without actually solving the problem.

create_latin_iterator(random_generator=None, repetitions=1)[source]

Creates iterator returning latin hypercube samples of the variables in question.

NOTE: This does NOT use the field self.number_of_trials_per_combination.

custom_latin_iterator(field_names, random_generator=None, repetitions=1)[source]

Creates a latin iterator from a custom list of field names.

Each field name must be a field in the BenchmarkOptionsGenerator class.

named_tuple_product(**items)[source]

Returns

Based on the following Stack Overflow post: https://stackoverflow.com/a/9098295 CC BY-SA 3.0 https://creativecommons.org/licenses/by-sa/3.0/

ts_latin_iterator(random_generator=None, repetitions=1)[source]: Creates a latin iterator for TS options only.

class Latin_MILP_File_Generator(BenchmarkOptionsGenerator, seed=None)[source]

Bases: object

Object that generates IITCHS MILP .lp / .mps problem files using a BenchmarkOptionsGenerator and Latin Hypercube Sampling.

The MILP problem is NOT solved. The output location of the files can be controlled by setting the .static_options.transition_system_filename variable for the input BenchmarkOptionsGenerator.

class OutputTuple(Trial_Number, MILP_Solver_Used, Runtime_Seconds, Timed_Out, Robust, Regularize, Alpha, Upper_Bound, Grid_TS_Xdim, Grid_TS_Ydim, Number_of_Agents, Agent_List, Number_of_MILP_Constraints, Number_of_MILP_Variables, Objective_Value, Optimizer_Final_Status, Robustness_Variable_Value, Normalized_Travel_Time, TS_Filename, Solution_Filename, Error_Occurred, Formula, Formula_AST_Bound, Formula_Num_Tasks, Formula_Num_TL_Operators, Formula_Num_Bool_Operators, Max_Generation_Attempts_Hit)

Bases: tuple

Agent_List: Alias for field number 11

Alpha: Alias for field number 6

Error_Occurred: Alias for field number 20

Formula: Alias for field number 21

Formula_AST_Bound: Alias for field number 22

Formula_Num_Bool_Operators: Alias for field number 25

Formula_Num_TL_Operators: Alias for field number 24

Formula_Num_Tasks: Alias for field number 23

Grid_TS_Xdim: Alias for field number 8

Grid_TS_Ydim: Alias for field number 9

MILP_Solver_Used: Alias for field number 1

Max_Generation_Attempts_Hit: Alias for field number 26

Normalized_Travel_Time: Alias for field number 17

Number_of_Agents: Alias for field number 10

Number_of_MILP_Constraints: Alias for field number 12

Number_of_MILP_Variables: Alias for field number 13

Objective_Value: Alias for field number 14

Optimizer_Final_Status: Alias for field number 15

Regularize: Alias for field number 5

Robust: Alias for field number 4

Robustness_Variable_Value: Alias for field number 16

Runtime_Seconds: Alias for field number 2

Solution_Filename: Alias for field number 19

TS_Filename: Alias for field number 18

Timed_Out: Alias for field number 3

Trial_Number: Alias for field number 0

Upper_Bound: Alias for field number 7

class latin_dict_iterator(random_generator=None, repetitions=1, **kwargs)[source]

Bases: object

Creates an iterator producing Latin Hypercube samples from the given list of options. Outputs are in the form of dictionaries.

Method for Sampling:

First, all input iterators are turned into lists. The number of input iterators defines the number of “variables” in the sample.

The least common multiple (LCM) of all list lengths defines the dimension of the Latin hypercube samples; i.e. the number of discrete “bins” to be sampled from.

A 2D Numpy array is formed in memory. Each column of the array contains the “raw” coordinates for one Latin hypercube sample routine. (“Raw” means that the coordinates are based on the LCM of all list lengths). When repetition > 1, multiple Latin hypercube routine results are concatenated horizontally into one matrix, with the number of routines equal to repetition.

When next() is called on the iterator, the raw coordinates for a hypercube sample are matched to the corresponding bins in the stored lists. A named tuple is returned containing the entries from these bins.

latin_hypercube_sample(num_variables, num_bins, random_generator=None)[source]

Generates a discrete latin hypercube sampling.

Given n = num_variables and m = num_bins, this function returns an n x m numpy matrix. The iith column of the matrix contains the coordinates for the iith hypercube sample. All samples are guaranteed to be unique in their respective (multidimensional) rows and columns.

Example: 2 variables, 10 bins. A possible return matrix is

array([[5, 3, 0, 9, 6, 8, 7, 4, 2, 1],
[2, 5, 3, 4, 1, 7, 6, 8, 9, 0]])

Each column is the 2D index of a sample that is unique in its row and column (i.e. 10 rooks on a chessboard that don’t threaten each other).

Example: 3 variables, 10 bins. A possible return matrix is

array([[1, 9, 4, 2, 6, 7, 3, 0, 8, 5],
[0, 1, 9, 2, 7, 6, 4, 3, 5, 8], [6, 4, 8, 3, 0, 2, 9, 7, 5, 1]])

Each column is the 3D index of a sample that is unique in its 3D rows /columns (i.e. 10 rooks in a 3D cube chessboard that don’t threaten each other)

TODO: Move this to generation_tools.py?

class latin_named_tuple_iterator(random_generator=None, repetitions=1, **kwargs)[source]

Bases: object

Similar to named_tuple_iterator, but generates latin hypercube samples to reduce the amount of testing required.

Method for Sampling:

First, all input iterators are turned into lists. The number of input iterators defines the number of “variables” in the sample.

The least common multiple (LCM) of all list lengths defines the dimension of the Latin hypercube samples; i.e. the number of discrete “bins” to be sampled from.

A 2D Numpy array is formed in memory. Each column of the array contains the “raw” coordinates for one Latin hypercube sample routine. (“Raw” means that the coordinates are based on the LCM of all list lengths). When repetition > 1, multiple Latin hypercube routine results are concatenated horizontally into one matrix, with the number of routines equal to repetition.

When next() is called on the iterator, the raw coordinates for a hypercube sample are matched to the corresponding bins in the stored lists. A named tuple is returned containing the entries from these bins.

lcm(number_list)[source]: Finds the least common multiple of a list of integers

class named_tuple_iterator(**kwargs)[source]

Bases: object

Similar to sized_product_iter, but returns the items as named tuples.

Note: Does not take the “repeat” keyword argument used in itertools.product.

class sized_product_iter(*args, repeat=1)[source]

Bases: object

Similar to itertools.product, but maintains an internal count of the objects it has left.

Works with next() and len().

solve_one_optimization_problem(options_tuple, static_options, trial_number=None, verbose=False, transition_system=None, formula=None, seed=None)[source]

Runs one optimization problem using the parameters from the named tuple options_tuple argument and the SimpleNamespace object static_options.

The input tuple must be a named tuple obtained from BenchmarkOptionsGenerator.create_iterator().

Returns: Running time of the optimization algorithm PuLP_Model:
Return type: runtime (float)

solve_problem_robust_and_not_robust(options_tuple, static_options, trial_number=None, verbose=False, formula=None, seed=None)[source]: Solves an IITCHS problem configuration for both the ‘robust’ and ‘not robust’ cases, keeping the transition system the same.

generation_tools

Random generation tools for IITCHS benchmarking purposes.

The generation functions fall roughly in three groups:

Transition System generation

Agent / Capability generation

CaTL Formula generation

Some of the functions are modifications of functions in the file RandomizedCaTLExperiments.py.

Author: James Usevitch (james.usevitch@ll.mit.edu)

FG_operators_and_tasks_to_strings(operator_strings, intervals, task_strings)[source]

Creates a Python list of formulas from the inputs.

This function only combines the operators F, G, FG, GF with tasks. To combine formulas together using AND and OR, use the function [INSERT HERE].

Args:

Returns:

class_to_capability_dict(capabilities, presort=True)[source]

Creates dictionary mapping capability class to the corresponding sets of capabilities.

For example, given the capabilities (UV, IR, Mo), the dictionary might satisfy:

class_to_capability_dict = {
set('UV'),
set('IR'),
set('Mo'),
set(['UV','IR']),
set(['IR','Mo']),
set(['UV','Mo']),
set(['UV','IR','Mo'])
}

Note

To ensure results are deterministic, by default the list of capabilities is sorted alphabetically in a case insensitive manner (using str.casefold) before creating the dictionary. To turn off this sorting, use the keyword argument presort=False.

Parameters

capabilities (list) – List of capability strings.
presort (bool) – Boolean. If True, the list of capabilities is sorted in a case-insensitive manner before creating the dictionary. True by default.

combine_formulas_AND_OR(formulas, operators)[source]

Combines multiple formulas together with AND and OR operators.

Formulas and operators must be listed in order; i.e. entry ii of operators goes between entries ii and ii+1 of formulas.

Parameters

formulas (list) – List of formula strings consisting of F, G, FG, GF.
operators (list) – List of AND / OR operators in the form “AND”, “OR”, “&&”, or “||”. Must be listed in order of combination, i.e. entry ii goes between entries ii and ii+1 from formulas.

Returns

String of the resulting formula.

Return type

(str)

generateGridTS_label_counts(tsname, dimensions, labelNames, edgeWeightRange, label_counts, random_generator=None)[source]

Generates a transition system in the form of a grid, with a specified number of occurrences for each label.

Similar to generateRandomGridTS. The main difference is that a label_counts vector is passed in specifying how many times each label should occur in the transition system. States are allowed to have multiple labels.

Parameters

tsname (str) – Name of the transition system
dimensions (list) – Two-element list with the x, y dimensions of the grid, e.g. [xdim, ydim]
labelNames (list) – String names of each label
edgeWeightRange (list) –
label_counts (list) – List of integers specifying how many times each label should occur in the transition system. Must have the same length as the labelNames list.
random_generator – Numpy random generator object. If unspecified, a new one is created using np.random.default_rng().

Returns

A Lomap transition system

Return type

()

generateRandomGridTS(tsname, dimensions, labelNames, edgeWeightRange, max_labels_per_state, random_generator=None)[source]

Generates a transition system in the form of a grid.

All states

Note

This function is loosely based on the function generateRandomGridTS_seed in RandomizedCaTLExperiments.py. The main differences include:

A random_generator is passed into this function instead of a seed number.
The method of assigning labels is different

generate_agents_by_class(state_list, capability_list, num_agents_per_class, random_generator=None)[source]

Generates an equal amount of agents per agent class.

Initial starting states

generate_agents_by_total_and_distribution(total_agents, class_to_capability_dict, capability_class_distribution, initial_state_list, random_generator=None)[source]

Generates agents by specifying the total number of agents and a probability distribution over all possible capability classes.

Parameters

total_agents (int) – The total number of agents to create
class_to_capability_dict –
Dictionary mapping capability class to the corresponding sets of capabilities. For example, given the capabilities (UV, IR, Mo), the dictionary might satisfy ```python class_to_capability_dict = {

0: set(‘UV’), 1: set(‘IR’), 2: set(‘Mo’), 3: set([‘UV’,’IR’]), 4: set([‘IR’,’Mo’]), 5: set([‘UV’,’Mo’]), 6: set([‘UV’,’IR’,’Mo’])
capability_class_distribution (list) – List of probabilities for each capability class
initial_state_list – List of potential starting states for the agents
random_generator – A Numpy random generator. If None, the function creates one using np.random.default_rng().

Returns

A list of agents.

Return type

(list)

generate_multiple_random_CaTL_formula(options_tuple, number_of_formulas=1)[source]

Generates random TL formulas.

Parameters

number_of_formulas (int) – Number of formula strings to generate.
number_of_atomics_per_formula (int) – Number of atomics to include in each formula string. An “atomic” is one temporal operator (e.g. F, G, FG, GF, U) combined with one task (two tasks for the U operator). Atomics are combined into one formula with the AND / OR boolean operators.

Returns

List of formula strings.

Return type

(list)

generate_random_CaTL_formula_and_info(options_tuple, random_generator=None)[source]

Generates one random TL formula and returns it, along with other information about the formula.

Parameters

options_tuple (namedtuple) –
random_generator – Numpy random generator, e.g. np.random.default_rng(). If None, then the function will create one using np.random.default_rng(). Passing in a random number generator helps prevent similar results when running multiple benchmark simulations in parallel.

Returns

Output tuple including the following elements:

formula (string): The CaTL formula
ast_bound (int): The AST bound of the formula.
number_of_atomics_per_formula (int): The number of atomics in the formula. Note that by
the definition of an atomic, this number is identical to:
The number of tasks # TODO: Only true if U isn’t included

The number of TL operators

The number of boolean operators + 1
num_tasks (int): The number of tasks that are in the formula
num_tl_operators (int): The total number of F, G, FG, GF, or U operators
found in the formula.
num_bool_operators (int): The total number of AND and OR operators
found in the formula.

Return type

(tuple)

generate_random_agents(state_list, capability_list, num_capabilities_per_agent_range, number_of_agents_generated=1, seed=None)[source]

Generates random arrays of agents.

The num_capabilities_per_agent_range is in the form [min,max]. Agents are given a random number of capabilities, where the number of capabilities is in this range. To specify a specific number of capabilities, set min == max.

probability_over_capability_cardinality(cardinality_distr)[source]

Generates a probability distribution based on how likely it is for agents to have a _number_ of capabilities, e.g. 1 capability vs. 3 capabilities.

A capability cardinality class is a set of capability classes, each class having the same cardinality of capabilities. For example,

The capability classes {UV}, {IR}, {Mo} are all of cardinality class 1 (one capability per class)

The capability classes {UV,IR}, {UV,Mo}, {IR, Mo} are all of cardinality class 2 (two capabilities per class)

The capability class {UV,IR,Mo} is of cardinality class 3 (three capabilities per class)

This function assumes that each cardinality class C_i is given a probability weight w_i (e.g., the probability of an agent having 1, or 2, or 3 capabilities). The probability w_i is then divided uniformly among all possible capability classes within that cardinality class.

More specifically, given n capabilities, the capability cardinality class k has (n choose k) agents. If class k is given probability weight w_k, then each capability class in cardinality class k has probability w_k / (n choose k).

Example

Suppose our capabilities are {UV, IR, Mo}. Suppose that cardinality_distr = [0.2, 0.3, 0.5]. Then:

Each capability class of cardinality 1 ({UV}, {Mo}, {IR}) would have probability 0.2 / 3
Each capability class of cardinality 2 ({UV,Mo}, {Mo,IR}, {UV,IR}) would have probability 0.3 / 3
Each capability class of cardinality 3 ({UV,Mo,IR}) would have probability 0.5 / 1

task_capabilities_to_string(capabilities, num_required_agents)[source]

Converts a list of capabilities and a list of number of required agents to string form for CaTL task formulas.

Parameters

capabilities (list) – A list of string capabilities, e.g. ['UV', 'Mo', 'Vis', 'IR'].
num_required_agents (list) – A list of integers specifying how many agents are needed for the corresponding entries in capabilities.

Returns

A string representation of the capabilities needed for a task, e.g. ‘{(UV,1)}’ or ‘{(IR,2),(Mo,3)}’.

Return type

(string)

tasks_to_strings(durations, state_labels, capability_strings)[source]

Creates a Python list of task strings from the inputs.

Parameters

durations (list) – List of nonnegative integer time durations
state_labels (list) – List of string state labels
capability_strings (list) – List of capability strings, e.g. ‘{(UV,1)}’ or ‘{(Vis,2),(IR,4)}’. Use task_capabilities_to_string() function.

Returns

A Python list of task strings.

Return type

(list)