fp20_binary.c File Reference

#include "qs_config.h"
#include "fp20_priority.h"
#include "fp20_sortrus.h"
#include "fp20_iqsutil.h"
#include "fp20_lpdata.h"
#include "fp20_lpdefs.h"
#include "fp20_simplex.h"
#include "fp20_binary.h"
#include "fp20_price.h"
#include "fp20_lib.h"
#include "fp20_qstruct.h"
#include "fp20_qsopt.h"

Include dependency graph for fp20_binary.c:

Go to the source code of this file.

Data Structures

struct  fp20_bbnode
struct  fp20_mipinfo

Defines

#define fp20_FIRSTBRANCH   1
#define fp20_ILL_BRANCH_PENALTY_VAL(v0, v1, f)
#define fp20_ILL_BRANCH_PENALTY_WEIGHT   (2)
#define fp20_ILL_BRANCH_STRONG_VAL(v0, v1)
#define fp20_ILL_BRANCH_STRONG_WEIGHT   (10)
#define fp20_ILL_INTTOL   fp20_PFEAS_TOLER
#define fp20_MIDDLEBRANCH   2
#define fp20_PENALTYBRANCH   4
#define fp20_STRONG_CANDIDATES   (10)
#define fp20_STRONG_PIVOTS   (50)
#define fp20_STRONGBRANCH   3

Functions

static void fp20_best_bbnode (fp20_mipinfo *minf, fp20_bbnode **best)
static void fp20_check_integral (fp20_lpinfo *lp, EGfp20_t *x, int *yesno)
static int fp20_child_work (fp20_mipinfo *minf, fp20_bbnode *active, int bvar, int bdir, EGfp20_t *cval, int *cp, itcnt_t *itcnt)
static void fp20_cleanup_mip (fp20_mipinfo *minf)
static void fp20_copy_x (int nstruct, EGfp20_t *from_x, EGfp20_t *to_x)
static int fp20_find_branch (fp20_mipinfo *minf, EGfp20_t *x, EGfp20_t *lpval, int *bvar, itcnt_t *itcnt)
static void fp20_find_first_branch (fp20_lpinfo *lp, EGfp20_t *x, int *bvar)
static void fp20_find_middle_branch (fp20_lpinfo *lp, EGfp20_t *x, int *bvar)
static int fp20_find_penalty_branch (fp20_lpinfo *lp, fp20_price_info *pinf, EGfp20_t *x, EGfp20_t *downpen, EGfp20_t *uppen, EGfp20_t *lpval, int *bvar, itcnt_t *itcnt)
static int fp20_find_strong_branch (fp20_lpinfo *lp, fp20_price_info *pinf, EGfp20_t *x, int *bvar, itcnt_t *itcnt)
static int fp20_fix_variables (fp20_lpinfo *lp, EGfp20_t *bestval, fp20_bbnode *b, EGfp20_t *wupper, EGfp20_t *wlower, int *hit)
static void fp20_free_bbnode (fp20_bbnode *b)
static void fp20_free_mipinfo (fp20_mipinfo *minf)
int fp20_ILLmip_bfs (fp20_lpinfo *lp, EGfp20_t *val, EGfp20_t *x, itcnt_t *itcnt)
static void fp20_init_bbnode (fp20_bbnode *b)
static void fp20_init_mipinfo (fp20_mipinfo *minf)
static int fp20_plunge (fp20_mipinfo *minf, itcnt_t *itcnt)
static int fp20_plunge_work (fp20_mipinfo *minf, int depth, itcnt_t *itcnt)
static int fp20_process_bfs_bbnode (fp20_mipinfo *minf, fp20_bbnode *active, itcnt_t *itcnt)
static void fp20_put_bbnode (fp20_mipinfo *minf, fp20_bbnode *b)
static void fp20_remove_bbnode (fp20_bbnode *b)
static int fp20_round_variables (fp20_mipinfo *minf, int *count, EGfp20_t *tol)
static int fp20_run_bfs (fp20_mipinfo *minf, itcnt_t *itcnt)
static int fp20_startup_mip (fp20_mipinfo *minf, fp20_lpinfo *lp, fp20_price_info *pinf, EGfp20_t *lpval, itcnt_t *itcnt)
 ILL_PTRWORLD_ROUTINES (ILL_PTRWORLD_LISTFREE_ROUTINE(fp20_bbnode, bbnodealloc, bbnode_bulkalloc, bbnodefree)

Variables

static int TRACE = 0


Define Documentation

#define fp20_FIRSTBRANCH   1

Definition at line 76 of file fp20_binary.c.

Referenced by fp20_find_branch().

#define fp20_ILL_BRANCH_PENALTY_VAL ( v0,
v1,
 ) 

