//************************************************************************
//* retroLP solves linear programs using the simplex method.             *
//* Copyright (C) 2001, 2003, 2005 Gavriel Yarmish & Richard Van Slyke.  *
//* For further information, and gpl licensing, see the end of this file.*
//************************************************************************/

// IMPORTANT! IT IS IMPORTANT TO MAINTAIN CONSISTANCY AMONG
// PIVOT (used in refresh), PIVOT_PLUS (used in regular iteration,
// AND CHOOSE_COLUMN (used if no available column from PIVOT_PLUS)

#include <math.h>
#include <stdlib.h>
#include <float.h>
#include "simplex.h"
#include "params.h"
//#include "makedll.h"
//#include "stdafx.h"

extern long cntnfx, cntcc;
long choose_column(LP_state *, double *,short * , double);
long choose_row(LP_state *, long , short, double *, iter_result *, double);

//============ CHOOSE_COLUMN ===========
// Implements three column choice rules;
// For ccr = 1 we use the classical column with extreme reduced cost
// For ccr = 2 we use steepest edge pricing
// For ccr = 3 we use the column that results in the greatest
//    improvement in the objective (except when encountering fixed
//    variables in basis. We pivot those in right away. (This one
//    is not being used now.)
 
long choose_column
//			 long choose_column
(
 LP_state *lp,        // Linear programming data structure
 double *val,         // Value of best column
 short *up_flag,      // If true we wish to increase the non-basic
 double delta         // EXPAND tolerance used only for greatest
                      // improvement
 )
{
  long jp = 0, i, j;
  switch(ccr)
    {
    case 1:
      //classical (Dantzig) column choice rule
      double temp;
      *val=epsc;
      for (j=1;j<=lp->n;j++) if(lp->nrange[j]!=ATBOTH)// Not interested
	// in fixed non-basic variable at proper value
	{
	  // Do we want to (can we) increase this non-basic variable?
	  // If so, is this column better than previous?
	  if(((temp=lp->a[j][lp->mm]) > *val) && (lp->nrange[j]!=ATUPPER))
            {
	      *val=temp;
	      jp=j;
	      *up_flag = TRUE;
            }
	  // Do we want to (can we) decrease this non-basic variable?
	  // If so, is this column better than previous?
	  else if(temp < -*val && lp->nrange[j]!=ATLOWER)
            {
	      *val=-temp;
	      jp=j;
	      *up_flag = FALSE;
            }
	}
      // Test to see if any column accepted
      if(jp==0)*val=0.0;
      return jp;
      break;
    case 2:
      //steepest edge pricing
      double num, den;
      *val = -DBL_MAX;
      for (j=1;j<=lp->n;j++) if(lp->nrange[j]!=ATBOTH)
	{
	  cntnfx++;  // counts the number that are not fixed and non-basic
	  // Do we want to (can we) increase this non-basic variable?
	  if(lp->a[j][lp->mm]>epsc && lp->nrange[j]!=ATUPPER)
            // If so, is this column better than previous?
            {
	      num = lp->a[j][lp->mm];
	      num = num * num;
	      den = 1.0;
	      for( i=1; i<=lp->m; i++ )
		den+=lp->a[j][i]*lp->a[j][i];
	      if (num/den > *val)
		{
		  *val=num/den;
		  jp=j;
		  *up_flag = TRUE;
		}
            }
	  // Do we want to (can we) decrease this non-basic variable?
	  else
	    {
	      if(lp->a[j][lp->mm] < -epsc && lp->nrange[j]!=ATLOWER)
		// If so, is this column better than previous?
		{
		  num = -lp->a[j][lp->mm];
		  num = num * num;
		  den = 1.0;
		  for( i=1; i<=lp->m; i++ )
		    den+=lp->a[j][i]*lp->a[j][i];
		  if (num/den > *val)
		    {
		      *val=num/den;
		      jp=j;
		      *up_flag = FALSE;
		    }
		}
	      else cntcc++; // This counts the number of times
	      // that the column choice rule is not used
	    }
	}
      if(!jp)*val=0.0;
      return jp;
      
      break;
 
    case 3:
      //maximum change in objective
      double dx;
      iter_result nonbasicflag;
      *val = -DBL_MAX;
      for (j=1;j<=lp->n;j++) if(lp->nrange[j]!=ATBOTH)
	{
	  cntnfx++;  // counts the number that are not fixed and non-basic
	  // Do we want to (can we) increase this non-basic variable?
	  if(lp->a[j][lp->mm]>epsc  && lp->nrange[j]!=ATUPPER)
            // If so, is this column better than previous?
            {
	      i = choose_row(lp,j,TRUE, &dx,&nonbasicflag, delta);
	      if(i < 0)
		{
		  *up_flag = TRUE;
		  *val = DBL_MAX;
		  return j; // Unbounded
		}
	      if (lp->a[j][lp->mm]*dx > *val)
		{
		  *val=lp->a[j][lp->mm]*dx;
		  jp=j;
		  *up_flag = TRUE;
		}
            }
	  // Do we want to (can we) decrease this non-basic variable?
	  else if(lp->a[j][lp->mm]<-epsc && lp->nrange[j]!=ATLOWER)
	    // If so, is this column better than previous?
            {
              i = choose_row(lp,j,FALSE, &dx,&nonbasicflag, delta);
              if(i < 0)
		{
		  *up_flag = FALSE;
		  *val = DBL_MAX;
		  return j; // Unbounded
		}
	      if (lp->a[j][lp->mm]*dx > *val)
		{
		  *val=lp->a[j][lp->mm]*dx;
		  jp=j;
		  *up_flag = FALSE;
		}
	    }
	  else cntcc++; // This counts the number of times
	  // that the column choice rule is not used
	}
      if(!jp)*val=0.0;
      return jp;
      break;
    }
  // This should not be reached
  assert(0);
  return -2;
}

/************************************************************************
* retroLP solves linear programs using the simplex method.             *
* Copyright (C) 2001, 2003, 2005 Gavriel Yarmish & Richard Van Slyke.  *
*                                                                      *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or    *
* (at your option) any later version.                                  *
*                                                                      *
* This program is distributed in the hope that it will be useful,      *
* but WITHOUT ANY WARRANTY; without even the implied warranty of       *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the        *
* GNU General Public License for more details.                         *
*                                                                      *
* You should have received a copy of the GNU General Public License    *  
* along with this program; if not, write to the Free Software          *
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,           *
*                                                                      *
************************************************************************/
