ppopt.mp_solvers package

Submodules

ppopt.mp_solvers.mpqp_ahmadi module

ppopt.mp_solvers.mpqp_ahmadi.solve(program: MPQP_Program) → Solution | None

This solves a MPQP program with the method proposed by Parisa Ahmadi-Moshkenani et al. This algorithm is similar to the graph algorithm proposed by Richard Oberdeik.

The source for the algorithm can be found here. https://ieeexplore.ieee.org/document/8252719

Parameters:: program – a MPQP_Program
Returns:: The solution of a MPQP Program

ppopt.mp_solvers.mpqp_combinatorial module

ppopt.mp_solvers.mpqp_combinatorial.check_child_feasibility(program: MPQP_Program, set_list: List[List[int]], combination_checker: CombinationTester) → List[List[int]]

Checks the feasibility of a list of active set combinations, if infeasible add to the combination checker and returns all feasible active set combinations

Parameters:

program – An MPQP Program
set_list – The list of active sets
combination_checker – The combination checker that prunes

Returns:

The list of all feasible active sets

ppopt.mp_solvers.mpqp_combinatorial.solve(program: MPQP_Program) → Solution

Solves the MPQP program with a modified algorithm described in Gupta et al. 2011. The algorithm is described in this paper https://www.sciencedirect.com/science/article/pii/S0005109811003190

Parameters:: program – MPQP to be solved
Returns:: the solution of the MPQP

ppopt.mp_solvers.mpqp_geometric module

ppopt.mp_solvers.mpqp_geometric.solve(program: MPQP_Program, active_set=None) → Solution

This solved the multiparametric program using the geometric algorithm described in Spjotvold et al.

https://www.sciencedirect.com/science/article/pii/S1474667016369154

Parameters:

program – a multiparametric program
active_set – an initial optimal active set combination

Returns:

the solution to the multiparametric optimization problem

ppopt.mp_solvers.mpqp_graph module

ppopt.mp_solvers.mpqp_graph.graph_initialization(program, initial_active_sets)

Initializes the graph algorithm based on input

Parameters:

program –
initial_active_sets –

Returns:

ppopt.mp_solvers.mpqp_graph.solve(program: MPQP_Program, initial_active_sets: List[List[int]] | None = None, use_pruning: bool = True) → Solution

Solves the MPQP program with a modified algorithm described in Oberdieck et al. 2016

url: https://www.sciencedirect.com/science/article/pii/S0005109816303971

Parameters:

program – MPQP to be solved
initial_active_sets – An initial critical region to start this algorithm with, otherwise one will be found
use_pruning – Flag for setting if a pruning list is kept and utilized to remove

Returns:

the solution of the MPQP

ppopt.mp_solvers.mpqp_parallel_geometric module

ppopt.mp_solvers.mpqp_parallel_geometric.full_process(center: ndarray, norm: ndarray, radius: float, program: MPQP_Program, current_active_set, indexed_region_as)

This is the function block to be executed in parallel. Takes in a facet. Returns the associated CR on the other side of the facet if it exists, and all the facets associated with the other side of the

Parameters:

center – Chebychev Center of a Critical Region Facet
norm – Normal of the Facet
radius – Chebychev Radius of the Critical Region Facet
program – the multiparametric program being considered
indexed_region_as – set of all critical regions found so far
current_active_set – list of the active set that we are stepping out of

Returns:

The identified Critical Region on the other side of the facet, and the facets of this critical region or None of nothing

ppopt.mp_solvers.mpqp_parallel_geometric.solve(program: MPQP_Program, active_set=None, num_cores=-1) → Solution

This solved the multiparametric program using the geometric algorithm described in Spjotvold et al.

https://www.sciencedirect.com/science/article/pii/S1474667016369154

Parameters:

program – a multiparametric program
active_set – an initial optimal active set combination
num_cores – number of cores to run this calculation on, default of -1 means use all available cores

Returns:

the solution to the multiparametric optimization problem

ppopt.mp_solvers.mpqp_parallel_geometric_exp module

ppopt.mp_solvers.mpqp_parallel_geometric_exp.fathem_facet_exp(center: ndarray, normal: ndarray, radius: float, program, current_active_set: list) → List[int] | None

ppopt.mp_solvers.mpqp_parallel_geometric_exp.fathem_initial_active_sets(program: MPQP_Program, initial_active_sets: List[List[int]])

Covers an initial active set

Parameters:

program –
initial_active_sets –

Returns:

ppopt.mp_solvers.mpqp_parallel_geometric_exp.full_process_2(program, current_active_set)

