qp_solver.h

很多二维 三维几何计算算法 C++ 类库

  void  init_r_C(Tag_false /*is_nonnegative*/);
  void  init_r_S_B(Tag_true  /*is_nonnegative*/);
  void  init_r_S_B(Tag_false /*is_nonnegative*/);

  void  init_r_B_O();
  void  init_w();


  void  init_solution( );
  void  init_solution__b_C( Tag_true  has_no_inequalities);
  void  init_solution__b_C( Tag_false has_no_inequalities); 
  void  init_solution__b_C( bool has_no_inequalities) {
    if (has_no_inequalities)
      init_solution__b_C (Tag_true());
    else
      init_solution__b_C (Tag_false());
  }

  void  init_additional_data_members( );
    
  // function needed for set up of auxiliary problem for symbolic perturbation
  int  signed_leading_exponent( int row);
  // This is a variant of set_up_auxiliary_problem for symbolic perturbation
  // for the perturbed case
  void  set_up_auxiliary_problemI( Tag_true is_perturbed);

  void  set_up_auxiliary_problem();

  // transition (to phase II)
  void  transition( );
  void  transition( Tag_true  is_linear);
  void  transition( Tag_false is_linear);
    
  // pivot step
  void  pivot_step( );

  // pricing
  void  pricing( );

  template < class NT, class It >
  void  mu_j__linear_part_( NT& mu_j, int j, It lambda_it,
			    Tag_true  has_no_inequalities) const;
  template < class NT, class It >
  void  mu_j__linear_part_( NT& mu_j, int j, It lambda_it,
			    Tag_false has_no_inequalities) const;
  template < class NT, class It >
  void  mu_j__linear_part_( NT& mu_j, int j, It lambda_it,
			    bool has_no_inequalities) const {
    if (has_no_inequalities)
      mu_j__linear_part_ (mu_j, j, lambda_it, Tag_true());
    else
      mu_j__linear_part_ (mu_j, j, lambda_it, Tag_false());
  }


