Cgl012cut.hpp

// $Id$
// Copyright (C) 2010, International Business Machines
// Corporation and others.  All Rights Reserved.
// This code is licensed under the terms of the Eclipse Public License (EPL).
/** @file 012cut.h Include file for C coded 0-1/2 separator */
#ifndef CGL012CUT
#define CGL012CUT
#include <cstdio>
#include <cstdlib>
#include <cmath>

#define CGL_NEW_SHORT
#ifndef CGL_NEW_SHORT
typedef  /* arc */
   struct arc_st
{
   int              len;            /* length of the arc */
   struct node_st   *head;           /* head node */
}
  arc;

typedef  /* node */
   struct node_st
{
   arc              *first;           /* first outgoing arc */
   int              dist;	      /* tentative shortest path length */
   struct node_st   *parent;          /* parent pointer */
   struct node_st   *next;            /* next node in queue */
   struct node_st   *prev;            /* previous node in queue */
   int               status;          /* status of node */
   int               temp;            /* for temporary labels */
   int               index;           /* index of the node in the graph */
} node;
#endif
typedef struct 
{
  int length; // Length of arc
  int to; // To node
} cgl_arc;

typedef struct
{
  cgl_arc * firstArc; // First outgoing arc 
  int parentNode; // Parent node in shortest path 
  int index; // Which node I am
  int distanceBack; // Distance back to source
} cgl_node;

typedef struct 
{
  int nnodes; // Number of nodes in graph
  int narcs; // Number of arcs in graph
  cgl_node * nodes;
  cgl_arc * arcs;
} cgl_graph;
/* #define PRINT */
/* #define PRINT_CUTS */
#define REDUCTION

typedef struct {
int mr; /* number of rows in the ILP matrix */
int mc; /* number of columns in the ILP matrix */
int mnz; /* number of nonzero's in the ILP matrix */
int *mtbeg; /* starting position of each row in arrays mtind and mtval */
int *mtcnt; /* number of entries of each row in arrays mtind and mtval */
int *mtind; /* column indices of the nonzero entries of the ILP matrix */
int *mtval; /* values of the nonzero entries of the ILP matrix */
int *vlb; /* lower bounds on the variables */
int *vub; /* upper bounds on the variables */
int *mrhs; /* right hand sides of the constraints */
char *msense; /* senses of the constraints: 'L', 'G' or 'E' */
const double *xstar; /* current optimal solution of the LP relaxation */
} ilp; 

typedef struct {
int mr; /* number of rows in the parity ILP matrix */
int mc; /* number of columns in the parity ILP matrix */
int mnz; /* number of 1's in the parity ILP matrix */
int *mtbeg; /* starting position of each row in arrays mtind and mtval */
int *mtcnt; /* number of entries of each row in arrays mtind and mtval */
int *mtind; /* column indices of the 1's of the parity ILP matrix */
short int *mrhs; /* right hand side parity of the constraints */
double *xstar; /* current optimal solution of the LP relaxation */
double *slack; /* slack of the constraints w.r.t. xstar */
short int *row_to_delete; /* flag for marking rows not to be considered */
short int *col_to_delete; /* flag for marking columns not to be considered */
int *gcd; /* greatest common divisor of each row in the input ILP matrix */
short int *possible_weak; /* possible weakening types of each column */
short int *type_even_weak; /* type of even weakening of each column 
                              (lower or upper bound weakening) */
short int *type_odd_weak; /* type of odd weakening of each column 
                              (lower or upper bound weakening) */
double *loss_even_weak; /* loss for the even weakening of each column */
double *loss_odd_weak; /* loss for the odd weakening of each column */
double *min_loss_by_weak; /* minimum loss for the weakening of each column */
} parity_ilp; 

typedef struct {
int nweak; /* number of variables weakened */
int *var; /* list of variables weakened */
short int *type; /* type of weakening (lower or upper bound weakening) */
} info_weak;

typedef struct {
int endpoint1, endpoint2; /* endpoints of the edge */
double weight; /* edge weight */
short int parity; /* edge parity (even or odd) */
int constr; /* constraint associated with the edge */
info_weak *weak; /* weakening information */
} edge;

