QSopt

binary.c File Reference

#include "econfig.h"
#include "priority.h"
#include "sortrus.h"
#include "iqsutil.h"
#include "lpdata.h"
#include "lpdefs.h"
#include "simplex.h"
#include "binary.h"
#include "price.h"
#include "lib.h"
#include "qstruct.h"
#include "qsopt.h"

Include dependency graph for binary.c:

Go to the source code of this file.

Data Structures

struct  bbnode
struct  mipinfo

Defines

#define FIRSTBRANCH   1
#define ILL_BRANCH_PENALTY_VAL(v0, v1, f)
#define ILL_BRANCH_PENALTY_WEIGHT   (2)
#define ILL_BRANCH_STRONG_VAL(v0, v1)
#define ILL_BRANCH_STRONG_WEIGHT   (10)
#define ILL_INTTOL   PFEAS_TOLER
#define MIDDLEBRANCH   2
#define PENALTYBRANCH   4
#define STRONG_CANDIDATES   (10)
#define STRONG_PIVOTS   (50)
#define STRONGBRANCH   3

Functions

static void best_bbnode (mipinfo *minf, bbnode **best)
static void check_integral (lpinfo *lp, EGlpNum_t *x, int *yesno)
static int child_work (mipinfo *minf, bbnode *active, int bvar, int bdir, EGlpNum_t *cval, int *cp, itcnt_t *itcnt)
static void cleanup_mip (mipinfo *minf)
static void copy_x (int nstruct, EGlpNum_t *from_x, EGlpNum_t *to_x)
static int find_branch (mipinfo *minf, EGlpNum_t *x, EGlpNum_t *lpval, int *bvar, itcnt_t *itcnt)
static void find_first_branch (lpinfo *lp, EGlpNum_t *x, int *bvar)
static void find_middle_branch (lpinfo *lp, EGlpNum_t *x, int *bvar)
static int find_penalty_branch (lpinfo *lp, price_info *pinf, EGlpNum_t *x, EGlpNum_t *downpen, EGlpNum_t *uppen, EGlpNum_t *lpval, int *bvar, itcnt_t *itcnt)
static int find_strong_branch (lpinfo *lp, price_info *pinf, EGlpNum_t *x, int *bvar, itcnt_t *itcnt)
static int fix_variables (lpinfo *lp, EGlpNum_t *bestval, bbnode *b, EGlpNum_t *wupper, EGlpNum_t *wlower, int *hit)
static void free_bbnode (bbnode *b)
static void free_mipinfo (mipinfo *minf)
 ILL_PTRWORLD_ROUTINES (ILL_PTRWORLD_LISTFREE_ROUTINE(bbnode, bbnodealloc, bbnode_bulkalloc, bbnodefree)
int ILLmip_bfs (lpinfo *lp, EGlpNum_t *val, EGlpNum_t *x, itcnt_t *itcnt)
static void init_bbnode (bbnode *b)
static void init_mipinfo (mipinfo *minf)
static int plunge (mipinfo *minf, itcnt_t *itcnt)
static int plunge_work (mipinfo *minf, int depth, itcnt_t *itcnt)
static int process_bfs_bbnode (mipinfo *minf, bbnode *active, itcnt_t *itcnt)
static void put_bbnode (mipinfo *minf, bbnode *b)
static void remove_bbnode (bbnode *b)
static int round_variables (mipinfo *minf, int *count, EGlpNum_t *tol)
static int run_bfs (mipinfo *minf, itcnt_t *itcnt)
static int startup_mip (mipinfo *minf, lpinfo *lp, price_info *pinf, EGlpNum_t *lpval, itcnt_t *itcnt)

Variables

static int TRACE = 0

Define Documentation

#define FIRSTBRANCH   1

Definition at line 76 of file binary.c.

Referenced by find_branch().

#define ILL_BRANCH_PENALTY_VAL ( v0,
v1,
f   ) 

Value:

