/* glpmip.h (branch-and-bound method) */ /*---------------------------------------------------------------------- -- Copyright (C) 2000, 2001, 2002, 2003, 2004 Andrew Makhorin, -- Department for Applied Informatics, Moscow Aviation Institute, -- Moscow, Russia. All rights reserved. E-mail: <mao@mai2.rcnet.ru>. -- -- This file is part of GLPK (GNU Linear Programming Kit). -- -- 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 2, 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; see the file COPYING. If not, write to the Free -- Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA -- 02111-1307, USA. ----------------------------------------------------------------------*/ #ifndef _GLPMIP_H #define _GLPMIP_H #include "glplpx.h" #define mip_create_tree glp_mip_create_tree #define mip_revive_node glp_mip_revive_node #define mip_freeze_node glp_mip_freeze_node #define mip_clone_node glp_mip_clone_node #define mip_delete_node glp_mip_delete_node #define mip_delete_tree glp_mip_delete_tree #define mip_pseudo_root glp_mip_pseudo_root #define mip_best_node glp_mip_best_node #define mip_relative_gap glp_mip_relative_gap #define mip_solve_node glp_mip_solve_node #define mip_driver glp_mip_driver typedef struct MIPTREE MIPTREE; /* branch-and-bound tree */ typedef struct MIPSLOT MIPSLOT; /* node subproblem slot */ typedef struct MIPNODE MIPNODE; /* node subproblem descriptor */ typedef struct MIPBNDS MIPBNDS; /* bounds change entry */ typedef struct MIPSTAT MIPSTAT; /* status change entry */ struct MIPTREE { /* branch-and-bound tree */ /*--------------------------------------------------------------*/ /* global information (valid for all subproblems) */ int m; /* number of rows */ int n; /* number of columns */ int dir; /* optimization direction: LPX_MIN - minimization LPX_MAX - maximization */ int int_obj; /* if this flag is set, the objective function is integral */ int *int_col; /* int int_col[1+n]; */ /* integer column flags; int_col[0] is not used; int_col[j], 1 <= j <= n, is the flag of j-th column; if this flag is set, corresponding structural variable is required to be integer */ /*--------------------------------------------------------------*/ /* memory management */ DMP *node_pool; /* memory pool for MIPNODE objects */ DMP *bnds_pool; /* memory pool for MIPBNDS objects */ DMP *stat_pool; /* memory pool for MIPSTAT objects */ /*--------------------------------------------------------------*/ /* branch-and-bound tree */ int nslots; /* length of the array of slots (increased automatically) */ int avail; /* index of first free slot; 0 means all slots are in use */ MIPSLOT *slot; /* MIPSLOT slot[1+nslots]; */ /* array of slots: slot[0] is never 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) */ MIPNODE *head; /* pointer to the head of the active list */ MIPNODE *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 whenever a new node is created and never decreased */ /*--------------------------------------------------------------*/ /* best known integer feasible solution */ int found; /* if this flag is set, at least one integer feasible solution has been found */ double best; /* incumbent objective value, that is the objective value which corresponds to the best known integer feasible solution (it is undefined if the flag found is not set); this value is a global upper (minimization) or lower (maximization) bound for integer optimal solution of the original problem being solved */ double *mipx; /* double mipx[1+m+n]; */ /* values of auxiliary and structural variables which correspond to the best known integer feasible solution (these are values are undefined if the flag found is not set): mipx[0] is not used; mipx[i], 1 <= i <= m, is a value of i-th auxiliary variable; mipx[m+j], 1 <= j <= n, is a value of j-th structural variable note: if j-th structural variable is required to be integer, its value mipx[m+j] is provided to be integral */ /*--------------------------------------------------------------*/ /* current subproblem and its LP relaxation */ MIPNODE *curr; /* pointer to the current subproblem (which can be only active); NULL means the current subproblem does not exist */ LPX *lp; /* LP relaxation of the current subproblem (this problem object contains global data valid for all subproblems, namely, the sets of rows and columns, objective coefficients, as well as the constraint matrix; only bounds and statuses of some rows and/or columns may be changed for a particular subproblem) */ int *old_type; /* int old_type[1+m+n]; */ double *old_lb; /* double old_lb[1+m+n]; */ double *old_ub; /* double old_ub[1+m+n]; */ int *old_stat; /* int old_stat[1+m+n]; */ /* these four arrays contain attributes of rows and columns which they have in the parent subproblem (types, lower bounds, upper bounds, and statuses); this information is used to build change lists on freezing the current subproblem; note that if the root subproblem is current, standard attributes of rows and columns are used (all rows are free and basic, all columns are fixed at zero and non-basic) */ int *non_int; /* int non_int[1+n]; */ /* these column flags are set once LP relaxation of the current subproblem has been solved; non_int[0] is not used; non_int[j], 1 <= j <= n, is the flag of j-th column; if this flag is set, corresponding structural variable is required to be integer, but its value in basic solution is fractional */ /*--------------------------------------------------------------*/ /* control parameters and statistics */ int msg_lev; /* level of messages issued by the solver: 0 - no output 1 - error messages only 2 - normal output 3 - detailed step-by-step output */ int branch; /* MIP */ /* branching heuristic: 0 - branch on first variable 1 - branch on last variable 2 - branch using heuristic by Driebeck and Tomlin 3 - branch on most fractional variable */ int btrack; /* MIP */ /* backtracking heuristic: 0 - select most recent node (depth first search) 1 - select earliest node (breadth first search) 2 - select node using the best projection heuristic 3 - select node with best local bound */ double tol_int; /* absolute tolerance used to check if the current basic solution is integer feasible */ double tol_obj; /* relative tolerance used to check if the value of the objective function is better than the incumbent objective value */ double tm_lim; /* searching time limit, in seconds; if this value is positive, it is decreased whenever one complete round of the search is performed by the amount of time spent for the round, and reaching zero value signals the solver to stop the search; negative value means no time limit */ double out_frq; /* output frequency, in seconds; this parameter specifies how frequently the solver sends information about the progress of the search to the standard output */ double out_dly; /* output delay, in seconds; this parameter specifies how long output from the LP solver is delayed on solving LP relaxation of the current subproblem; zero value means no delay */ double tm_beg; /* starting time of the search, in seconds; the total time of the search is the difference between utime() and tm_beg */ double tm_lag; /* the most recent time, in seconds, at which the progress of the the search was displayed */ }; struct MIPSLOT { /* node subproblem slot */ MIPNODE *node; /* pointer to subproblem descriptor; NULL means free slot */ int next; /* index of another free slot (only if this slot is free) */ }; struct MIPNODE { /* node subproblem descriptor */ int p; /* subproblem reference number (it is the index to corresponding slot, i.e. slot[p] points to this descriptor) */ MIPNODE *up; /* pointer to 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 */ MIPBNDS *bnds; /* linked list of rows and columns whose types and bounds were changed; this list is destroyed on reviving and built anew on freezing the subproblem */ MIPSTAT *stat; /* linked list of rows and columns whose statuses were changed; this list is destroyed on reviving and built anew on freezing the subproblem */ double bound; /* local lower (minimization) or upper (maximization) bound of integer optimal solution of *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 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; /* the sum of integer infeasibilities */ MIPNODE *temp; /* auxiliary pointer used by some routines */ MIPNODE *prev; /* pointer to previous subproblem in the active list */ MIPNODE *next; /* pointer to next subproblem in the active list */ }; struct MIPBNDS { /* bounds change entry */ int k; /* ordinal number of corresponding row (1 <= k <= m) or column (m+1 <= k <= m+n) */ int type; /* new type */ double lb; /* new lower bound */ double ub; /* new upper bound */ MIPBNDS *next; /* pointer to next entry for the same subproblem */ }; struct MIPSTAT { /* status change entry */ int k; /* ordinal number of corresponding row (1 <= k <= m) or column (m+1 <= k <= m+n) */ int stat; /* new status */ MIPSTAT *next; /* pointer to next entry for the same subproblem */ }; /* exit codes returned by the routine mip_driver: */ #define MIP_E_OK 1200 /* the search is completed */ #define MIP_E_ITLIM 1201 /* iterations limit exhausted */ #define MIP_E_TMLIM 1202 /* time limit exhausted */ #define MIP_E_ERROR 1203 /* error on solving LP relaxation */ MIPTREE *mip_create_tree(int m, int n, int dir); /* create branch-and-bound tree */ void mip_revive_node(MIPTREE *tree, int p); /* revive specified subproblem */ void mip_freeze_node(MIPTREE *tree); /* freeze current subproblem */ void mip_clone_node(MIPTREE *tree, int p, int nnn, int ref[]); /* clone specified subproblem */ void mip_delete_node(MIPTREE *tree, int p); /* delete specified subproblem */ void mip_delete_tree(MIPTREE *tree); /* delete branch-and-bound tree */ int mip_pseudo_root(MIPTREE *tree); /* find pseudo-root of the branch-and-bound tree */ int mip_best_node(MIPTREE *tree); /* find active node with best local bound */ double mip_relative_gap(MIPTREE *tree); /* compute relative mip gap */ int mip_solve_node(MIPTREE *tree); /* solve LP relaxation of current subproblem */ int mip_driver(MIPTREE *tree); /* branch-and-bound driver */ #endif /* eof */