randomized_rounding_triumvirate

class vnep_approx.randomized_rounding_triumvirate.DecompositionMDK(scenario, fractional_solution, gurobi_settings=None, optimization_callback=<function gurobi_callback>, lp_output_file=None, potential_iis_filename=None, logger=None)

Given the decomposition into convex combinations of valid mappings for each request, the MDK computes the optimal rounding given all mapping possibilities found.

calc_max_loads(L)

create_constraints()

create_objective()

create_variables()

post_process_integral_computation()

preprocess_input()

recover_integral_solution_from_variables()

exception vnep_approx.randomized_rounding_triumvirate.RandomizedRoundingError

class vnep_approx.randomized_rounding_triumvirate.RandomizedRoundingMetaData(time_preprocessing, time_optimization, time_postprocessing, lost_flow_in_decomposition, temporal_log, status)

lost_flow_in_decomposition

Alias for field number 3

status

Alias for field number 5

temporal_log

Alias for field number 4

time_optimization

Alias for field number 1

time_postprocessing

Alias for field number 2

time_preprocessing

Alias for field number 0

class vnep_approx.randomized_rounding_triumvirate.RandomizedRoundingSolutionData(profit, max_node_load, max_edge_load, time_to_round_solution)

max_edge_load

Alias for field number 2

max_node_load

Alias for field number 1

profit

Alias for field number 0

time_to_round_solution

Alias for field number 3

class vnep_approx.randomized_rounding_triumvirate.RandomizedRoundingTriumvirate(scenario, gurobi_settings=None, logger=None, number_of_solutions_to_round=1000, mdk_gurobi_parameters=None, write_lp_file_format=None, decomposition_epsilon=1e-10, relative_decomposition_abortion_epsilon=0.001, absolute_decomposition_abortion_epsilon=1e-06)

This class implements 3 different randomized rounding heuristics for obtaining integral mappings. The first class of heuristics applies rounding directly. Either the solution minimizing resource violations or the one maximizing the profit is returned. The second one does round but discards any (chosen) mappings whose addition would violate resource capacities. The last one simply computes the optimal solution of the corresponding Multi-Dimensional Knapsack (MDK). Specifically, given the decomposed solution for each mapping a binary variable is introduced such that capacities are not exceeded and for each request at most one mapping is selected.

ALGORITHM_ID = 'RandomizedRoundingTriumvirate'

calc_max_loads(L)

check_whether_mapping_would_obey_resource_violations(L, mapping_loads)

collect_X_randomized_rounding_samples_with_potential_violations(number_of_samples)

compute_integral_solution()

init_model_creator()

round_solution_without_violations(number_of_samples)

rounding_iteration_violations_allowed_sampling_max_violations(L)

rounding_iteration_violations_without_violations(L, outer_tries)

class vnep_approx.randomized_rounding_triumvirate.RandomizedRoundingTriumvirateResult(meta_data, collection_of_samples_with_violations, result_wo_violations, mdk_result, mdk_meta_data)

cleanup_references(original_scenario)

get_solution()

Returns:the solution (as a namedtuple) stored in this class; abstract function