(((v0)*(f) < (v1)*(1.0-(f)) ?                                    \
        (ILL_BRANCH_PENALTY_WEIGHT * (v0)*(f) + (v1)*(1.0-(f)))    \
      : (ILL_BRANCH_PENALTY_WEIGHT * (v1)*(1.0-(f)) + (v0)*(f)))    \
                    / (ILL_BRANCH_PENALTY_WEIGHT + 1.0))

Definition at line 68 of file binary.c.

#define ILL_BRANCH_PENALTY_WEIGHT   (2)

Definition at line 67 of file binary.c.

#define ILL_BRANCH_STRONG_VAL ( v0,
v1   ) 

Value:

(((v0) < (v1) ? (ILL_BRANCH_STRONG_WEIGHT * (v0) + (v1))         \
                  : (ILL_BRANCH_STRONG_WEIGHT * (v1) + (v0)))        \
                    / (ILL_BRANCH_STRONG_WEIGHT + 1.0))

Definition at line 62 of file binary.c.

#define ILL_BRANCH_STRONG_WEIGHT   (10)

Definition at line 61 of file binary.c.

#define ILL_INTTOL   PFEAS_TOLER

Definition at line 56 of file binary.c.

Referenced by check_integral(), child_work(), find_first_branch(), find_penalty_branch(), find_strong_branch(), fix_variables(), and plunge_work().

#define MIDDLEBRANCH   2

Definition at line 77 of file binary.c.

Referenced by find_branch().

#define PENALTYBRANCH   4

Definition at line 79 of file binary.c.

Referenced by find_branch(), and ILLmip_bfs().

#define STRONG_CANDIDATES   (10)

Definition at line 59 of file binary.c.

Referenced by find_strong_branch().

#define STRONG_PIVOTS   (50)

Definition at line 58 of file binary.c.

#define STRONGBRANCH   3

Definition at line 78 of file binary.c.

Referenced by find_branch(), and init_mipinfo().

Function Documentation

static void best_bbnode ( mipinfo *  minf,
bbnode **  best 
) [static]

Definition at line 955 of file binary.c.

References bbnode::bound, EGlpNum_t, EGlpNumClearVar, EGlpNumInitVar, mipinfo::head_bbnode, ILL_MAXDOUBLE, ILLutil_priority_deletemin(), bbnode::next, and mipinfo::que.

Referenced by run_bfs().

Here is the call graph for this function:

static void check_integral ( lpinfo *  lp,
EGlpNum_t *  x,
int *  yesno 
) [static]

Definition at line 1373 of file binary.c.

References EGlpNum_t, EGlpNumClearVar, EGlpNumFloor, EGlpNumInitVar, EGlpNumIsNeq, EGlpNumIsNeqZero, EGlpNumSign, EGlpNumSubTo, ILL_INTTOL, ILLlpdata::intmarker, ILLlpdata::nstruct, lpinfo::O, and oneLpNum.

Referenced by child_work().

static int child_work ( mipinfo *  minf,
bbnode *  active,
int  bvar,
int  bdir,
EGlpNum_t *  cval,
int *  cp,
itcnt_t *  itcnt 
) [static]

Definition at line 691 of file binary.c.

References mipinfo::bestx, bbnode::bound, bbnode::bound_cnt, bbnode::bound_indx, bbnode::bounds, check_integral(), copy_x(), bbnode::cstat, bbnode::depth, price_info::dII_price, DUAL_SIMPLEX, EGlpNum_t, EGlpNumAllocArray, EGlpNumCeil, EGlpNumClearVar, EGlpNumCopy, EGlpNumFloor, EGlpNumFreeArray, EGlpNumInitVar, EGlpNumIsLeq, EGlpNumIsLess, EGlpNumSubTo, EGlpNumToLf, bbnode::id, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_INTTOL, ILL_MAXDOUBLE, ILL_SAFE_MALLOC, ILLlib_chgbnd(), ILLlib_getbasis(), ILLlib_getbnd(), ILLlib_getrownorms(), ILLlib_iter(), ILLlib_objval(), ILLlib_optimize(), ILLutil_priority_insert(), init_bbnode(), mipinfo::lastpivots, mipinfo::lp, bbnode::lu, lpinfo::nrows, ILLlpdata::nstruct, lpinfo::O, mipinfo::objectivebound, mipinfo::pinf, mipinfo::ptrworld, put_bbnode(), QS_LP_INFEASIBLE, QS_LP_UNSOLVED, QS_PRICE_DSTEEP, mipinfo::que, bbnode::rownorms, bbnode::rstat, mipinfo::totalnodes, mipinfo::totalpivots, mipinfo::value, and mipinfo::x.