//   template < class NT, class It >
//   void  mu_j__quadratic_part_( NT& mu_j, int j, It x_it,
// 			       Tag_true  is_linear) const;
//   template < class NT, class It >
//   void  mu_j__quadratic_part_( NT& mu_j, int j, It x_it,
// 			       Tag_false is_linear) const;
//   template < class NT, class It >
//   void  mu_j__quadratic_part_( NT& mu_j, int j, It x_it,
// 			       Tag_false is_linear,
// 			       Tag_true  is_symmetric) const;
//   template < class NT, class It >
//   void  mu_j__quadratic_part_( NT& mu_j, int j, It x_it,
// 			       Tag_false is_linear,
// 			       Tag_false is_symmetric) const;

  template < class NT, class It >
  void  mu_j__slack_or_artificial_( NT& mu_j, int j, It lambda_it, 
				    const NT& dd,
				    Tag_true  has_no_inequalities) const;
  template < class NT, class It >
  void  mu_j__slack_or_artificial_( NT& mu_j, int j, It lambda_it, 
				    const NT& dd,
				    Tag_false has_no_inequalities) const;

  template < class NT, class It >
  void  mu_j__slack_or_artificial_( NT& mu_j, int j, It lambda_it,
				    const NT& dd,
				    bool has_no_inequalities) const {
    if (has_no_inequalities)
      mu_j__slack_or_artificial_ (mu_j, j, lambda_it, dd, Tag_true());
    else
      mu_j__slack_or_artificial_ (mu_j, j, lambda_it, dd, Tag_false());
  }

  // ratio test
  void  ratio_test_init( );
  void  ratio_test_init__A_Cj( Value_iterator A_Cj_it, int j,
			       Tag_true  has_no_inequalities);
  void  ratio_test_init__A_Cj( Value_iterator A_Cj_it, int j,
			       Tag_false has_no_inequalities);
  void  ratio_test_init__A_Cj( Value_iterator A_Cj_it, int j,
			       bool has_no_inequalities) {
    if (has_no_inequalities) 
      ratio_test_init__A_Cj (A_Cj_it, j, Tag_true());
    else
      ratio_test_init__A_Cj (A_Cj_it, j, Tag_false());
  }

  void  ratio_test_init__2_D_Bj( Value_iterator two_D_Bj_it, int j,
				 Tag_true  is_linear);
  void  ratio_test_init__2_D_Bj( Value_iterator two_D_Bj_it, int j,
				 Tag_false is_linear);
  void  ratio_test_init__2_D_Bj( Value_iterator two_D_Bj_it, int j,
				 Tag_false is_linear,
				 Tag_true  has_no_inequalities);
  void  ratio_test_init__2_D_Bj( Value_iterator two_D_Bj_it, int j,
				 Tag_false is_linear,
				 Tag_false has_no_inequalities);
  void  ratio_test_init__2_D_Bj( Value_iterator two_D_Bj_it, int j,
				 Tag_false is_linear,
				 bool has_no_inequalities) {
    if (has_no_inequalities)
      ratio_test_init__2_D_Bj( two_D_Bj_it, j, is_linear, Tag_true());
    else
      ratio_test_init__2_D_Bj( two_D_Bj_it, j, is_linear, Tag_false());
  }


  void  ratio_test_1( );
  void  ratio_test_1__q_x_O( Tag_true  is_linear);
  void  ratio_test_1__q_x_O( Tag_false is_linear);
  void  ratio_test_1__q_x_S( Tag_true  has_no_inequalities);
  void  ratio_test_1__q_x_S( Tag_false has_no_inequalities);
  void  ratio_test_1__q_x_S( bool has_no_inequalities) {
    if (has_no_inequalities)
      ratio_test_1__q_x_S (Tag_true());
    else
      ratio_test_1__q_x_S (Tag_false());
  }

  void  ratio_test_1__t_min_j(Tag_true  /*is_nonnegative*/);  
  void  ratio_test_1__t_min_j(Tag_false /*is_nonnegative*/);
    
  void  ratio_test_1__t_i( Index_iterator i_it, Index_iterator end_it,
			   Value_iterator x_it, Value_iterator   q_it,
			   Tag_true  no_check);
  void  ratio_test_1__t_i( Index_iterator i_it, Index_iterator end_it,
			   Value_iterator x_it, Value_iterator   q_it,
			   Tag_false  no_check);
    
  // replaces the above two functions
  void  ratio_test_1__t_min_B(Tag_true has_no_inequalities );
  void  ratio_test_1__t_min_B(Tag_false has_no_inequalities ); 
  void  ratio_test_1__t_min_B(bool has_no_inequalities ) {
    if (has_no_inequalities)
      ratio_test_1__t_min_B (Tag_true());
    else
      ratio_test_1__t_min_B (Tag_false());
  }
   
  void  ratio_test_1_B_O__t_i(Index_iterator i_it, Index_iterator end_it,
			      Value_iterator x_it, Value_iterator q_it,
			      Tag_true  /*is_nonnegative*/);
  void  ratio_test_1_B_O__t_i(Index_iterator i_it, Index_iterator end_it,
			      Value_iterator x_it, Value_iterator q_it,
			      Tag_false /*is_nonnegative*/);
  void  ratio_test_1_B_S__t_i(Index_iterator i_it, Index_iterator end_it,
			      Value_iterator x_it, Value_iterator q_it,
			      Tag_true  /*is_nonnegative*/);
  void  ratio_test_1_B_S__t_i(Index_iterator i_it, Index_iterator end_it,
			      Value_iterator x_it, Value_iterator q_it,
			      Tag_false /*is_nonnegative*/);
			     
  void  test_implicit_bounds_dir_pos(int k, const ET& x_k, const ET& q_k, 
				     int& i_min, ET& d_min, ET& q_min);
  void  test_implicit_bounds_dir_neg(int k, const ET& x_k, const ET& q_k, 
				     int& i_min, ET& d_min, ET& q_min);
  void  test_explicit_bounds_dir_pos(int k, const ET& x_k, const ET& q_k, 
				     int& i_min, ET& d_min, ET& q_min);
  void  test_explicit_bounds_dir_neg(int k, const ET& x_k, const ET& q_k, 
				     int& i_min, ET& d_min, ET& q_min);
  void  test_mixed_bounds_dir_pos(int k, const ET& x_k, const ET& q_k, 
				  int& i_min, ET& d_min, ET& q_min);
  void  test_mixed_bounds_dir_neg(int k, const ET& x_k, const ET& q_k, 
				  int& i_min, ET& d_min, ET& q_min);    
                                    
  void  ratio_test_1__t_j( Tag_true  is_linear);
  void  ratio_test_1__t_j( Tag_false is_linear);

  void  ratio_test_2( Tag_true  is_linear);
  void  ratio_test_2( Tag_false is_linear);
  void  ratio_test_2__p( Tag_true  has_no_inequalities);
  void  ratio_test_2__p( Tag_false has_no_inequalities);   
  void  ratio_test_2__p( bool has_no_inequalities) {
    if (has_no_inequalities)
      ratio_test_2__p (Tag_true());
    else
      ratio_test_2__p (Tag_false());
  }

  // update
  void  update_1( );
  void  update_1( Tag_true  is_linear);
  void  update_1( Tag_false is_linear);

  void  update_2( Tag_true  is_linear);
  void  update_2( Tag_false is_linear);

  void  replace_variable( );
  void  replace_variable( Tag_true  has_no_inequalities);
  void  replace_variable( Tag_false has_no_inequalities);
  void  replace_variable( bool has_no_inequalities) {
    if (has_no_inequalities)
      replace_variable (Tag_true());
    else
      replace_variable (Tag_false());
  }

  void  replace_variable_original_original( );
  // update of the vector r
  void  replace_variable_original_original_upd_r(Tag_true
						 /*is_nonnegative*/);
  void  replace_variable_original_original_upd_r(Tag_false
						 /*is_nonnegative*/);

  void  replace_variable_original_slack( );
  // update of the vector r
  void  replace_variable_original_slack_upd_r(Tag_true /*is_nonnegative*/);
  void  replace_variable_original_slack_upd_r(Tag_false /*is_nonnegative*/);

  void  replace_variable_slack_original( );
  // update of the vector r
  void  replace_variable_slack_original_upd_r(Tag_true /*is_nonnegative*/);
  void  replace_variable_slack_original_upd_r(Tag_false /*is_nonnegative*/);
    
  void  replace_variable_slack_slack( );
  // update of the vector r
  void  replace_variable_slack_slack_upd_r(Tag_true /*is_nonnegative*/);
  void  replace_variable_slack_slack_upd_r(Tag_false /*is_nonnegative*/);
    
  void  remove_artificial_variable_and_constraint( );
  // update of the vector r
  void  remove_artificial_variable_and_constraint_upd_r(Tag_true
							/*is_nonnegative*/);
  void  remove_artificial_variable_and_constraint_upd_r(Tag_false
							/*is_nonnegative*/);    
    
  void  expel_artificial_variables_from_basis( );
    
  // update that occurs only with upper bounding in ratio test step 1
  void  enter_and_leave_variable( );

  void  enter_variable( );
  // update of the vectors w and r
  void  enter_variable_original_upd_w_r(Tag_true /*is_nonnegative*/);
  void  enter_variable_original_upd_w_r(Tag_false /*is_nonnegative*/);
  void  enter_variable_slack_upd_w_r(Tag_true /*is_nonnegative*/);
  void  enter_variable_slack_upd_w_r(Tag_false /*is_nonnegative*/);
    
  void  leave_variable( );
  // update of the vectors w and r
  void  leave_variable_original_upd_w_r(Tag_true /*is_nonnegative*/);    
  void  leave_variable_original_upd_w_r(Tag_false /*is_nonnegative*/);
  void  leave_variable_slack_upd_w_r(Tag_true /*is_nonnegative*/);
  void  leave_variable_slack_upd_w_r(Tag_false /*is_nonnegative*/);
    
  void  z_replace_variable( );
  void  z_replace_variable( Tag_true has_no_inequalities);
  void  z_replace_variable( Tag_false has_no_inequalities);
  void  z_replace_variable( bool has_no_inequalities) {
    if (has_no_inequalities) 
      z_replace_variable (Tag_true());
    else
      z_replace_variable (Tag_false());
  }
    
  void  z_replace_variable_original_by_original( );
  // update of the vectors w and r
  void  z_replace_variable_original_by_original_upd_w_r(Tag_true 
							/*is_nonnegative*/);
  void  z_replace_variable_original_by_original_upd_w_r(Tag_false 
							/*is_nonnegative*/);
    
  void  z_replace_variable_original_by_slack( );
  // update of the vectors w and r    
  void  z_replace_variable_original_by_slack_upd_w_r(Tag_true 
						     /*is_nonnegative*/);
  void  z_replace_variable_original_by_slack_upd_w_r(Tag_false
						     /*is_nonnegative*/);
    
  void  z_replace_variable_slack_by_original( );
  // update of the vectors w and r
  void  z_replace_variable_slack_by_original_upd_w_r(Tag_true
						     /*is_nonnegative*/);
  void  z_replace_variable_slack_by_original_upd_w_r(Tag_false
						     /*is_nonnegative*/);
    
  void  z_replace_variable_slack_by_slack( );
  // update of the vectors w and r
  void  z_replace_variable_slack_by_slack_upd_w_r(Tag_true
						  /*is_nonnegative*/);
  void  z_replace_variable_slack_by_slack_upd_w_r(Tag_false
						  /*is_nonnegative*/);
    
  // update of the parts r_C and r_S_B
  void  update_r_C_r_S_B__j(ET& x_j);
  void  update_r_C_r_S_B__j_i(ET& x_j, ET& x_i);
  void  update_r_C_r_S_B__i(ET& x_i);
    
  // update of w and r_B_O 
  void  update_w_r_B_O__j(ET& x_j);
  void  update_w_r_B_O__j_i(ET& x_j, ET& x_i);
  void  update_w_r_B_O__i(ET& x_i);
    
    
  bool  basis_matrix_stays_regular( );

  // current solution
  void  compute_solution(Tag_true  /*is_nonnegative*/);
  void  compute_solution(Tag_false /*is_nonnegative*/);

  void  compute__x_B_S( Tag_false  has_no_inequalities,
			Tag_false /*is_nonnegative*/);
  void  compute__x_B_S( Tag_false  has_no_inequalities,
			Tag_true  /*is_nonnegative*/);
  void  compute__x_B_S( Tag_true  has_no_inequalities,
			Tag_false /*is_nonnegative*/);
  void  compute__x_B_S( Tag_true  has_no_inequalities,
			Tag_true  /*is_nonnegative*/);
  void  compute__x_B_S( bool  has_no_inequalities,
			Tag_true  is_nonnegative) {
    if (has_no_inequalities)
      compute__x_B_S (Tag_true(), is_nonnegative);
    else
      compute__x_B_S (Tag_false(), is_nonnegative);
  }
    
  void  compute__x_B_S( bool  has_no_inequalities,
			Tag_false  is_nonnegative) {
    if (has_no_inequalities)
      compute__x_B_S (Tag_true(), is_nonnegative);
    else
      compute__x_B_S (Tag_false(), is_nonnegative);
  }  

  void  multiply__A_S_BxB_O( Value_iterator in, Value_iterator out) const;
    
  ET    multiply__A_ixO(int row) const;
  void  multiply__A_CxN_O(Value_iterator out) const;
  bool  check_r_C(Tag_true  /*is_nonnegative*/) const;
  bool  check_r_C(Tag_false /*is_nonnegative*/) const;
    
  void  multiply__A_S_BxN_O(Value_iterator out) const;
  bool  check_r_S_B(Tag_true  /*is_nonnegative*/) const;
  bool  check_r_S_B(Tag_false /*is_nonnegative*/) const;
    
  void  multiply__2D_B_OxN_O(Value_iterator out) const;
  bool  check_r_B_O(Tag_true  /*is_nonnegative*/) const;
  bool  check_r_B_O(Tag_false /*is_nonnegative*/) const;
        
  void  multiply__2D_OxN_O(Value_iterator out) const;
  bool  check_w(Tag_true  /*is_nonnegative*/) const;
  bool  check_w(Tag_false /*is_nonnegative*/) const;
    
  // utility routines for QP's in nonstandard form:
  ET original_variable_value_under_bounds(int i) const;
  ET nonbasic_original_variable_value (int i) const;

public: 
  // for original variables
  ET variable_numerator_value(int i) const;
  ET unbounded_direction_value(int i) const;
  ET lambda_numerator(int i) const
  {
    // we use the vector lambda which conforms to C (basic constraints)
    CGAL_qpe_assertion (i >= 0);
    CGAL_qpe_assertion (i <= qp_m);
    if (no_ineq)
      return lambda[i];
    else {
      int k = in_C[i];     // position of i in C
      if (k != -1) 
	return lambda[k];
      else 
	return et0;
    }   
}

private:
  // check basis inverse
  bool  check_basis_inverse( );
  bool  check_basis_inverse( Tag_true  is_linear);