ppopt.mp_solvers.mpqp_parallel_geometric_exp.solve(program: MPQP_Program, initial_active_sets: List[List[int]] | None = None, num_cores=-1) → Solution

This solved the multiparametric program using the geometric algorithm described in Spjotvold et al.

https://www.sciencedirect.com/science/article/pii/S1474667016369154

Parameters:

program – a multiparametric program
initial_active_sets – a set of optimal active set combinations to initiate the algorithm
num_cores – number of cores to run this calculation on, default of -1 means use all available cores

Returns:

the solution to the multiparametric optimization problem

ppopt.mp_solvers.mpqp_parrallel_combinatorial module

ppopt.mp_solvers.mpqp_parrallel_combinatorial.full_process(program: MPQP_Program, active_set: List[int], murder_list, gen_children) → Tuple[CriticalRegion | None, Set[Tuple[int, ...]], List[List[int]]]

This is the fundamental building block of the parallel combinatorial algorithm, here we branch off of a known feasible active set combinationand then

Parameters:

program – A multiparametric program
active_set – the active set combination that we are expanding on
murder_list – the list containing all previously found
gen_children – A boolean flag, that determines if we should generate the children subsets

Returns:

a list of the following form [Optional[CriticalRegion], pruned active set combination,Possibly Feasible Active set combinations]

ppopt.mp_solvers.mpqp_parrallel_combinatorial.solve(program: MPQP_Program, num_cores=-1) → Solution

Solves the MPQP program with a modified algorithm described in Gupta et al. 2011

This is the parallel version of the combinatorial.

url: https://www.sciencedirect.com/science/article/pii/S0005109811003190

Parameters:

num_cores – Sets the number of cores that are allocated to run this algorithm
program – MPQP to be solved

Returns:

the solution of the MPQP

ppopt.mp_solvers.mpqp_parrallel_combinatorial_exp module

ppopt.mp_solvers.mpqp_parallel_combinatorial_exp.full_process(program: MPQP_Program, active_set: List[int]) → Tuple[List[List[int]], List[CriticalRegion]]

This is the function block that is executed in parallel. This takes a MPQP program as well as an active set combination, and checks the feasibility of all super sets of cardinality + 1. This is done without using a pruning list as in the otherparallel combinatorial algorithm. This is suited for particularly large problems where an exponential number of prunedactive sets are stored, causing a large memory overhead.

Parameters:

program –
active_set –

Returns:

ppopt.mp_solvers.mpqp_parallel_combinatorial_exp.solve(program: MPQP_Program, num_cores=-1) → Solution

Solves the MPQP program with a modified algorithm described in Gupta et al. 2011

This is the parallel version of the combinatorial.

url: https://www.sciencedirect.com/science/article/pii/S0005109811003190

Parameters:

num_cores – Sets the number of cores that are allocated to run this algorithm
program – MPQP to be solved

Returns:

the solution of the MPQP

ppopt.mp_solvers.mpqp_parrallel_graph module

ppopt.mp_solvers.mpqp_parrallel_graph.full_process(program, candidate, murder_list)

This function is the main kernel of the parallel graph algorithm.

Parameters:

program – A multiparametric program
candidate – the active set combination that we are expanding on
murder_list – the list containing all previously found

Returns:

a list of the following form [List[Active Set combinations], active set to prune, Optional[CriticalRegion]]

ppopt.mp_solvers.mpqp_parrallel_graph.solve(program: MPQP_Program, initial_active_sets=None, num_cores=-1, use_pruning: bool = True) → Solution

Solves the MPQP program with a modified algorithm described in Oberdieck et al. 2016

url: https://www.sciencedirect.com/science/article/pii/S0005109816303971

Parameters:: program – MPQP to be solved

:param initial_active_sets:An initial critical region to start this algorithm with, otherwise one will be found :param num_cores: number of cores to run this calculation on, default of -1 means use all available cores :param use_pruning: if the pruning list should be shared to the other threads :return: the solution of the MPQP

ppopt.mp_solvers.solve_mplp module

class ppopt.mp_solvers.solve_mplp.mplp_solver(value)

Bases: Enum

An enumeration.

Dustin = '1'

ppopt.mp_solvers.solve_mplp.solve_mplp(problem: MPLP_Program, algorithm: mplp_solver = mplp_solver.Dustin)

This is the main solver interface for MPLP type problems.

Parameters:

problem –
algorithm –

Returns:

ppopt.mp_solvers.solve_mpqp module