Here is the call graph for this function:

static void cleanup_mip ( mipinfo *  minf  )  [static]

Definition at line 389 of file binary.c.

References EGlpNumSign, ILL_MAX, ILL_MIN, mipinfo::lp, lpinfo::ncols, lpinfo::O, ILLlpdata::obj, ILLlpdata::objsense, and mipinfo::objsense.

Referenced by ILLmip_bfs().

static void copy_x ( int  nstruct,
EGlpNum_t *  from_x,
EGlpNum_t *  to_x 
) [static]

Definition at line 1656 of file binary.c.

References EGlpNumCopy.

Referenced by child_work(), ILLmip_bfs(), and plunge_work().

static int find_branch ( mipinfo *  minf,
EGlpNum_t *  x,
EGlpNum_t *  lpval,
int *  bvar,
itcnt_t *  itcnt 
) [static]

Definition at line 999 of file binary.c.

References mipinfo::branching_rule, mipinfo::downpen, find_first_branch(), find_middle_branch(), find_penalty_branch(), find_strong_branch(), FIRSTBRANCH, ILL_CLEANUP_IF, ILL_RETURN, mipinfo::lp, MIDDLEBRANCH, PENALTYBRANCH, mipinfo::pinf, STRONGBRANCH, and mipinfo::uppen.

Here is the call graph for this function:

static void find_first_branch ( lpinfo *  lp,
EGlpNum_t *  x,
int *  bvar 
) [static]

Definition at line 1037 of file binary.c.

References EGlpNum_t, EGlpNumFloor, EGlpNumInitVar, EGlpNumIsNeq, EGlpNumIsNeqZero, EGlpNumSign, EGlpNumSubTo, ILL_INTTOL, ILLlpdata::intmarker, ILLlpdata::nstruct, lpinfo::O, oneLpNum, and t.

Referenced by find_branch().

static void find_middle_branch ( lpinfo *  lp,
EGlpNum_t *  x,
int *  bvar 
) [static]

Definition at line 1068 of file binary.c.

References EGlpNum_t, EGlpNumCopy, EGlpNumDivUiTo, EGlpNumFloor, EGlpNumInitVar, EGlpNumIsLess, EGlpNumIsLessZero, EGlpNumMultUiTo, EGlpNumSet, EGlpNumSign, EGlpNumSubTo, ILLlpdata::intmarker, ILLlpdata::nstruct, lpinfo::O, oneLpNum, and t.

Referenced by find_branch(), and plunge_work().

static int find_penalty_branch ( lpinfo *  lp,
price_info *  pinf,
EGlpNum_t *  x,
EGlpNum_t *  downpen,
EGlpNum_t *  uppen,
EGlpNum_t *  lpval,
int *  bvar,
itcnt_t *  itcnt 
) [static]

Definition at line 1117 of file binary.c.

References EGlpNum_t, EGlpNumAllocArray, EGlpNumCopy, EGlpNumFloor, EGlpNumInitVar, EGlpNumIsEqqual, EGlpNumIsNeq, EGlpNumIsNeqZero, EGlpNumSign, EGlpNumSubTo, ILL_INTTOL, ILL_MINDOUBLE, ILL_SAFE_MALLOC, ILLlpdata::intmarker, ILLlpdata::nstruct, lpinfo::O, oneLpNum, and t.

