<s> from __future__ import print_function , unicode_literals , absolute_import , division <EOL> from . edit_info import EditInfo <EOL> from . error import RequiredFailure , ConstraintNotFound , InternalError <EOL> from . expression import Expression , StayConstraint , EditConstraint , ObjectiveVariable , SlackVariable , DummyVariable <EOL> from . tableau import Tableau <EOL> from . utils import approx_equal , EPSILON , STRONG , WEAK <EOL> class SolverEditContext ( object ) : <EOL> def __init__ ( self , solver ) : <EOL> self . solver = solver <EOL> def __enter__ ( self ) : <EOL> self . solver . begin_edit ( ) <EOL> def __exit__ ( self , type , value , tb ) : <EOL> self . solver . end_edit ( ) <EOL> class SimplexSolver ( Tableau ) : <EOL> def __init__ ( self ) : <EOL> super ( SimplexSolver , self ) . __init__ ( ) <EOL> self . stay_error_vars = [ ] <EOL> self . error_vars = { } <EOL> self . marker_vars = { } <EOL> self . objective = ObjectiveVariable ( '<STR_LIT>' ) <EOL> self . edit_var_map = { } <EOL> self . slack_counter = <NUM_LIT:0> <EOL> self . artificial_counter = <NUM_LIT:0> <EOL> self . dummy_counter = <NUM_LIT:0> <EOL> self . auto_solve = True <EOL> self . needs_solving = False <EOL> self . optimize_count = <NUM_LIT:0> <EOL> self . rows [ self . objective ] = Expression ( ) <EOL> self . edit_variable_stack = [ <NUM_LIT:0> ] <EOL> def __repr__ ( self ) : <EOL> parts = [ ] <EOL> parts . append ( '<STR_LIT>' % self . stay_error_vars ) <EOL> parts . append ( '<STR_LIT>' % self . edit_var_map ) <EOL> return super ( SimplexSolver , self ) . __repr__ ( ) + '<STR_LIT:\n>' + '<STR_LIT:\n>' . join ( parts ) <EOL> def add_constraint ( self , cn , strength = None , weight = None ) : <EOL> if strength or weight : <EOL> cn = cn . clone ( ) <EOL> if strength : <EOL> cn . strength = strength <EOL> if weight : <EOL> cn . weight = weight <EOL> expr , eplus , eminus , prev_edit_constant = self . new_expression ( cn ) <EOL> if not self . try_adding_directly ( expr ) : <EOL> self . add_with_artificial_variable ( expr ) <EOL> self . needs_solving = True <EOL> if cn . is_edit_constraint : <EOL> i = len ( self . edit_var_map ) <EOL> self . edit_var_map [ cn . variable ] = EditInfo ( cn , eplus , eminus , prev_edit_constant , i ) <EOL> if self . auto_solve : <EOL> self . optimize ( self . objective ) <EOL> self . set_external_variables ( ) <EOL> return cn <EOL> def add_edit_var ( self , v , strength = STRONG ) : <EOL> return self . add_constraint ( EditConstraint ( v , strength ) ) <EOL> def remove_edit_var ( self , v ) : <EOL> self . remove_constraint ( self . edit_var_map [ v ] . constraint ) <EOL> def edit ( self ) : <EOL> return SolverEditContext ( self ) <EOL> def resolve ( self ) : <EOL> self . dual_optimize ( ) <EOL> self . set_external_variables ( ) <EOL> self . infeasible_rows . clear ( ) <EOL> self . reset_stay_constants ( ) <EOL> def new_expression ( self , cn ) : <EOL> expr = Expression ( constant = cn . expression . constant ) <EOL> eplus = None <EOL> eminus = None <EOL> prev_edit_constant = None <EOL> for v , c in cn . expression . terms . items ( ) : <EOL> e = self . rows . get ( v ) <EOL> if not e : <EOL> expr . add_variable ( v , c ) <EOL> else : <EOL> expr . add_expression ( e , c ) <EOL> if cn . is_inequality : <EOL> self . slack_counter = self . slack_counter + <NUM_LIT:1> <EOL> slack_var = SlackVariable ( prefix = '<STR_LIT:s>' , number = self . slack_counter ) <EOL> expr . set_variable ( slack_var , - <NUM_LIT:1> ) <EOL> self . marker_vars [ cn ] = slack_var <EOL> if not cn . is_required : <EOL> self . slack_counter = self . slack_counter + <NUM_LIT:1> <EOL> eminus = SlackVariable ( prefix = '<STR_LIT>' , number = self . slack_counter ) <EOL> expr . set_variable ( eminus , <NUM_LIT:1> ) <EOL> z_row = self . rows [ self . objective ] <EOL> z_row . set_variable ( eminus , cn . strength * cn . weight ) <EOL> self . insert_error_var ( cn , eminus ) <EOL> self . note_added_variable ( eminus , self . objective ) <EOL> else : <EOL> if cn . is_required : <EOL> self . dummy_counter = self . dummy_counter + <NUM_LIT:1> <EOL> dummy_var = DummyVariable ( number = self . dummy_counter ) <EOL> eplus = dummy_var <EOL> eminus = dummy_var <EOL> prev_edit_constant = cn . expression . constant <EOL> expr . set_variable ( dummy_var , <NUM_LIT:1> ) <EOL> self . marker_vars [ cn ] = dummy_var <EOL> else : <EOL> self . slack_counter = self . slack_counter + <NUM_LIT:1> <EOL> eplus = SlackVariable ( prefix = '<STR_LIT>' , number = self . slack_counter ) <EOL> eminus = SlackVariable ( prefix = '<STR_LIT>' , number = self . slack_counter ) <EOL> expr . set_variable ( eplus , - <NUM_LIT:1> ) <EOL> expr . set_variable ( eminus , <NUM_LIT:1> ) <EOL> self . marker_vars [ cn ] = eplus <EOL> z_row = self . rows [ self . objective ] <EOL> sw_coeff = cn . strength * cn . weight <EOL> z_row . set_variable ( eplus , sw_coeff ) <EOL> self . note_added_variable ( eplus , self . objective ) <EOL> z_row . set_variable ( eminus , sw_coeff ) <EOL> self . note_added_variable ( eminus , self . objective ) <EOL> self . insert_error_var ( cn , eminus ) <EOL> self . insert_error_var ( cn , eplus ) <EOL> if cn . is_stay_constraint : <EOL> self . stay_error_vars . append ( ( eplus , eminus ) ) <EOL> elif cn . is_edit_constraint : <EOL> prev_edit_constant = cn . expression . constant <EOL> if expr . constant < <NUM_LIT:0> : <EOL> expr . multiply ( - <NUM_LIT:1.0> ) <EOL> return expr , eplus , eminus , prev_edit_constant <EOL> def begin_edit ( self ) : <EOL> assert len ( self . edit_var_map ) > <NUM_LIT:0> <EOL> self . infeasible_rows . clear ( ) <EOL> self . reset_stay_constants ( ) <EOL> self . edit_variable_stack . append ( len ( self . edit_var_map ) ) <EOL> def end_edit ( self ) : <EOL> assert len ( self . edit_var_map ) > <NUM_LIT:0> <EOL> self . resolve ( ) <EOL> self . edit_variable_stack . pop ( ) <EOL> self . remove_edit_vars_to ( self . edit_variable_stack [ - <NUM_LIT:1> ] ) <EOL> def remove_all_edit_vars ( self ) : <EOL> self . remove_edit_vars_to ( <NUM_LIT:0> ) <EOL> def remove_edit_vars_to ( self , n ) : <EOL> try : <EOL> removals = [ ] <EOL> for v , cei in self . edit_var_map . items ( ) : <EOL> if cei . index >= n : <EOL> removals . append ( v ) <EOL> for v in removals : <EOL> self . remove_edit_var ( v ) <EOL> assert len ( self . edit_var_map ) == n <EOL> except ConstraintNotFound : <EOL> raise InternalError ( '<STR_LIT>' ) <EOL> def add_stay ( self , v , strength = WEAK , weight = <NUM_LIT:1.0> ) : <EOL> return self . add_constraint ( StayConstraint ( v , strength , weight ) ) <EOL> def remove_constraint ( self , cn ) : <EOL> self . needs_solving = True <EOL> self . reset_stay_constants ( ) <EOL> z_row = self . rows [ self . objective ] <EOL> e_vars = self . error_vars . get ( cn ) <EOL> if e_vars : <EOL> for cv in e_vars : <EOL> try : <EOL> z_row . add_expression ( self . rows [ cv ] , - cn . weight * cn . strength , self . objective , self ) <EOL> except KeyError : <EOL> z_row . add_variable ( cv , - cn . weight * cn . strength , self . objective , self ) <EOL> try : <EOL> marker = self . marker_vars . pop ( cn ) <EOL> except KeyError : <EOL> raise ConstraintNotFound ( ) <EOL> if not self . rows . get ( marker ) : <EOL> col = self . columns [ marker ] <EOL> exit_var = None <EOL> min_ratio = <NUM_LIT:0.0> <EOL> for v in col : <EOL> if v . is_restricted : <EOL> expr = self . rows [ v ] <EOL> coeff = expr . coefficient_for ( marker ) <EOL> if coeff < <NUM_LIT:0> : <EOL> r = - expr . constant / coeff <EOL> if exit_var is None or r < min_ratio : <EOL> min_ratio = r <EOL> exit_var = v <EOL> if exit_var is None : <EOL> for v in col : <EOL> if v . is_restricted : <EOL> expr = self . rows [ v ] <EOL> coeff = expr . coefficient_for ( marker ) <EOL> r = expr . constant / coeff <EOL> if exit_var is None or r < min_ratio : <EOL> min_ratio = r <EOL> exit_var = v <EOL> if exit_var is None : <EOL> if len ( col ) == <NUM_LIT:0> : <EOL> self . remove_column ( marker ) <EOL> else : <EOL> exit_var = [ v for v in col if v != self . objective ] [ - <NUM_LIT:1> ] <EOL> if exit_var is not None : <EOL> self . pivot ( marker , exit_var ) <EOL> if self . rows . get ( marker ) : <EOL> expr = self . remove_row ( marker ) <EOL> if e_vars : <EOL> for v in e_vars : <EOL> if v != marker : <EOL> self . remove_column ( v ) <EOL> if cn . is_stay_constraint : <EOL> if e_vars : <EOL> remaining = [ ] <EOL> while self . stay_error_vars : <EOL> p_evar , m_evar = self . stay_error_vars . pop ( ) <EOL> found = False <EOL> try : <EOL> e_vars . remove ( p_evar ) <EOL> found = True <EOL> except KeyError : <EOL> pass <EOL> try : <EOL> e_vars . remove ( m_evar ) <EOL> found = True <EOL> except KeyError : <EOL> pass <EOL> if not found : <EOL> remaining . append ( ( p_evar , m_evar ) ) <EOL> self . stay_error_vars = remaining <EOL> elif cn . is_edit_constraint : <EOL> assert e_vars is not None <EOL> self . remove_column ( self . edit_var_map [ cn . variable ] . edit_minus ) <EOL> del self . edit_var_map [ cn . variable ] <EOL> if e_vars : <EOL> for e_var in e_vars : <EOL> del self . error_vars [ e_var ] <EOL> if self . auto_solve : <EOL> self . optimize ( self . objective ) <EOL> self . set_external_variables ( ) <EOL> def resolve_array ( self , new_edit_constants ) : <EOL> for v , cei in self . edit_var_map . items ( ) : <EOL> self . suggest_value ( v , new_edit_constants [ cei . index ] ) <EOL> self . resolve ( ) <EOL> def suggest_value ( self , v , x ) : <EOL> cei = self . edit_var_map . get ( v ) <EOL> if not cei : <EOL> raise InternalError ( "<STR_LIT>" % v ) <EOL> delta = x - cei . prev_edit_constant <EOL> cei . prev_edit_constant = x <EOL> self . delta_edit_constant ( delta , cei . edit_plus , cei . edit_minus ) <EOL> def solve ( self ) : <EOL> if self . needs_solving : <EOL> self . optimize ( self . objective ) <EOL> self . set_external_variables ( ) <EOL> def set_edited_value ( self , v , n ) : <EOL> if v not in self . columns or v not in self . rows : <EOL> v . value = n <EOL> if not approx_equal ( n , v . value ) : <EOL> self . add_edit_var ( v ) <EOL> self . begin_edit ( ) <EOL> self . suggest_value ( v , n ) <EOL> self . end_edit ( ) <EOL> def add_var ( self , v ) : <EOL> if v not in self . columns or v not in self . rows : <EOL> self . add_stay ( v ) <EOL> def add_with_artificial_variable ( self , expr ) : <EOL> self . artificial_counter = self . artificial_counter + <NUM_LIT:1> <EOL> av = SlackVariable ( prefix = '<STR_LIT:a>' , number = self . artificial_counter ) <EOL> az = ObjectiveVariable ( '<STR_LIT>' ) <EOL> az_row = expr . clone ( ) <EOL> self . add_row ( az , az_row ) <EOL> self . add_row ( av , expr ) <EOL> self . optimize ( az ) <EOL> az_tableau_row = self . rows [ az ] <EOL> if not approx_equal ( az_tableau_row . constant , <NUM_LIT:0.0> ) : <EOL> self . remove_row ( az ) <EOL> self . remove_column ( av ) <EOL> raise RequiredFailure ( ) <EOL> e = self . rows . get ( av ) <EOL> if e is not None : <EOL> if e . is_constant : <EOL> self . remove_row ( av ) <EOL> self . remove_row ( az ) <EOL> return <EOL> entry_var = e . any_pivotable_variable ( ) <EOL> self . pivot ( entry_var , av ) <EOL> assert av not in self . rows <EOL> self . remove_column ( av ) <EOL> self . remove_row ( az ) <EOL> def try_adding_directly ( self , expr ) : <EOL> subject = self . choose_subject ( expr ) <EOL> if subject is None : <EOL> return False <EOL> expr . new_subject ( subject ) <EOL> if subject in self . columns : <EOL> self . substitute_out ( subject , expr ) <EOL> self . add_row ( subject , expr ) <EOL> return True <EOL> def choose_subject ( self , expr ) : <EOL> subject = None <EOL> found_unrestricted = False <EOL> found_new_restricted = False <EOL> retval_found = False <EOL> retval = None <EOL> for v , c in expr . terms . items ( ) : <EOL> if found_unrestricted : <EOL> if not v . is_restricted : <EOL> if v not in self . columns : <EOL> retval_found = True <EOL> retval = v <EOL> break <EOL> else : <EOL> if v . is_restricted : <EOL> if not found_new_restricted and not v . is_dummy and c < <NUM_LIT:0> : <EOL> col = self . columns . get ( v ) <EOL> if col == None or ( len ( col ) == <NUM_LIT:1> and self . objective in self . columns ) : <EOL> subject = v <EOL> found_new_restricted = True <EOL> else : <EOL> subject = v <EOL> found_unrestricted = True <EOL> if retval_found : <EOL> return retval <EOL> if subject : <EOL> return subject <EOL> coeff = <NUM_LIT:0.0> <EOL> for v , c in expr . terms . items ( ) : <EOL> if not v . is_dummy : <EOL> retval_found = True <EOL> retval = None <EOL> break <EOL> if not v in self . columns : <EOL> subject = v <EOL> coeff = c <EOL> if retval_found : <EOL> return retval <EOL> if not approx_equal ( expr . constant , <NUM_LIT:0.0> ) : <EOL> raise RequiredFailure ( ) <EOL> if coeff > <NUM_LIT:0> : <EOL> expr = expr * - <NUM_LIT:1> <EOL> return subject <EOL> def delta_edit_constant ( self , delta , plus_error_var , minus_error_var ) : <EOL> expr_plus = self . rows . get ( plus_error_var ) <EOL> if expr_plus is not None : <EOL> expr_plus . constant = expr_plus . constant + delta <EOL> if expr_plus . constant < <NUM_LIT:0.0> : <EOL> self . infeasible_rows . add ( plus_error_var ) <EOL> return <EOL> expr_minus = self . rows . get ( minus_error_var ) <EOL> if expr_minus is not None : <EOL> expr_minus . constant = expr_minus . constant - delta <EOL> if expr_minus . constant < <NUM_LIT:0> : <EOL> self . infeasible_rows . add ( minus_error_var ) <EOL> return <EOL> try : <EOL> for basic_var in self . columns [ minus_error_var ] : <EOL> expr = self . rows [ basic_var ] <EOL> c = expr . coefficient_for ( minus_error_var ) <EOL> expr . constant = expr . constant + ( c * delta ) <EOL> if basic_var . is_restricted and expr . constant < <NUM_LIT:0> : <EOL> self . infeasible_rows . add ( basic_var ) <EOL> except KeyError : <EOL> pass <EOL> def dual_optimize ( self ) : <EOL> z_row = self . rows . get ( self . objective ) <EOL> while self . infeasible_rows : <EOL> exit_var = self . infeasible_rows . pop ( ) <EOL> entry_var = None <EOL> expr = self . rows . get ( exit_var ) <EOL> if expr : <EOL> if expr . constant < <NUM_LIT:0> : <EOL> ratio = float ( '<STR_LIT>' ) <EOL> for v , cd in expr . terms . items ( ) : <EOL> if cd > <NUM_LIT:0> and v . is_pivotable : <EOL> zc = z_row . coefficient_for ( v ) <EOL> r = zc / cd <EOL> if r < ratio : <EOL> entry_var = v <EOL> ratio = r <EOL> if ratio == float ( '<STR_LIT>' ) : <EOL> raise InternalError ( "<STR_LIT>" ) <EOL> self . pivot ( entry_var , exit_var ) <EOL> def optimize ( self , z_var ) : <EOL> self . optimize_count = self . optimize_count + <NUM_LIT:1> <EOL> z_row = self . rows [ z_var ] <EOL> entry_var = None <EOL> exit_var = None <EOL> while True : <EOL> objective_coeff = <NUM_LIT:0.0> <EOL> for v , c in sorted ( z_row . terms . items ( ) , key = lambda x : x [ <NUM_LIT:0> ] . name ) : <EOL> if v . is_pivotable and c < objective_coeff : <EOL> objective_coeff = c <EOL> entry_var = v <EOL> break ; <EOL> if objective_coeff >= - EPSILON or entry_var is None : <EOL> return <EOL> min_ratio = float ( '<STR_LIT>' ) <EOL> r = <NUM_LIT:0> <EOL> for v in self . columns [ entry_var ] : <EOL> if v . is_pivotable : <EOL> expr = self . rows [ v ] <EOL> coeff = expr . coefficient_for ( entry_var ) <EOL> if coeff < <NUM_LIT:0> : <EOL> r = - expr . constant / coeff <EOL> if r < min_ratio : <EOL> min_ratio = r <EOL> exit_var = v <EOL> if min_ratio == float ( '<STR_LIT>' ) : <EOL> raise RequiredFailure ( '<STR_LIT>' ) <EOL> self . pivot ( entry_var , exit_var ) <EOL> def pivot ( self , entry_var , exit_var ) : <EOL> if entry_var is None : <EOL> print ( "<STR_LIT>" ) <EOL> if exit_var is None : <EOL> print ( "<STR_LIT>" ) <EOL> p_expr = self . remove_row ( exit_var ) <EOL> p_expr . change_subject ( exit_var , entry_var ) <EOL> self . substitute_out ( entry_var , p_expr ) <EOL> self . add_row ( entry_var , p_expr ) <EOL> def reset_stay_constants ( self ) : <EOL> for p_var , m_var in self . stay_error_vars : <EOL> expr = self . rows . get ( p_var ) <EOL> if expr is None : <EOL> expr = self . rows . get ( m_var ) <EOL> if expr : <EOL> expr . constant = <NUM_LIT:0.0> <EOL> def set_external_variables ( self ) : <EOL> for v in self . external_parametric_vars : <EOL> if self . rows . get ( v ) : <EOL> continue <EOL> v . value = <NUM_LIT:0.0> <EOL> for v in self . external_rows : <EOL> expr = self . rows [ v ] <EOL> v . value = expr . constant <EOL> self . needs_solving = False <EOL> def insert_error_var ( self , cn , var ) : <EOL> constraint_set = self . error_vars . get ( var ) <EOL> if not constraint_set : <EOL> constraint_set = set ( ) <EOL> self . error_vars [ cn ] = constraint_set <EOL> constraint_set . add ( var ) <EOL> self . error_vars . setdefault ( var , set ( ) ) . add ( var ) </s>