ppopt.mp_solvers.solve_mpqp.filter_solution(solution: Solution) → Solution

This is a placeholder function, in the future this will be used to process and operate on the solution before it is returned to the user.

Parameters:: solution – a multi parametric solution
Returns:: A processed solution

class ppopt.mp_solvers.solve_mpqp.mpqp_algorithm(value)

Bases: Enum

Enum that selects the mpqp algorithm to be used

This is done by passing the argument mpqp_algorithm.algorithm

static all_algos()

combinatorial = 'combinatorial'

combinatorial_graph = 'combinatorial graph'

combinatorial_parallel = 'p combinatorial'

combinatorial_parallel_exp = 'p combinatorial exp'

geometric = 'geometric'

geometric_parallel = 'p geometric'

geometric_parallel_exp = 'p geometric exp'

graph = 'graph'

graph_exp = 'graph exp'

graph_parallel = 'p graph'

graph_parallel_exp = 'p graph exp'

ppopt.mp_solvers.solve_mpqp.solve_mpqp(problem: MPQP_Program, algorithm: mpqp_algorithm = mpqp_algorithm.combinatorial) → Solution

Takes a mpqp programming problem and solves it in a specified manner, In addition this solves MPLPs. The default: solve algorithm is the Combinatorial algorithm by Gupta. et al.

Parameters:

problem – Multiparametric Program to be solved
algorithm – Selects the algorithm to be used

Returns:

the solution of the MPQP, returns an empty solution if there is not an implemented algorithm

ppopt.mp_solvers.solver_utils module

class ppopt.mp_solvers.solver_utils.CombinationTester

Bases: object

Keeps track of all the infeasible active set combinations and filters prospective active set combinations

add_combo(active_set) → None

add_combos(set_list: Set[Tuple[int]]) → None

check(active_set: Set[int]) → bool

Checks if the provided active set combination is a superset of a previously tested infeasible active set

Parameters:: active_set –
Returns:: False if it should be culled and not tested any further, True if the set could be feasible

ppopt.mp_solvers.solver_utils.fathem_facet(center: ndarray, normal: ndarray, radius: float, program, indexed_region_as: Set, current_active_set: list, cand_sol: Solution | None = None) → CriticalRegion | None

This explores the feasible space looking out from a chebychev center of a critical region facet.

Starts from a point with a slight offset from the facet ;= center + D*normal and then check if this is feasible, check if for numerical reasons we accidentally hit ourselves, check to see if we stepped into a found region, if the active set is full rank we can try to build the critical region, return if full dimensional else double the distance from the facet we are considering

Parameters:

center – chebychev center of
normal – the normal of the polytope facet
radius – chebychev radius of the polytope facet
program – the multiparametric program being considered
indexed_region_as – set of all indexed critical region active sets
current_active_set – active set of the region we are stepping out of
cand_sol – a candidate solution to check against

Returns:

a critical region of the other side of the facet if one exists otherwise none

ppopt.mp_solvers.solver_utils.find_optimal_set(problem: MPLP_Program | MPQP_Program) → List[int]

This is a simple combinatorial algorithm for finding the first optimal active set. This is more or less only here for implementation completeness as this should never be used in practice.

Parameters:: problem – a multiparametric optimization program
Returns:: An optimal active set combination

ppopt.mp_solvers.solver_utils.generate_children_sets(active_set, num_constraints: int, murder_list=None) → List[List[int]]

ppopt.mp_solvers.solver_utils.generate_extra(candidate: tuple, expansion_set, murder_list=None, attempted=None) → list

Special routine for graph based algorithm, where we look for optimal active sets that

Parameters:

candidate –
expansion_set –
murder_list –
attempted –

Returns:

ppopt.mp_solvers.solver_utils.generate_reduce(candidate: tuple, murder_list=None, attempted=None, equality_set: Set[int] | None = None) → list

ppopt.mp_solvers.solver_utils.get_facet_centers(A: ndarray, b: ndarray) → List[Tuple[ndarray, ndarray, float]]

This takes the polytope P, and finds all the chebychev centers and normal vectors of each facet and the radius.

\[P = \{x \in \mathbb{R}^n: Ax \leq b\}\]

Parameters:

A – The LHS constraint matrix
b – The RHS constraint vector

Returns:

a list with a tuple for each facet in the polytope (chebychev center, facet normal vector, chebychev radius)

ppopt.mp_solvers.solver_utils.manufacture_lambda(attempted, murder_list)

Module contents

PPOPT.MP_SOLVERS INIT FILE - todo fill in.