Value:

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

Definition at line 68 of file fp20_binary.c.

#define fp20_ILL_BRANCH_PENALTY_WEIGHT   (2)

Definition at line 67 of file fp20_binary.c.

#define fp20_ILL_BRANCH_STRONG_VAL ( v0,
v1   ) 

Value:

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

Definition at line 62 of file fp20_binary.c.

#define fp20_ILL_BRANCH_STRONG_WEIGHT   (10)

Definition at line 61 of file fp20_binary.c.

#define fp20_ILL_INTTOL   fp20_PFEAS_TOLER

Definition at line 56 of file fp20_binary.c.

Referenced by fp20_check_integral(), fp20_child_work(), fp20_find_first_branch(), fp20_find_penalty_branch(), fp20_find_strong_branch(), fp20_fix_variables(), and fp20_plunge_work().

#define fp20_MIDDLEBRANCH   2

Definition at line 77 of file fp20_binary.c.

Referenced by fp20_find_branch().

#define fp20_PENALTYBRANCH   4

Definition at line 79 of file fp20_binary.c.

Referenced by fp20_find_branch(), and fp20_ILLmip_bfs().

#define fp20_STRONG_CANDIDATES   (10)

Definition at line 59 of file fp20_binary.c.

Referenced by fp20_find_strong_branch().

#define fp20_STRONG_PIVOTS   (50)

Definition at line 58 of file fp20_binary.c.

#define fp20_STRONGBRANCH   3

Definition at line 78 of file fp20_binary.c.

Referenced by fp20_find_branch(), and fp20_init_mipinfo().


Function Documentation

static void fp20_best_bbnode ( fp20_mipinfo minf,
fp20_bbnode **  best 
) [static]

Definition at line 955 of file fp20_binary.c.

References fp20_bbnode::bound, fp20_ILL_MAXDOUBLE, fp20_ILLutil_priority_deletemin(), fp20_mipinfo::head_bbnode, fp20_bbnode::next, and fp20_mipinfo::que.

Referenced by fp20_run_bfs().

Here is the call graph for this function:

static void fp20_check_integral ( fp20_lpinfo lp,
EGfp20_t *  x,
int *  yesno 
) [static]

Definition at line 1373 of file fp20_binary.c.

References fp20_ILL_INTTOL, fp20_ILLlpdata::intmarker, fp20_ILLlpdata::nstruct, and fp20_lpinfo::O.

Referenced by fp20_child_work().

static int fp20_child_work ( fp20_mipinfo minf,
fp20_bbnode active,
int  bvar,
int  bdir,
EGfp20_t *  cval,
int *  cp,
itcnt_t itcnt 
) [static]

Definition at line 691 of file fp20_binary.c.

References fp20_mipinfo::bestx, fp20_bbnode::bound, fp20_bbnode::bound_cnt, fp20_bbnode::bound_indx, fp20_bbnode::bounds, fp20_bbnode::cstat, fp20_bbnode::depth, fp20_price_info::dII_price, DUAL_SIMPLEX, fp20_check_integral(), fp20_copy_x(), fp20_ILL_INTTOL, fp20_ILL_MAXDOUBLE, fp20_ILLlib_chgbnd(), fp20_ILLlib_getbasis(), fp20_ILLlib_getbnd(), fp20_ILLlib_getrownorms(), fp20_ILLlib_iter(), fp20_ILLlib_objval(), fp20_ILLlib_optimize(), fp20_ILLutil_priority_insert(), fp20_init_bbnode(), fp20_put_bbnode(), fp20_bbnode::id, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_SAFE_MALLOC, fp20_mipinfo::lastpivots, fp20_mipinfo::lp, fp20_bbnode::lu, fp20_lpinfo::nrows, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, fp20_mipinfo::objectivebound, fp20_mipinfo::pinf, fp20_mipinfo::ptrworld, QS_LP_INFEASIBLE, QS_LP_UNSOLVED, QS_PRICE_DSTEEP, fp20_mipinfo::que, fp20_bbnode::rownorms, fp20_bbnode::rstat, fp20_mipinfo::totalnodes, fp20_mipinfo::totalpivots, fp20_mipinfo::value, and fp20_mipinfo::x.

Here is the call graph for this function:

static void fp20_cleanup_mip ( fp20_mipinfo minf  )  [static]

Definition at line 389 of file fp20_binary.c.