Referenced by find_branch().

static int find_strong_branch ( lpinfo *  lp,
price_info *  pinf,
EGlpNum_t *  x,
int *  bvar,
itcnt_t *  itcnt 
) [static]

Definition at line 1238 of file binary.c.

References EGlpNum_t, EGlpNumAllocArray, EGlpNumCopy, EGlpNumDivUiTo, EGlpNumFloor, EGlpNumInitVar, EGlpNumIsLessZero, EGlpNumIsNeq, EGlpNumMultUiTo, EGlpNumSign, EGlpNumSubTo, ILL_INTTOL, ILL_MINDOUBLE, ILL_SAFE_MALLOC, ILLutil_sprand(), ILLlpdata::intmarker, ILLlpdata::nstruct, lpinfo::O, oneLpNum, and STRONG_CANDIDATES.

Referenced by find_branch().

Here is the call graph for this function:

static int fix_variables ( lpinfo *  lp,
EGlpNum_t *  bestval,
bbnode *  b,
EGlpNum_t *  wupper,
EGlpNum_t *  wlower,
int *  hit 
) [static]

Definition at line 846 of file binary.c.

References bbnode::bound_cnt, bbnode::bound_indx, bbnode::bounds, EGlpNum_t, EGlpNumAddTo, EGlpNumAllocArray, EGlpNumCopy, EGlpNumInitVar, EGlpNumIsLess, EGlpNumIsNeqq, EGlpNumReallocArray, EGlpNumSign, EGlpNumSubTo, EGrealloc, ILL_CLEANUP_IF, ILL_INTTOL, ILL_MAXDOUBLE, ILL_SAFE_MALLOC, ILLlib_chgbnd(), ILLlib_objval(), ILLlib_solution(), ILLlpdata::intmarker, bbnode::lu, ILLlpdata::nstruct, lpinfo::O, and oneLpNum.

Here is the call graph for this function:

static void free_bbnode ( bbnode *  b  )  [static]

Definition at line 1748 of file binary.c.

References bbnode::bound, bbnode::bound_indx, bbnode::bounds, bbnode::cstat, EGlpNumClearVar, EGlpNumFreeArray, ILL_IFFREE, bbnode::lu, bbnode::rownorms, and bbnode::rstat.

Referenced by run_bfs().

static void free_mipinfo ( mipinfo *  minf  )  [static]

Definition at line 1700 of file binary.c.

References mipinfo::bestx, mipinfo::downpen, EGlpNumClearVar, EGlpNumFreeArray, mipinfo::head_bbnode, ILLptrworld_delete(), mipinfo::lower, bbnode::next, mipinfo::objectivebound, mipinfo::ptrworld, mipinfo::uppen, mipinfo::upper, mipinfo::value, and mipinfo::x.

Referenced by ILLmip_bfs().

Here is the call graph for this function:

ILL_PTRWORLD_ROUTINES ( ILL_PTRWORLD_LISTFREE_ROUTINE (  bbnode,
bbnodealloc  ,
bbnode_bulkalloc  ,
bbnodefree   
)

Definition at line 132 of file binary.c.

References QS_PRICE_DSTEEP, and QS_PRICE_PSTEEP.

int ILLmip_bfs ( lpinfo *  lp,
EGlpNum_t *  val,
EGlpNum_t *  x,
itcnt_t *  itcnt 
)

Definition at line 176 of file binary.c.

References mipinfo::activenodes, mipinfo::bestx, bbnode::bound, mipinfo::branching_rule, cleanup_mip(), copy_x(), bbnode::cstat, bbnode::depth, price_info::dII_price, EGlpNum_t, EGlpNumAllocArray, EGlpNumClearVar, EGlpNumCopy, EGlpNumFreeArray, EGlpNumInitVar, EGlpNumIsNeqq, EGlpNumSign, free_mipinfo(), mipinfo::head_bbnode, price_info::htrigger, bbnode::id, ILL_CLEANUP_IF, ILL_IFFREE, ILL_MAX, ILL_MAXDOUBLE, ILL_RETURN, ILL_SAFE_MALLOC, ILLlib_getbasis(), ILLlib_getrownorms(), ILLprice_free_pricing_info(), ILLprice_init_pricing_info(), ILLutil_priority_free(), ILLutil_priority_init(), ILLutil_priority_insert(), ILLutil_zeit(), init_bbnode(), init_mipinfo(), bbnode::next, lpinfo::nrows, ILLlpdata::nstruct, lpinfo::O, mipinfo::objsense, PENALTYBRANCH, mipinfo::ptrworld, QS_PRICE_DSTEEP, mipinfo::que, bbnode::rownorms, bbnode::rstat, run_bfs(), startup_mip(), mipinfo::totalnodes, mipinfo::totalpivots, and mipinfo::value.

Referenced by solver_main().

Here is the call graph for this function:

static void init_bbnode ( bbnode *  b  )  [static]

Definition at line 1726 of file binary.c.

References bbnode::bound, bbnode::bound_cnt, bbnode::bound_indx, bbnode::bounds, bbnode::cstat, bbnode::depth, EGlpNumCopy, EGlpNumInitVar, bbnode::handle, bbnode::id, ILL_MINDOUBLE, bbnode::lu, bbnode::next, bbnode::prev, bbnode::rownorms, and bbnode::rstat.

Referenced by child_work(), and ILLmip_bfs().

static void init_mipinfo ( mipinfo *  minf  )  [static]

Definition at line 1669 of file binary.c.

References mipinfo::activenodes, mipinfo::bestx, mipinfo::branching_rule, mipinfo::depth, mipinfo::downpen, EGlpNumCopy, EGlpNumInitVar, mipinfo::head_bbnode, ILL_MAXDOUBLE, ILLptrworld_init(), mipinfo::lastpivots, mipinfo::lower, mipinfo::lp, bbnode::next, mipinfo::objectivebound, mipinfo::pinf, bbnode::prev, mipinfo::ptrworld, mipinfo::que, STRONGBRANCH, mipinfo::totalnodes, mipinfo::totalpivots, mipinfo::uppen, mipinfo::upper, mipinfo::value, mipinfo::watch, and mipinfo::x.

Referenced by ILLmip_bfs().

Here is the call graph for this function:

static int plunge ( mipinfo *  minf,
itcnt_t *  itcnt 
) [static]

Definition at line 1407 of file binary.c.

References DUAL_SIMPLEX, EGlpNum_t, EGlpNumAllocArray, EGlpNumCopy, EGlpNumFreeArray, ILL_CLEANUP_IF, ILL_RETURN, ILLlib_chgbnd(), ILLlib_optimize(), mipinfo::lower, mipinfo::lp, ILLlpdata::nstruct, lpinfo::O, mipinfo::pinf, plunge_work(), mipinfo::upper, and mipinfo::watch.

Here is the call graph for this function:

static int plunge_work ( mipinfo *  minf,
int  depth,
itcnt_t *  itcnt 
) [static]

Definition at line 1458 of file binary.c.

References mipinfo::bestx, copy_x(), DUAL_SIMPLEX, EGlpNum_t, EGlpNumClearVar, EGlpNumCopy, EGlpNumCopyDiff, EGlpNumInitVar, EGlpNumIsEqqual, EGlpNumIsLess, EGlpNumOne, EGlpNumSet, EGlpNumToLf, EGlpNumZero, find_middle_branch(), ILL_CLEANUP, ILL_CLEANUP_IF, ILL_INTTOL, ILL_MAXDOUBLE, ILL_RETURN, ILLlib_chgbnd(), ILLlib_get_x(), ILLlib_objval(), ILLlib_optimize(), mipinfo::lower, mipinfo::lp, ILLlpdata::nstruct, lpinfo::O, mipinfo::objectivebound, oneLpNum, mipinfo::pinf, QS_LP_INFEASIBLE, QS_LP_OPTIMAL, QS_LP_UNSOLVED, round_variables(), mipinfo::upper, mipinfo::value, mipinfo::x, and zeroLpNum.

Referenced by plunge().

Here is the call graph for this function:

static int process_bfs_bbnode ( mipinfo *  minf,
bbnode *  active,
itcnt_t *  itcnt 
) [static]

Definition at line 432 of file binary.c.

References mipinfo::activenodes, bbnode::bound, bbnode::bound_cnt, bbnode::bound_indx, bbnode::bounds, EGlpNum_t, EGlpNumAllocArray, EGlpNumCopy, EGlpNumInitVar, EGlpNumIsLeq, EGlpNumIsLess, EGlpNumIsNeqq, EGlpNumToLf, bbnode::id, ILL_CLEANUP_IF, ILL_MAXDOUBLE, ILLlib_chgbnds(), ILLlp_basis_init(), mipinfo::lastpivots, mipinfo::lp, bbnode::lu, ILLlpdata::nstruct, lpinfo::O, mipinfo::objectivebound, mipinfo::orig_lower, mipinfo::orig_upper, t, mipinfo::totalpivots, mipinfo::value, and mipinfo::watch.

Referenced by run_bfs().

Here is the call graph for this function:

static void put_bbnode ( mipinfo *  minf,
bbnode *  b 
) [static]

Definition at line 980 of file binary.c.

References mipinfo::head_bbnode, bbnode::next, and bbnode::prev.

Referenced by child_work().

static void remove_bbnode ( bbnode *  b  )  [static]

Definition at line 991 of file binary.c.

References bbnode::next, and bbnode::prev.

Referenced by run_bfs().

static int round_variables ( mipinfo *  minf,
int *  count,
EGlpNum_t *  tol 
) [static]

Definition at line 1614 of file binary.c.

References EGlpNumIsEqual, EGlpNumIsLess, EGlpNumIsNeqq, EGlpNumOne, EGlpNumZero, ILL_CLEANUP_IF, ILLlib_chgbnd(), ILLlpdata::intmarker, mipinfo::lower, mipinfo::lp, ILLlpdata::nstruct, lpinfo::O, oneLpNum, mipinfo::upper, mipinfo::x, and zeroLpNum.

Referenced by plunge_work().

Here is the call graph for this function:

static int run_bfs ( mipinfo *  minf,
itcnt_t *  itcnt 
) [static]

Definition at line 409 of file binary.c.

References mipinfo::activenodes, best_bbnode(), free_bbnode(), mipinfo::head_bbnode, ILL_CLEANUP_IF, ILL_RETURN, bbnode::next, process_bfs_bbnode(), mipinfo::ptrworld, and remove_bbnode().

Referenced by ILLmip_bfs().

Here is the call graph for this function:

static int startup_mip ( mipinfo *  minf,
lpinfo *  lp,
price_info *  pinf,
EGlpNum_t *  lpval,
itcnt_t *  itcnt 
) [static]

Definition at line 274 of file binary.c.

References DUAL_SIMPLEX, EGlpNum_t, EGlpNumCopy, EGlpNumInitVar, EGlpNumIsEqqual, EGlpNumToLf, ILL_CLEANUP_IF, ILL_MAXDOUBLE, ILL_MINDOUBLE, ILLlib_iter(), ILLlib_objval(), ILLlib_optimize(), ILLlpdata::intmarker, ILLlpdata::lower, ILLlpdata::nstruct, lpinfo::O, ILLlpdata::structmap, mipinfo::totalpivots, and ILLlpdata::upper.

Referenced by ILLmip_bfs().

Here is the call graph for this function:

Variable Documentation

int TRACE = 0 [static]

Definition at line 24 of file binary.c.

Generated on Wed Apr 22 09:17:15 2009 for QSopt_ex by  doxygen 1.5.2