qp_full_exact_pricing.h

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

// Copyright (c) 1997-2007  ETH Zurich (Switzerland).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.3-branch/QP_solver/include/CGAL/QP_solver/QP_full_exact_pricing.h $
// $Id: QP_full_exact_pricing.h 38453 2007-04-27 00:34:44Z gaertner $
// 
//
// Author(s)     : Sven Schoenherr
//                 Bernd Gaertner <[e-mail]>
//                 Franz Wessendorp
//                 Kaspar Fischer

#ifndef CGAL_QP_FULL_EXACT_PRICING_H
#define CGAL_QP_FULL_EXACT_PRICING_H

// includes
#include <CGAL/QP_solver/QP_pricing_strategy.h>

CGAL_BEGIN_NAMESPACE

// =================
// class declaration
// =================
template < typename Q, typename ET, typename Tags >
class QP_full_exact_pricing;

// ===============
// class interface
// ===============
template < typename Q, typename ET, typename Tags >
class QP_full_exact_pricing : public QP_pricing_strategy<Q,ET,Tags> {

  // self
  typedef  QP_pricing_strategy<Q,ET,Tags>    Base;
  typedef  QP_full_exact_pricing<Q,ET,Tags>  Self;

  // types from the base class
  typedef  typename Tags::Is_nonnegative     Is_nonnegative;
  typedef  typename CGAL::QP_solver<Q,ET,Tags>    QP_solver;

 public:

  // creation
  QP_full_exact_pricing();

  // operations
  int  pricing(int& direction );
    
  // cleanup
  ~QP_full_exact_pricing() { };
    
 private:
  int pricing_helper(int& direction, Tag_true  /*is_in_standard_form*/);
  int pricing_helper(int& direction, Tag_false /*is_in_standard_form*/);
};

// ----------------------------------------------------------------------------

// =============================
// class implementation (inline)
// =============================

// construction
template < typename Q, typename ET, typename Tags >  inline
QP_full_exact_pricing<Q,ET,Tags>::
QP_full_exact_pricing()
  : QP_pricing_strategy<Q,ET,Tags>("full exact")
{ }
    
// operations
template < typename Q, typename ET, typename Tags >
int  QP_full_exact_pricing<Q,ET,Tags>::
pricing(int& direction )
{
  return (pricing_helper(direction, Is_nonnegative()));
}

template < typename Q, typename ET, typename Tags >
int  QP_full_exact_pricing<Q,ET,Tags>::
pricing_helper(int& /*direction*/, Tag_true /*is_in_standard_form*/)
{
  // get properties of quadratic program:
  int  w = this->solver().number_of_working_variables();

  // loop over all non-basic variables:
  int  j,  min_j  = -1;
  ET   mu, min_mu = this->et0;
  for (j = 0; j < w; ++j) {

    // variable non-basic?
    if (!this->solver().is_basic(j)) {
	
      // don't price artificial variables:
      if (this->solver().is_artificial(j)) {
	CGAL_qpe_debug { 
	  this->vout() << "mu_" << j << ": artificial [ not priced ]"
		       << std::endl;
	}
	continue;
      }

      // compute mu_j:
      mu = this->mu_j(j);

      CGAL_qpe_debug {
	this->vout() << "mu_" << j << ": " << mu << std::endl;
      }

      // new minimum?
      if (mu < min_mu) { min_j = j; min_mu = mu; }
    }
  }
  CGAL_qpe_debug { 
    this->vout() << std::endl;
  }

  // return index of entering variable:
  return min_j;
    
}

template < typename Q, typename ET, typename Tags >
int  QP_full_exact_pricing<Q,ET,Tags>::
pricing_helper(int& direction, Tag_false /*is_in_standard_form*/)
{
    
  // get properties of quadratic program:
  int  w = this->solver().number_of_working_variables();

  // loop over all non-basic variables:
  int  j,  min_j  = -1;
  // 
  ET   min_mu = this->et0;     // Note: for mu_j > 0 we will compare -mu_j and
			       // min_mu.
  for (j = 0; j < w; ++j) {

    // variable non-basic?
    if (!this->solver().is_basic(j)) {
	
      // don't price artificial variables:
      if (this->solver().is_artificial(j)) {
	CGAL_qpe_debug { 
	  this->vout() << "mu_" << j << ": artificial [ not priced ]"
		       << std::endl;
	}
	continue;
      }
      
      const ET mu = this->mu_j(j);
      // from pricing strategy base class
      price_dantzig (j, mu, this->et0, min_j, min_mu, direction);          
    }
  }
  CGAL_qpe_debug { 
    this->vout() << std::endl;
  }

  // return index of entering variable
  return min_j;
    
}


CGAL_END_NAMESPACE

#endif // CGAL_QP_FULL_EXACT_PRICING_H

// ===== EOF ==================================================================