typedef struct {
int nnodes; /* number of nodes */
int nedges; /* number of edges */
int *nodes; /* indexes of the ILP columns corresponding to the nodes */
int *ind; /* indexes of the nodes corresponding to the ILP columns */
edge **even_adj_list; /* pointers to the even edges */ 
edge **odd_adj_list; /* pointers to the odd edges */ 
} separation_graph;

#ifndef CGL_NEW_SHORT
typedef struct {
int nnodes; /* number of nodes */
int narcs; /* number of arcs */
node *nodes; /* array of the nodes - see "types_db.h" */ 
arc *arcs; /* array of the arcs - see "types_db.h" */ 
} auxiliary_graph;
#else
typedef struct {
int nnodes; /* number of nodes */
int narcs; /* number of arcs */
cgl_node *nodes; /* array of the nodes - see "types_db.h" */ 
cgl_arc *arcs; /* array of the arcs - see "types_db.h" */ 
} auxiliary_graph;
#endif

typedef struct {
long dist; /* distance from/to root */
int pred; /* index of the predecessor */
} short_path_node;

typedef struct {
double weight; /* overall weight of the cycle */
int length; /* number of edges in the cycle */
edge **edge_list; /* list of edges in the cycle */
} cycle;

typedef struct {
int cnum; /* overall number of cycles */
cycle **list; /* pointers to the cycles in the list */
} cycle_list;

typedef struct {
int n_of_constr; /* number of constraints combined to get the cut */
int *constr_list; /* list of the constraints combined */
short int *in_constr_list; /* flag saying whether a given constraint is
                              in the list of constraints of the cut (IN)
                              or not (OUT) */
int cnzcnt; /* overall number of nonzero's in the cut */
int *cind; /* column indices of the nonzero entries of the cut */
int *cval; /* values of the nonzero entries of the cut */
int crhs; /* right hand side of the cut */
char csense; /* sense of the cut: 'L', 'G' or 'E' */
double violation; /* violation of the cut w.r.t. the current LP solution */
} cut;

typedef struct {
int cnum; /* overall number of cuts */
cut **list; /* pointers to the cuts in the list */
} cut_list;

typedef struct {
int n_of_constr; /* number of constraints combined to get the cut */
int *constr_list; /* list of the constraints combined */
int code; /* identifier of the cut */
int n_it_violated; /* number of consecutive iterations (starting from the
                      last and going backward) in which the cut was
                      violated by the LP solution */
int it_found; /* iteration in which the cut was separated */
double score; /* score of the cut, used to choose wich cut should be 
                 added to the current LP (if any) */
} pool_cut;
 
typedef struct {
int cnum; /* overall number of cuts */
pool_cut **list; /* pointers to the cuts in the list */
int *ncod; /* number of cuts with a given code in the pool */
} pool_cut_list;

typedef struct {
int *ccoef; /* coefficients of the cut */
int crhs; /* right hand side of the cut */
int pool_index; /* index of the cut in the pool */
double score; /* cut score (to be maximized) */
} select_cut;

typedef struct {
int n_it_zero; /* number of consecutive iterations (starting from the
                   last and going backward) in which each variable took
                   the value 0 in the LP solution */
} log_var;
/** 012Cut Generator Class

 This class is to make Cgl01cut thread safe etc
*/

class Cgl012Cut {
 
public:

  /**@name Generate Cuts */
  //@{
int sep_012_cut(
/*
  INPUT parameters:
*/
int mr, /* number of rows in the ILP matrix */
int mc, /* number of columns in the ILP matrix */
int mnz, /* number of nonzero's in the ILP matrix */
int *mtbeg, /* starting position of each row in arrays mtind and mtval */
int *mtcnt, /* number of entries of each row in arrays mtind and mtval */
int *mtind, /* column indices of the nonzero entries of the ILP matrix */
int *mtval, /* values of the nonzero entries of the ILP matrix */
int *vlb, /* lower bounds on the variables */
int *vub, /* upper bounds on the variables */
int *mrhs, /* right hand sides of the constraints */
char *msense, /* senses of the constraints: 'L', 'G' or 'E' */
const double *xstar, /* current optimal solution of the LP relaxation */
bool aggressive, /* flag asking whether as many cuts as possible are
			 required on output (TRUE) or not (FALSE) */
/*
  OUTPUT parameters (the memory for the vectors is allocated INTERNALLY
  by the procedure: if some memory is already allocated, it is FREED):
*/
int *cnum, /* number of violated 0-1/2 cuts identified by the procedure */
int *cnzcnt, /* overall number of nonzero's in the cuts */
int **cbeg, /* starting position of each cut in arrays cind and cval */
int **ccnt, /* number of entries of each cut in arrays cind and cval */
int **cind, /* column indices of the nonzero entries of the cuts */
int **cval, /* values of the nonzero entries of the cuts */
int **crhs, /* right hand sides of the cuts */
char **csense /* senses of the cuts: 'L', 'G' or 'E' */
/* 
  NOTE that all the numerical input/output vectors are INTEGER (with
  the exception of xstar), since the procedure is intended to work
  with pure ILP's, and that the ILP matrix has to be given on input
  in ROW format.
*/
		);
void ilp_load(
	      int mr, /* number of rows in the ILP matrix */
	      int mc, /* number of columns in the ILP matrix */
	      int mnz, /* number of nonzero's in the ILP matrix */
	      int *mtbeg, /* starting position of each row in arrays mtind and mtval */
	      int *mtcnt, /* number of entries of each row in arrays mtind and mtval */
	      int *mtind, /* column indices of the nonzero entries of the ILP matrix */
	      int *mtval, /* values of the nonzero entries of the ILP matrix */
	      int *vlb, /* lower bounds on the variables */
	      int *vub, /* upper bounds on the variables */
	      int *mrhs, /* right hand sides of the constraints */
	      char *msense /* senses of the constraints: 'L', 'G' or 'E' */
	      );
void free_ilp();
/* alloc_parity_ilp: allocate the memory for the parity ILP data structure */

void alloc_parity_ilp(
		      int mr, /* number of rows in the ILP matrix */
		      int mc, /* number of columns in the ILP matrix */
		      int mnz /* number of nonzero's in the ILP matrix */
		      );
void free_parity_ilp();
  void initialize_log_var();
/* free_log_var */
  void free_log_var();
private:
/* best_weakening: find the best upper/lower bound weakening of a set
   of variables */

int best_weakening(
		   int n_to_weak, /* number of variables to weaken */
int *vars_to_weak, /* indices of the variables to weaken */
short int original_parity, /* original parity of the constraint to weaken */
double original_slack, /* original slack of the constraint to weaken */
double *best_even_slack, /* best possible slack of a weakened constraint 
			   with even right-hand-side */
double *best_odd_slack, /* best possible slack of a weakened constraint 
			  with odd right-hand-side */
info_weak **info_even_weak, /* weakening information about the best possible
			       even weakened constraint */ 
info_weak **info_odd_weak, /* weakening information about the best possible
			      odd weakened constraint */ 
short int only_odd, /* flag which tells whether only an odd weakening is of
		       interest (TRUE) or both weakenings are (FALSE) */
short int only_viol /* flag which tells whether only an inequality of
			slack smaller than MAX_SLACK is of interest (TRUE)
			otherwise (FALSE) */
		   );

/* best_cut: find the coefficients, the rhs and the violation of the
   best possible cut that can be obtained by weakening a given set of
   coefficients to even and a rhs to odd, dividing by 2 and rounding */

short int best_cut(
		   int *ccoef, /* vector of the coefficients */
		   int *crhs, /* pointer to rhs value */
		   double *violation, /* violation of the cut */
		   short int update, /* TRUE/FALSE: if TRUE, the new ccoef and crhs are 
					given on output */ 
		   short int only_viol /* flag which tells whether only an inequality of
			slack smaller than MAX_SLACK is of interest (TRUE)
			otherwise (FALSE) */
			      );
/* get_cut: extract a hopefully violated cut from an odd cycle of the
   separation graph */

cut *get_cut(
	     cycle *s_cyc /* shortest odd cycles identified in the separation graph */
	     );

/* update_log_var: update the log information for the problem variables */
  void update_log_var();

/* basic_separation: try to identify violated 0-1/2 cuts by using the 
   original procedure described in Caprara and Fischetti's MP paper */