References fp20_ILL_MAX, fp20_ILL_MIN, fp20_mipinfo::lp, fp20_lpinfo::ncols, fp20_lpinfo::O, fp20_ILLlpdata::obj, fp20_ILLlpdata::objsense, and fp20_mipinfo::objsense.

Referenced by fp20_ILLmip_bfs().

static void fp20_copy_x ( int  nstruct,
EGfp20_t *  from_x,
EGfp20_t *  to_x 
) [static]

Definition at line 1656 of file fp20_binary.c.

Referenced by fp20_child_work(), fp20_ILLmip_bfs(), and fp20_plunge_work().

static int fp20_find_branch ( fp20_mipinfo minf,
EGfp20_t *  x,
EGfp20_t *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 999 of file fp20_binary.c.

References fp20_mipinfo::branching_rule, fp20_mipinfo::downpen, fp20_find_first_branch(), fp20_find_middle_branch(), fp20_find_penalty_branch(), fp20_find_strong_branch(), fp20_FIRSTBRANCH, fp20_MIDDLEBRANCH, fp20_PENALTYBRANCH, fp20_STRONGBRANCH, ILL_CLEANUP_IF, ILL_RETURN, fp20_mipinfo::lp, fp20_mipinfo::pinf, and fp20_mipinfo::uppen.

Here is the call graph for this function:

static void fp20_find_first_branch ( fp20_lpinfo lp,
EGfp20_t *  x,
int *  bvar 
) [static]

Definition at line 1037 of file fp20_binary.c.

References fp20_ILL_INTTOL, fp20_ILLlpdata::intmarker, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, and t.

Referenced by fp20_find_branch().

static void fp20_find_middle_branch ( fp20_lpinfo lp,
EGfp20_t *  x,
int *  bvar 
) [static]

Definition at line 1068 of file fp20_binary.c.

References fp20_ILLlpdata::intmarker, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, and t.

Referenced by fp20_find_branch(), and fp20_plunge_work().

static int fp20_find_penalty_branch ( fp20_lpinfo lp,
fp20_price_info pinf,
EGfp20_t *  x,
EGfp20_t *  downpen,
EGfp20_t *  uppen,
EGfp20_t *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1117 of file fp20_binary.c.

References fp20_ILL_INTTOL, fp20_ILL_MINDOUBLE, ILL_SAFE_MALLOC, fp20_ILLlpdata::intmarker, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, and t.

Referenced by fp20_find_branch().

static int fp20_find_strong_branch ( fp20_lpinfo lp,
fp20_price_info pinf,
EGfp20_t *  x,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1238 of file fp20_binary.c.

References fp20_ILL_INTTOL, fp20_ILL_MINDOUBLE, fp20_STRONG_CANDIDATES, ILL_SAFE_MALLOC, ILLutil_sprand(), fp20_ILLlpdata::intmarker, fp20_ILLlpdata::nstruct, and fp20_lpinfo::O.

Referenced by fp20_find_branch().

Here is the call graph for this function:

static int fp20_fix_variables ( fp20_lpinfo lp,
EGfp20_t *  bestval,
fp20_bbnode b,
EGfp20_t *  wupper,
EGfp20_t *  wlower,
int *  hit 
) [static]

Definition at line 846 of file fp20_binary.c.

References fp20_bbnode::bound_cnt, fp20_bbnode::bound_indx, fp20_bbnode::bounds, fp20_ILL_INTTOL, fp20_ILL_MAXDOUBLE, fp20_ILLlib_chgbnd(), fp20_ILLlib_objval(), fp20_ILLlib_solution(), ILL_CLEANUP_IF, ILL_SAFE_MALLOC, fp20_ILLlpdata::intmarker, fp20_bbnode::lu, fp20_ILLlpdata::nstruct, and fp20_lpinfo::O.

Here is the call graph for this function:

static void fp20_free_bbnode ( fp20_bbnode b  )  [static]

Definition at line 1748 of file fp20_binary.c.

References fp20_bbnode::bound, fp20_bbnode::bound_indx, fp20_bbnode::bounds, fp20_bbnode::cstat, ILL_IFFREE, fp20_bbnode::lu, fp20_bbnode::rownorms, and fp20_bbnode::rstat.

Referenced by fp20_run_bfs().

static void fp20_free_mipinfo ( fp20_mipinfo minf  )  [static]

Definition at line 1700 of file fp20_binary.c.

References fp20_mipinfo::bestx, fp20_mipinfo::downpen, fp20_mipinfo::head_bbnode, ILLptrworld_delete(), fp20_mipinfo::lower, fp20_bbnode::next, fp20_mipinfo::objectivebound, fp20_mipinfo::ptrworld, fp20_mipinfo::uppen, fp20_mipinfo::upper, fp20_mipinfo::value, and fp20_mipinfo::x.

Referenced by fp20_ILLmip_bfs().

Here is the call graph for this function:

int fp20_ILLmip_bfs ( fp20_lpinfo lp,
EGfp20_t *  val,
EGfp20_t *  x,
itcnt_t itcnt 
)

Definition at line 176 of file fp20_binary.c.

References fp20_mipinfo::activenodes, fp20_mipinfo::bestx, fp20_bbnode::bound, fp20_mipinfo::branching_rule, fp20_bbnode::cstat, fp20_bbnode::depth, fp20_price_info::dII_price, fp20_cleanup_mip(), fp20_copy_x(), fp20_free_mipinfo(), fp20_ILL_MAX, fp20_ILL_MAXDOUBLE, fp20_ILLlib_getbasis(), fp20_ILLlib_getrownorms(), fp20_ILLprice_free_pricing_info(), fp20_ILLprice_init_pricing_info(), fp20_ILLutil_priority_free(), fp20_ILLutil_priority_init(), fp20_ILLutil_priority_insert(), fp20_init_bbnode(), fp20_init_mipinfo(), fp20_PENALTYBRANCH, fp20_run_bfs(), fp20_startup_mip(), fp20_mipinfo::head_bbnode, fp20_price_info::htrigger, fp20_bbnode::id, ILL_CLEANUP_IF, ILL_IFFREE, ILL_RETURN, ILL_SAFE_MALLOC, ILLutil_zeit(), fp20_bbnode::next, fp20_lpinfo::nrows, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, fp20_mipinfo::objsense, fp20_mipinfo::ptrworld, QS_PRICE_DSTEEP, fp20_mipinfo::que, fp20_bbnode::rownorms, fp20_bbnode::rstat, fp20_mipinfo::totalnodes, fp20_mipinfo::totalpivots, and fp20_mipinfo::value.

Referenced by fp20_solver_main().

Here is the call graph for this function:

static void fp20_init_bbnode ( fp20_bbnode b  )  [static]

Definition at line 1726 of file fp20_binary.c.

References fp20_bbnode::bound, fp20_bbnode::bound_cnt, fp20_bbnode::bound_indx, fp20_bbnode::bounds, fp20_bbnode::cstat, fp20_bbnode::depth, fp20_ILL_MINDOUBLE, fp20_bbnode::handle, fp20_bbnode::id, fp20_bbnode::lu, fp20_bbnode::next, fp20_bbnode::prev, fp20_bbnode::rownorms, and fp20_bbnode::rstat.

Referenced by fp20_child_work(), and fp20_ILLmip_bfs().

static void fp20_init_mipinfo ( fp20_mipinfo minf  )  [static]

Definition at line 1669 of file fp20_binary.c.

References fp20_mipinfo::activenodes, fp20_mipinfo::bestx, fp20_mipinfo::branching_rule, fp20_mipinfo::depth, fp20_mipinfo::downpen, fp20_ILL_MAXDOUBLE, fp20_STRONGBRANCH, fp20_mipinfo::head_bbnode, ILLptrworld_init(), fp20_mipinfo::lastpivots, fp20_mipinfo::lower, fp20_mipinfo::lp, fp20_bbnode::next, fp20_mipinfo::objectivebound, fp20_mipinfo::pinf, fp20_bbnode::prev, fp20_mipinfo::ptrworld, fp20_mipinfo::que, fp20_mipinfo::totalnodes, fp20_mipinfo::totalpivots, fp20_mipinfo::uppen, fp20_mipinfo::upper, fp20_mipinfo::value, fp20_mipinfo::watch, and fp20_mipinfo::x.

Referenced by fp20_ILLmip_bfs().

Here is the call graph for this function:

static int fp20_plunge ( fp20_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 1407 of file fp20_binary.c.

References DUAL_SIMPLEX, fp20_ILLlib_chgbnd(), fp20_ILLlib_optimize(), fp20_plunge_work(), ILL_CLEANUP_IF, ILL_RETURN, fp20_mipinfo::lower, fp20_mipinfo::lp, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, fp20_mipinfo::pinf, fp20_mipinfo::upper, and fp20_mipinfo::watch.

Here is the call graph for this function:

static int fp20_plunge_work ( fp20_mipinfo minf,
int  depth,
itcnt_t itcnt 
) [static]

Definition at line 1458 of file fp20_binary.c.

References fp20_mipinfo::bestx, DUAL_SIMPLEX, fp20_copy_x(), fp20_find_middle_branch(), fp20_ILL_INTTOL, fp20_ILL_MAXDOUBLE, fp20_ILLlib_chgbnd(), fp20_ILLlib_get_x(), fp20_ILLlib_objval(), fp20_ILLlib_optimize(), fp20_round_variables(), ILL_CLEANUP, ILL_CLEANUP_IF, ILL_RETURN, fp20_mipinfo::lower, fp20_mipinfo::lp, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, fp20_mipinfo::objectivebound, fp20_mipinfo::pinf, QS_LP_INFEASIBLE, QS_LP_OPTIMAL, QS_LP_UNSOLVED, fp20_mipinfo::upper, fp20_mipinfo::value, and fp20_mipinfo::x.

Referenced by fp20_plunge().

Here is the call graph for this function:

static int fp20_process_bfs_bbnode ( fp20_mipinfo minf,
fp20_bbnode active,
itcnt_t itcnt 
) [static]

Definition at line 432 of file fp20_binary.c.

References fp20_mipinfo::activenodes, fp20_bbnode::bound, fp20_bbnode::bound_cnt, fp20_bbnode::bound_indx, fp20_bbnode::bounds, fp20_ILL_MAXDOUBLE, fp20_ILLlib_chgbnds(), fp20_ILLlp_basis_init(), fp20_bbnode::id, ILL_CLEANUP_IF, fp20_mipinfo::lastpivots, fp20_mipinfo::lp, fp20_bbnode::lu, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, fp20_mipinfo::objectivebound, fp20_mipinfo::orig_lower, fp20_mipinfo::orig_upper, t, fp20_mipinfo::totalpivots, fp20_mipinfo::value, and fp20_mipinfo::watch.

Referenced by fp20_run_bfs().

Here is the call graph for this function:

static void fp20_put_bbnode ( fp20_mipinfo minf,
fp20_bbnode b 
) [static]

Definition at line 980 of file fp20_binary.c.

References fp20_mipinfo::head_bbnode, fp20_bbnode::next, and fp20_bbnode::prev.

Referenced by fp20_child_work().

static void fp20_remove_bbnode ( fp20_bbnode b  )  [static]

Definition at line 991 of file fp20_binary.c.

References fp20_bbnode::next, and fp20_bbnode::prev.

Referenced by fp20_run_bfs().

static int fp20_round_variables ( fp20_mipinfo minf,
int *  count,
EGfp20_t *  tol 
) [static]

Definition at line 1614 of file fp20_binary.c.

References fp20_ILLlib_chgbnd(), ILL_CLEANUP_IF, fp20_ILLlpdata::intmarker, fp20_mipinfo::lower, fp20_mipinfo::lp, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, fp20_mipinfo::upper, and fp20_mipinfo::x.

Referenced by fp20_plunge_work().

Here is the call graph for this function:

static int fp20_run_bfs ( fp20_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 409 of file fp20_binary.c.

References fp20_mipinfo::activenodes, fp20_best_bbnode(), fp20_free_bbnode(), fp20_process_bfs_bbnode(), fp20_remove_bbnode(), fp20_mipinfo::head_bbnode, ILL_CLEANUP_IF, ILL_RETURN, fp20_bbnode::next, and fp20_mipinfo::ptrworld.

Referenced by fp20_ILLmip_bfs().

Here is the call graph for this function:

static int fp20_startup_mip ( fp20_mipinfo minf,
fp20_lpinfo lp,
fp20_price_info pinf,
EGfp20_t *  lpval,
itcnt_t itcnt 
) [static]

Definition at line 274 of file fp20_binary.c.

References DUAL_SIMPLEX, fp20_ILL_MAXDOUBLE, fp20_ILL_MINDOUBLE, fp20_ILLlib_iter(), fp20_ILLlib_objval(), fp20_ILLlib_optimize(), ILL_CLEANUP_IF, fp20_ILLlpdata::intmarker, fp20_ILLlpdata::lower, fp20_ILLlpdata::nstruct, fp20_lpinfo::O, fp20_ILLlpdata::structmap, fp20_mipinfo::totalpivots, and fp20_ILLlpdata::upper.

Referenced by fp20_ILLmip_bfs().

Here is the call graph for this function:

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

Definition at line 132 of file fp20_binary.c.

References QS_PRICE_DSTEEP, and QS_PRICE_PSTEEP.


Variable Documentation

int TRACE = 0 [static]

Definition at line 24 of file fp20_binary.c.


Generated on Thu Mar 29 09:37:30 2012 for QSopt_ex by  doxygen 1.4.7