#ifndef _LAGRANGE_H
#define	_LAGRANGE_H

#include <math.h>
#include "common.h"
#include "scpview.h"
#include "qsorter.h"



/** \brief Lagrangean heuristic type*/
typedef enum {
 /**Heuristic #1*/
 LAGRANGE_HEURISTIC_1=1,
 /**Heuristic #2*/
 LAGRANGE_HEURISTIC_2=2,
 /**Heuristic #3*/
 LAGRANGE_HEURISTIC_3=3,
 /**Heuristic #4*/
 LAGRANGE_HEURISTIC_4=4,
 /**Heuristic #5*/
 LAGRANGE_HEURISTIC_5=5
} HeuristicType;

#define LAGRANGE_ERROR -1

#ifdef	__cplusplus
extern "C" {
#endif

typedef struct _LagrangeSolver LagrangeSolver; 

/** \defgroup LAGRANGESOLVER Lagrangean heuristic for SCP
 *   Implementation of lagrangean heuristic for SCP based on the following
 *   article:
 *   INVESTIGATION OF LAGRANGIAN HEURISTICS FOR SET COVERING
 *   PROBLEMS by\n
 *   Techapichetvanich, Kavee\n
     Bricker, Dennis\n
 *   Department of Industrial Engineering,The University of Iowa,Iowa City, IA 52242,USA,May 1993
 @{*/

    
/** \brief State of Lagrangean heuristic*/
struct _LagrangeSolver {

    /** \brief View to the underlying problem*/
    SCPView* problemView;

    /** \brief Maximum lower bound found*/
    float ZMAX;
    /** \brief Best feasible solution*/
    float ZUB;
    /** \brief Current solution of original problem*/
    float ZLB;
    /** \brief Vector of lagrangian multipliers*/
    float* t;
    /** \brief Vector of lower bounds if j-th column is in the solution*/
    float* p;
    /** \brief Vector of the LRP solution*/
    unsigned char* x;
    /** \brief Vector of the current feasible solution*/
    unsigned char* xf;

    /** \brief Vector of the best ever feasible solution*/
    unsigned char* xbest;

    /** \brief Vector of reduced costs*/
    float* reducedCosts;

    /** \brief Temporary vector of modified or normal reduced costs*/
    float* modifiedReducedCosts;

    
    /** \brief Subgradient of dual problem*/
    int* G;
    /** \brief Iteration counter*/
    int iterations;
    /** \brief Supplementary iteration counter*/
    int sup_iterations;
    /** \brief Iteration multiplier*/
    float iteration_multiplier;
    /** \brief Supplementary ZMAX*/
    float sup_ZMAX;

    /** \brief List of available columns*/
    IList* availCols;

    /** \brief Used type of lagrangean heuristic*/
    HeuristicType heuristicType;
    
    /** \brief How many iterations were performed*/
    int stIterationCount;

    /** \Whether to stop if ZMAX was not improved last 30 iterations*/
    unsigned char fastCancel;

};

/** \brief Create new Lagrangean heuristic
 *  \param p View to the underlying problem that will be solved
 *  \param type Type of lagrangean heuristic
 *  \return New Lagrangean heuristic or NULL
 */
LagrangeSolver* lagrangesolver_new(SCPView* pv,HeuristicType type);



/** \brief Solve the SCP using lagrangian heuristic
 *  \param maxLowerBound Desired maximum lower bound. If that bound
 *   is reached, algorithm is stopped
 */
int lagrangesolver_solve(LagrangeSolver* s,int maxLowerBound,unsigned char fastCancel);

/** \brief 'Initialize' step of the algorithm*/
void lagrangesolver_initialize(LagrangeSolver* s);

/** \brief 'Solve LRP' step of the algorithm*/
void lagrangesolver_solve_lrp(LagrangeSolver* s);

/** \brief 'Solve original SCP' step of the algorithm */
void lagrangesolver_solve_original(LagrangeSolver* s);

/** \brief 'Remove columns' step of the algorithm*/
void lagrangesolver_removecolumns(LagrangeSolver* s);

/** \brief 'Subgradient' step of the algorithm
 *  \return quadratic sum of subgradient
 */
int lagrangesolver_subgradient(LagrangeSolver* s);

/** \brief 'Iteration' step of the algorithm
 */
int lagrangesolver_iteration(LagrangeSolver* s,int gqsum);


/** Beasley's lagrangean heuristic*/
void lagrangesolver_ha_beasley(LagrangeSolver* s);

/** Lagrangean heuristics #2 or #3
 *  \param maxCandidates. Maximum number of candidates that can cover uncovered row
 *  \param modifiedCost 0. Reduced costs are not modified. 1 Reduced costs are modified.
 */
void lagrangesolver_ha_reduced_costs_a(LagrangeSolver* s,int maxCandidates,unsigned char modifiedCost);

/** Lagrangean heuristics #4 or #5
 *\param maxCandidates. Maximum number of candidates that can cover uncovered row
 * \param modifiedCost 0. Reduced costs are not modified. 1 Reduced costs are modified.
 */
void lagrangesolver_ha_reduced_costs_b(LagrangeSolver* s,int maxCandidates,unsigned char modifiedCost);


/** \brief Initial preprocessing. Sort rows and columns according to the
     algorithm specifications
 */
void lagrangesolver_sort(LagrangeSolver* s);

/** \brief Calculate reduced cost of column
 *  \param columnIndex Index of column
 *  \return Reduced cost
 */
float lagrangesolver_get_reduced_cost(LagrangeSolver* s,int columnIndex);

/** \brief Supplementary comparation function*/
int lagrangesolver_compare_reduced_cost(SCPView* v,int c1,int c2,void* miscData);

/** \brief Alternative supplementary comparation function*/
int lagrangesolver_compare_reduced_cost2(SCPView* v,int c1,int c2,void* miscData);

/** \brief Supplementary comparation function*/
int lagrangesolver_compare_columns(SCPView* v,int c1,int c2,void* miscData);

/** \brief Supplementary comparation function*/
int lagrangesolver_compare_rows(SCPView* v,int c1,int c2,void* miscData);

/** \brief Update ZUB and store the best ever found feasible solution*/
void lagrangesolver_update_zub(LagrangeSolver* s,float candZUB);

/** \brief Print state of Lagrangean heuristic*/
void lagrangesolver_print(LagrangeSolver* s);

/** \brief Delete Lagrangean heuristic*/
 void lagrangesolver_delete(LagrangeSolver* s);

#ifdef	__cplusplus
}
#endif

#endif	/* _LAGRANGE_H */

/**@}*/
