cbcintlinprog added

1 files changed, 464 insertions, 0 deletions

diff --git a/thirdparty/linux/include/coin/Cgl012cut.hpp b/thirdparty/linux/include/coin/Cgl012cut.hpp
new file mode 100644
index 0000000..2814b0a
--- /dev/null
+++ b/thirdparty/linux/include/coin/Cgl012cut.hpp
@@ -0,0 +1,464 @@
+// $Id: Cgl012cut.hpp 1149 2013-10-21 18:23:53Z tkr $
+// 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