  cut_list *basic_separation();

/* score_by_moving: compute the score of the best cut obtainable from 
   the current local search solution by inserting/deleting a constraint */

double score_by_moving(
		       int i, /* constraint to be moved */
		       short int itype, /* type of move - ADD or DEL */
		       double thresh /* minimum value of an interesting score */
		       );
/* modify_current: update the current local search solution by inserting/
   deleting a constraint */

void modify_current(
		    int i, /* constraint to be moved */
		    short int itype /* type of move - ADD or DEL */
		    );

/* best neighbour: find the cut to be added/deleted from the current
   solution among those allowed by the tabu rules */

  short int best_neighbour(cut_list *out_cuts /* list of the violated cuts found */);

/* add_tight_constraint: initialize the current cut by adding a tight 
   constraint to it */
       
  void add_tight_constraint();

/* tabu_012: try to identify violated 0-1/2 cuts by a simple tabu search
   procedure adapted from that used by Battiti and Protasi for finding
   large cliques */

  cut_list *tabu_012();
/* initialize: initialize the data structures for local search */

  void initialize();
/* restart: perform a restart of the search - IMPORTANT: in the current
   implementation vector last_moved is not cleared at restart */
       
  void restart(short int failure /* flag forcing the restart if some trouble occurred */);
  void print_constr(int i /* constraint to be printed */);
  void print_parity_ilp();

/* get_parity_ilp: construct an internal data structure containing all the 
   information which can be useful for  0-1/2 cut separation */

  void get_parity_ilp();
/* initialize_sep_graph: allocate and initialize the data structure
   to contain the information associated with a separation graph */

  separation_graph *initialize_sep_graph();
  void print_cut(cut *v_cut);
/* get_ori_cut_coef: get the coefficients of a cut, before dividing by 2 and
   rounding, starting from the list of the constraints combined to get 
   the cut */

short int get_ori_cut_coef(
			   int n_of_constr, /* number of constraints combined */
			   int *constr_list, /* list of the constraints combined */
			   int *ccoef, /* cut left hand side coefficients */
			   int *crhs, /* cut right hand side */
			   short int only_viol /* flag which tells whether only an inequality of
			slack smaller than MAX_SLACK is of interest (TRUE)
			otherwise (FALSE) */
			   );
/* define_cut: construct a cut data structure from a vector of
   coefficients and a right-hand-side */

cut *define_cut(
		int *ccoef, /* coefficients of the cut */
		int crhs /* right hand side of the cut */
		);

/* cut_score: define the score of a (violated) cut */

double cut_score(
		 int *ccoef, /* cut left hand side coefficients */
		 int crhs, /* cut right hand side */
		 double viol, /* cut violation */
		 short int only_viol /* flag which tells whether only an inequality of
			slack smaller than MAX_SLACK is of interest (TRUE)
			otherwise (FALSE) */
		 );
/* get_current_cut: return a cut data type with the information about
   the current cut of the search procedure */

  cut *get_current_cut();
/* print_cur_cut: display cur_cut on output */

  void print_cur_cut();
  void print_cut_list(cut_list *cuts);
  //@}
public:
  /**@name Constructors and destructors */
  //@{
  /// Default constructor 
  Cgl012Cut ();
 
  /// Copy constructor 
  Cgl012Cut (
    const Cgl012Cut &);

  /// Assignment operator 
  Cgl012Cut &
    operator=(
    const Cgl012Cut& rhs);
  
  /// Destructor 
  virtual ~Cgl012Cut ();
  //@}

private:
  
  // Private member methods
   
  /**@name Private methods */
  //@{
  //@}
  
  
  /**@name Private member data */
  //@{

ilp *inp_ilp; /* input ILP data structure */
parity_ilp *p_ilp; /* parity ILP data structure */
int iter;
double gap;
double maxgap;
int errorNo;
int sep_iter; /* number of the current separation iteration */
log_var **vlog; /* information about the value attained
				  by the variables in the last iterations,
				  used to possibly set to 0 some coefficient
				  > 0 in a cut to be added */ 
bool aggr; /* flag saying whether as many cuts as possible are required
		   from the separation procedure (TRUE) or not (FALSE) */
  //@}
};
#endif