glpios.h

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

/* glpios.h (integer optimization suite) */

/***********************************************************************
*  This code is part of GLPK (GNU Linear Programming Kit).
*
*  Copyright (C) 2000,01,02,03,04,05,06,07,08,2009 Andrew Makhorin,
*  Department for Applied Informatics, Moscow Aviation Institute,
*  Moscow, Russia. All rights reserved. E-mail: <[e-mail]>.
*
*  GLPK 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 3 of the License, or
*  (at your option) any later version.
*
*  GLPK 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 GLPK. If not, see <http://www.gnu.org/licenses/>.
***********************************************************************/

#ifndef _GLPIOS_H
#define _GLPIOS_H

#define _GLP_TREE
typedef struct glp_tree glp_tree;

#include "glpapi.h"
#include "glpscg.h"

typedef struct IOSLOT IOSLOT;
typedef struct IOSNPD IOSNPD;
typedef struct IOSBND IOSBND;
typedef struct IOSTAT IOSTAT;
typedef struct IOSROW IOSROW;
typedef struct IOSAIJ IOSAIJ;
typedef struct IOSPOOL IOSPOOL;
typedef struct IOSCUT IOSCUT;
typedef struct IOSRIB IOSRIB;

struct glp_tree
{     /* branch-and-bound tree */
      DMP *pool;
      /* memory pool to store IOS components */
      int n;
      /* number of columns (variables) */
      /*--------------------------------------------------------------*/
      /* problem components corresponding to the original MIP and its
         LP relaxation (used to restore the original problem object on
         exit from the solver) */
      int orig_m;
      /* number of rows */
      int *orig_type; /* int orig_type[1+orig_m+n]; */
      /* types of all variables */
      double *orig_lb; /* double orig_lb[1+orig_m+n]; */
      /* lower bounds of all variables */
      double *orig_ub; /* double orig_ub[1+orig_m+n]; */
      /* upper bounds of all variables */
      int *orig_stat; /* int orig_stat[1+orig_m+n]; */
      /* statuses of all variables */
      double *orig_prim; /* double orig_prim[1+orig_m+n]; */
      /* primal values of all variables */
      double *orig_dual; /* double orig_dual[1+orig_m+n]; */
      /* dual values of all variables */
      double orig_obj;
      /* optimal objective value for LP relaxation */
      /*--------------------------------------------------------------*/
      /* branch-and-bound tree */
      int nslots;
      /* length of the array of slots (enlarged automatically) */
      int avail;
      /* index of the first free slot; 0 means all slots are in use */
      IOSLOT *slot; /* IOSLOT slot[1+nslots]; */
      /* array of slots:
         slot[0] is not used;
         slot[p], 1 <= p <= nslots, either contains a pointer to some
         node of the branch-and-bound tree, in which case p is used on
         API level as the reference number of corresponding subproblem,
         or is free; all free slots are linked into single linked list;
         slot[1] always contains a pointer to the root node (it is free
         only if the tree is empty) */
      IOSNPD *head;
      /* pointer to the head of the active list */
      IOSNPD *tail;
      /* pointer to the tail of the active list */
      /* the active list is a doubly linked list of active subproblems
         which correspond to leaves of the tree; all subproblems in the
         active list are ordered chronologically (each a new subproblem
         is always added to the tail of the list) */
      int a_cnt;
      /* current number of active nodes (including the current one) */
      int n_cnt;
      /* current number of all (active and inactive) nodes */
      int t_cnt;
      /* total number of nodes including those which have been already
         removed from the tree; this count is increased by one whenever
         a new node is created and never decreased */
      /*--------------------------------------------------------------*/
      /* problem components corresponding to the root subproblem */
      int root_m;
      /* number of rows */
      int *root_type; /* int root_type[1+root_m+n]; */
      /* types of all variables */
      double *root_lb; /* double root_lb[1+root_m+n]; */
      /* lower bounds of all variables */
      double *root_ub; /* double root_ub[1+root_m+n]; */
      /* upper bounds of all variables */
      int *root_stat; /* int root_stat[1+root_m+n]; */
      /* statuses of all variables */
      /*--------------------------------------------------------------*/
      /* current subproblem and its LP relaxation */
      IOSNPD *curr;
      /* pointer to the current subproblem (which can be only active);
         NULL means the current subproblem does not exist */
      glp_prob *mip;
      /* original problem object passed to the solver; if the current
         subproblem exists, its LP segment corresponds to LP relaxation
         of the current subproblem; if the current subproblem does not
         exist, its LP segment corresponds to LP relaxation of the root
         subproblem (note that the root subproblem may differ from the
         original MIP, because it may be preprocessed and/or may have
         additional rows) */
      int solved;
      /* this count shows how many times LP relaxation of the current
         subproblem is solved */
      int *non_int; /* int non_int[1+n]; */
      /* these column flags are set each time when LP relaxation of the
         current subproblem is solved;
         non_int[0] is not used;
         non_int[j], 1 <= j <= n, is j-th column flag; if this flag is
         set, corresponding variable is required to be integer, but its
         value in basic solution is fractional */
      /*--------------------------------------------------------------*/
      /* problem components corresponding to the parent (predecessor)
         subproblem for the current subproblem (used to inspect changes
         on freezing the current subproblem) */
      int pred_m;
      /* number of rows */
      int pred_max;
      /* length of the following four arrays (enlarged automatically),
         pred_max >= pred_m + n */
      int *pred_type; /* int pred_type[1+pred_m+n]; */
      /* types of all variables */
      double *pred_lb; /* double pred_lb[1+pred_m+n]; */
      /* lower bounds of all variables */
      double *pred_ub; /* double pred_ub[1+pred_m+n]; */
      /* upper bounds of all variables */
      int *pred_stat; /* int pred_stat[1+pred_m+n]; */
      /* statuses of all variables */
      /*--------------------------------------------------------------*/
      /* cut generator (under construction) */
      IOSPOOL *local;
      /* local cut pool */
      int first_attempt;
      int max_added_cuts;
      double min_eff;
      int miss;
      int just_selected;
      void *mir_gen;
      /* pointer to working area used by the MIR cut generator */
      void *clq_gen;
      /* pointer to working area used by the clique cut generator */
      int round;
      /* round number; shows how many times the cut generating routine
         is called for the same subproblem; 1 means call for the first
         time */
      /*--------------------------------------------------------------*/
      /* conflict graph for the current subproblem, or, if it does not
         exists, for the root subproblem */
      int *n_ref; /* int n_ref[1+n]; */
      /* n_ref[j], 1 <= j <= n, is the number of a node corresponding
         to binary variable x[j]; n_ref[j] = 0 means that the node is
         not assigned yet */
      int *c_ref; /* int c_ref[1+n]; */
      /* c_ref[j], 1 <= j <= n, is the number of a node corresponding
         to complemented binary variable x'[j]; c_ref[j] = 0 means that
         the node is not assigned yet */
      SCG *g;
      /* conflict graph for the current or root subproblem */
      int *j_ref; /* int j_ref[1+g->n_max]; */
      /* j_ref[k], 1 <= k <= g->n, is the number of a binary variable,
         which refers to node k, that is, j_ref[k] = j if n_ref[j] = k
         or c_ref[j] = k */
      /*--------------------------------------------------------------*/
      void *pcost;
      /* pointer to working area used on pseudocost branching */
      int *iwrk; /* int iwrk[1+n]; */
      /* working array */
      double *dwrk; /* double dwrk[1+n]; */
      /* working array */
      /*--------------------------------------------------------------*/
      /* control parameters and statistics */
      const glp_iocp *parm;
      /* copy of control parameters passed to the solver */
      xlong_t tm_beg;
      /* starting time of the search, in seconds; the total time of the
         search is the difference between xtime() and tm_beg */
      xlong_t tm_lag;
      /* the most recent time, in seconds, at which the progress of the
         the search was displayed */
      int sol_cnt;
      /* number of integer feasible solutions found */
      /*--------------------------------------------------------------*/
      /* advanced solver interface */
      int reason;
      /* flag indicating the reason why the callback routine is being
         called (see glpk.h) */
      int reopt;
      /* flag indicating that the current LP relaxation needs to be
         re-optimized */
      int br_var;
      /* the number of variable chosen to branch on */
      int br_sel;
      /* flag indicating which branch (subproblem) should be selected
         to continue the search:
         GLP_DN_BRNCH - select down-branch
         GLP_UP_BRNCH - select up-branch
         GLP_NO_BRNCH - use general selection technique */
      IOSNPD *btrack;
      /* pointer to active subproblem selected to continue the search;
         NULL means no subproblem has been selected */
      int terminate;
      /* flag indicating that the callback routine requires premature
         termination of the search */
};

struct IOSLOT
{     /* node subproblem slot */
      IOSNPD *node;
      /* pointer to subproblem descriptor; NULL means free slot */
      int next;
      /* index of another free slot (only if this slot is free) */
};

struct IOSNPD
{     /* node subproblem descriptor */
      int p;
      /* subproblem reference number (it is the index to corresponding
         slot, i.e. slot[p] points to this descriptor) */
      IOSNPD *up;
      /* pointer to the parent subproblem; NULL means this node is the
         root of the tree, in which case p = 1 */
      int level;
      /* node level (the root node has level 0) */
      int count;
      /* if count = 0, this subproblem is active; if count > 0, this
         subproblem is inactive, in which case count is the number of
         its child subproblems */
      IOSBND *b_ptr;
      /* linked list of rows and columns of the parent subproblem whose
         types and bounds were changed;
         this list is destroyed on reviving and built anew on freezing
         the subproblem */
      IOSTAT *s_ptr;
      /* linked list of rows and columns of the parent subproblem whose
         statuses were changed;
         this list is destroyed on reviving and built anew on freezing
         the subproblem */
      IOSROW *r_ptr;
      /* linked list of rows (cuts) added to the parent subproblem;
         this list is destroyed on reviving and built anew on freezing
         the subproblem */
      /*--------------------------------------------------------------*/
      /* changes in the conflict graph for this subproblem */
      int own_nn;
      /* number of nodes added for this subproblem */
      int own_nc;
      /* number of cliques added for this subproblem */
      IOSRIB *e_ptr;
      /* linked list of new edges added for this subproblem, where both
         endpoints were added in some ancestor subproblem */
      /*--------------------------------------------------------------*/
#if 1 /* 04/X-2008 */
      double lp_obj;
      /* optimal objective value to LP relaxation of this subproblem;
         on creating a subproblem this value is inherited from its
         parent; for the root subproblem, which has no parent, this
         value is initially set to -DBL_MAX (minimization) or +DBL_MAX
         (maximization); each time the subproblem is re-optimized, this
         value is appropriately changed */
#endif
      double bound;
      /* local lower (minimization) or upper (maximization) bound for
         integer optimal solution to *this* subproblem; this bound is
         local in the sense that only subproblems in the subtree rooted
         at this node cannot have better integer feasible solutions;
         on creating a subproblem its local bound is inherited from its
         parent and then can be made stronger (never weaker); for the
         root subproblem its local bound is initially set to -DBL_MAX
         (minimization) or +DBL_MAX (maximization) and then improved as
         the root LP relaxation has been solved */
#if 1 /* 04/X-2008 */
      int br_var;
      /* ordinal number of branching variable, 1 <= br_var <= n, used
         to split this subproblem; 0 means that either this subproblem
         is active or branching was made on a constraint */
      double br_val;
      /* (fractional) value of branching variable in optimal solution
         to final LP relaxation of this subproblem */
#endif
      /* if this subproblem is inactive, the following two quantities
         correspond to final optimal solution of its LP relaxation; for
         active subproblems these quantities are undefined */
      int ii_cnt;
      /* number of columns (structural variables) of integer kind whose
         primal values are fractional */
      double ii_sum;