dbl_binary.c File Reference

#include "qs_config.h"
#include "dbl_priority.h"
#include "dbl_sortrus.h"
#include "dbl_iqsutil.h"
#include "dbl_lpdata.h"
#include "dbl_lpdefs.h"
#include "dbl_simplex.h"
#include "dbl_binary.h"
#include "dbl_price.h"
#include "dbl_lib.h"
#include "dbl_qstruct.h"
#include "dbl_qsopt.h"

Include dependency graph for dbl_binary.c:

Go to the source code of this file.

Data Structures

struct  dbl_bbnode
struct  dbl_mipinfo

Defines

#define dbl_FIRSTBRANCH   1
#define dbl_ILL_BRANCH_PENALTY_VAL(v0, v1, f)
#define dbl_ILL_BRANCH_PENALTY_WEIGHT   (2)
#define dbl_ILL_BRANCH_STRONG_VAL(v0, v1)
#define dbl_ILL_BRANCH_STRONG_WEIGHT   (10)
#define dbl_ILL_INTTOL   dbl_PFEAS_TOLER
#define dbl_MIDDLEBRANCH   2
#define dbl_PENALTYBRANCH   4
#define dbl_STRONG_CANDIDATES   (10)
#define dbl_STRONG_PIVOTS   (50)
#define dbl_STRONGBRANCH   3

Functions

static void dbl_best_bbnode (dbl_mipinfo *minf, dbl_bbnode **best)
static void dbl_check_integral (dbl_lpinfo *lp, double *x, int *yesno)
static int dbl_child_work (dbl_mipinfo *minf, dbl_bbnode *active, int bvar, int bdir, double *cval, int *cp, itcnt_t *itcnt)
static void dbl_cleanup_mip (dbl_mipinfo *minf)
static void dbl_copy_x (int nstruct, double *from_x, double *to_x)
static int dbl_find_branch (dbl_mipinfo *minf, double *x, double *lpval, int *bvar, itcnt_t *itcnt)
static void dbl_find_first_branch (dbl_lpinfo *lp, double *x, int *bvar)
static void dbl_find_middle_branch (dbl_lpinfo *lp, double *x, int *bvar)
static int dbl_find_penalty_branch (dbl_lpinfo *lp, dbl_price_info *pinf, double *x, double *downpen, double *uppen, double *lpval, int *bvar, itcnt_t *itcnt)
static int dbl_find_strong_branch (dbl_lpinfo *lp, dbl_price_info *pinf, double *x, int *bvar, itcnt_t *itcnt)
static int dbl_fix_variables (dbl_lpinfo *lp, double *bestval, dbl_bbnode *b, double *wupper, double *wlower, int *hit)
static void dbl_free_bbnode (dbl_bbnode *b)
static void dbl_free_mipinfo (dbl_mipinfo *minf)
int dbl_ILLmip_bfs (dbl_lpinfo *lp, double *val, double *x, itcnt_t *itcnt)
static void dbl_init_bbnode (dbl_bbnode *b)
static void dbl_init_mipinfo (dbl_mipinfo *minf)
static int dbl_plunge (dbl_mipinfo *minf, itcnt_t *itcnt)
static int dbl_plunge_work (dbl_mipinfo *minf, int depth, itcnt_t *itcnt)
static int dbl_process_bfs_bbnode (dbl_mipinfo *minf, dbl_bbnode *active, itcnt_t *itcnt)
static void dbl_put_bbnode (dbl_mipinfo *minf, dbl_bbnode *b)
static void dbl_remove_bbnode (dbl_bbnode *b)
static int dbl_round_variables (dbl_mipinfo *minf, int *count, double *tol)
static int dbl_run_bfs (dbl_mipinfo *minf, itcnt_t *itcnt)
static int dbl_startup_mip (dbl_mipinfo *minf, dbl_lpinfo *lp, dbl_price_info *pinf, double *lpval, itcnt_t *itcnt)
 ILL_PTRWORLD_ROUTINES (ILL_PTRWORLD_LISTFREE_ROUTINE(dbl_bbnode, bbnodealloc, bbnode_bulkalloc, bbnodefree)

Variables

static int TRACE = 0


Define Documentation

#define dbl_FIRSTBRANCH   1

Definition at line 76 of file dbl_binary.c.

Referenced by dbl_find_branch().

#define dbl_ILL_BRANCH_PENALTY_VAL ( v0,
v1,
 ) 

Value:

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

Definition at line 68 of file dbl_binary.c.

#define dbl_ILL_BRANCH_PENALTY_WEIGHT   (2)

Definition at line 67 of file dbl_binary.c.

#define dbl_ILL_BRANCH_STRONG_VAL ( v0,
v1   ) 

Value:

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

Definition at line 62 of file dbl_binary.c.

#define dbl_ILL_BRANCH_STRONG_WEIGHT   (10)

Definition at line 61 of file dbl_binary.c.

#define dbl_ILL_INTTOL   dbl_PFEAS_TOLER

Definition at line 56 of file dbl_binary.c.

Referenced by dbl_check_integral(), dbl_child_work(), dbl_find_first_branch(), dbl_find_penalty_branch(), dbl_find_strong_branch(), dbl_fix_variables(), and dbl_plunge_work().

#define dbl_MIDDLEBRANCH   2

Definition at line 77 of file dbl_binary.c.

Referenced by dbl_find_branch().

#define dbl_PENALTYBRANCH   4

Definition at line 79 of file dbl_binary.c.

Referenced by dbl_find_branch(), and dbl_ILLmip_bfs().

#define dbl_STRONG_CANDIDATES   (10)

Definition at line 59 of file dbl_binary.c.

Referenced by dbl_find_strong_branch().

#define dbl_STRONG_PIVOTS   (50)

Definition at line 58 of file dbl_binary.c.

#define dbl_STRONGBRANCH   3

Definition at line 78 of file dbl_binary.c.

Referenced by dbl_find_branch(), and dbl_init_mipinfo().


Function Documentation

static void dbl_best_bbnode ( dbl_mipinfo minf,
dbl_bbnode **  best 
) [static]

Definition at line 955 of file dbl_binary.c.

References dbl_bbnode::bound, dbl_ILL_MAXDOUBLE, dbl_ILLutil_priority_deletemin(), dbl_mipinfo::head_bbnode, dbl_bbnode::next, and dbl_mipinfo::que.

Referenced by dbl_run_bfs().

Here is the call graph for this function:

static void dbl_check_integral ( dbl_lpinfo lp,
double *  x,
int *  yesno 
) [static]

Definition at line 1373 of file dbl_binary.c.

References dbl_ILL_INTTOL, dbl_ILLlpdata::intmarker, dbl_ILLlpdata::nstruct, and dbl_lpinfo::O.

Referenced by dbl_child_work().

static int dbl_child_work ( dbl_mipinfo minf,
dbl_bbnode active,
int  bvar,
int  bdir,
double *  cval,
int *  cp,
itcnt_t itcnt 
) [static]

Definition at line 691 of file dbl_binary.c.

References dbl_mipinfo::bestx, dbl_bbnode::bound, dbl_bbnode::bound_cnt, dbl_bbnode::bound_indx, dbl_bbnode::bounds, dbl_bbnode::cstat, dbl_check_integral(), dbl_copy_x(), dbl_ILL_INTTOL, dbl_ILL_MAXDOUBLE, dbl_ILLlib_chgbnd(), dbl_ILLlib_getbasis(), dbl_ILLlib_getbnd(), dbl_ILLlib_getrownorms(), dbl_ILLlib_iter(), dbl_ILLlib_objval(), dbl_ILLlib_optimize(), dbl_ILLutil_priority_insert(), dbl_init_bbnode(), dbl_put_bbnode(), dbl_bbnode::depth, dbl_price_info::dII_price, DUAL_SIMPLEX, dbl_bbnode::id, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_SAFE_MALLOC, dbl_mipinfo::lastpivots, dbl_mipinfo::lp, dbl_bbnode::lu, dbl_lpinfo::nrows, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, dbl_mipinfo::objectivebound, dbl_mipinfo::pinf, dbl_mipinfo::ptrworld, QS_LP_INFEASIBLE, QS_LP_UNSOLVED, QS_PRICE_DSTEEP, dbl_mipinfo::que, dbl_bbnode::rownorms, dbl_bbnode::rstat, dbl_mipinfo::totalnodes, dbl_mipinfo::totalpivots, dbl_mipinfo::value, and dbl_mipinfo::x.

Here is the call graph for this function:

static void dbl_cleanup_mip ( dbl_mipinfo minf  )  [static]

Definition at line 389 of file dbl_binary.c.

References dbl_ILL_MAX, dbl_ILL_MIN, dbl_mipinfo::lp, dbl_lpinfo::ncols, dbl_lpinfo::O, dbl_ILLlpdata::obj, dbl_ILLlpdata::objsense, and dbl_mipinfo::objsense.

Referenced by dbl_ILLmip_bfs().

static void dbl_copy_x ( int  nstruct,
double *  from_x,
double *  to_x 
) [static]

Definition at line 1656 of file dbl_binary.c.

Referenced by dbl_child_work(), dbl_ILLmip_bfs(), and dbl_plunge_work().

static int dbl_find_branch ( dbl_mipinfo minf,
double *  x,
double *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 999 of file dbl_binary.c.

References dbl_mipinfo::branching_rule, dbl_find_first_branch(), dbl_find_middle_branch(), dbl_find_penalty_branch(), dbl_find_strong_branch(), dbl_FIRSTBRANCH, dbl_MIDDLEBRANCH, dbl_PENALTYBRANCH, dbl_STRONGBRANCH, dbl_mipinfo::downpen, ILL_CLEANUP_IF, ILL_RETURN, dbl_mipinfo::lp, dbl_mipinfo::pinf, and dbl_mipinfo::uppen.

Here is the call graph for this function:

static void dbl_find_first_branch ( dbl_lpinfo lp,
double *  x,
int *  bvar 
) [static]

Definition at line 1037 of file dbl_binary.c.

References dbl_ILL_INTTOL, dbl_ILLlpdata::intmarker, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, and t.

Referenced by dbl_find_branch().

static void dbl_find_middle_branch ( dbl_lpinfo lp,
double *  x,
int *  bvar 
) [static]

Definition at line 1068 of file dbl_binary.c.

References dbl_ILLlpdata::intmarker, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, and t.

Referenced by dbl_find_branch(), and dbl_plunge_work().

static int dbl_find_penalty_branch ( dbl_lpinfo lp,
dbl_price_info pinf,
double *  x,
double *  downpen,
double *  uppen,
double *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1117 of file dbl_binary.c.

References dbl_ILL_INTTOL, dbl_ILL_MINDOUBLE, ILL_SAFE_MALLOC, dbl_ILLlpdata::intmarker, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, and t.

Referenced by dbl_find_branch().

static int dbl_find_strong_branch ( dbl_lpinfo lp,
dbl_price_info pinf,
double *  x,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1238 of file dbl_binary.c.

References dbl_ILL_INTTOL, dbl_ILL_MINDOUBLE, dbl_STRONG_CANDIDATES, ILL_SAFE_MALLOC, ILLutil_sprand(), dbl_ILLlpdata::intmarker, dbl_ILLlpdata::nstruct, and dbl_lpinfo::O.

Referenced by dbl_find_branch().

Here is the call graph for this function:

static int dbl_fix_variables ( dbl_lpinfo lp,
double *  bestval,
dbl_bbnode b,
double *  wupper,
double *  wlower,
int *  hit 
) [static]

Definition at line 846 of file dbl_binary.c.

References dbl_bbnode::bound_cnt, dbl_bbnode::bound_indx, dbl_bbnode::bounds, dbl_ILL_INTTOL, dbl_ILL_MAXDOUBLE, dbl_ILLlib_chgbnd(), dbl_ILLlib_objval(), dbl_ILLlib_solution(), ILL_CLEANUP_IF, ILL_SAFE_MALLOC, dbl_ILLlpdata::intmarker, dbl_bbnode::lu, dbl_ILLlpdata::nstruct, and dbl_lpinfo::O.

Here is the call graph for this function:

static void dbl_free_bbnode ( dbl_bbnode b  )  [static]

Definition at line 1748 of file dbl_binary.c.

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

Referenced by dbl_run_bfs().

static void dbl_free_mipinfo ( dbl_mipinfo minf  )  [static]

Definition at line 1700 of file dbl_binary.c.

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

Referenced by dbl_ILLmip_bfs().

Here is the call graph for this function:

int dbl_ILLmip_bfs ( dbl_lpinfo lp,
double *  val,
double *  x,
itcnt_t itcnt 
)

Definition at line 176 of file dbl_binary.c.

References dbl_mipinfo::activenodes, dbl_mipinfo::bestx, dbl_bbnode::bound, dbl_mipinfo::branching_rule, dbl_bbnode::cstat, dbl_cleanup_mip(), dbl_copy_x(), dbl_free_mipinfo(), dbl_ILL_MAX, dbl_ILL_MAXDOUBLE, dbl_ILLlib_getbasis(), dbl_ILLlib_getrownorms(), dbl_ILLprice_free_pricing_info(), dbl_ILLprice_init_pricing_info(), dbl_ILLutil_priority_free(), dbl_ILLutil_priority_init(), dbl_ILLutil_priority_insert(), dbl_init_bbnode(), dbl_init_mipinfo(), dbl_PENALTYBRANCH, dbl_run_bfs(), dbl_startup_mip(), dbl_bbnode::depth, dbl_price_info::dII_price, dbl_mipinfo::head_bbnode, dbl_price_info::htrigger, dbl_bbnode::id, ILL_CLEANUP_IF, ILL_IFFREE, ILL_RETURN, ILL_SAFE_MALLOC, ILLutil_zeit(), dbl_bbnode::next, dbl_lpinfo::nrows, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, dbl_mipinfo::objsense, dbl_mipinfo::ptrworld, QS_PRICE_DSTEEP, dbl_mipinfo::que, dbl_bbnode::rownorms, dbl_bbnode::rstat, dbl_mipinfo::totalnodes, dbl_mipinfo::totalpivots, and dbl_mipinfo::value.

Referenced by dbl_solver_main().

Here is the call graph for this function:

static void dbl_init_bbnode ( dbl_bbnode b  )  [static]

Definition at line 1726 of file dbl_binary.c.

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

Referenced by dbl_child_work(), and dbl_ILLmip_bfs().

static void dbl_init_mipinfo ( dbl_mipinfo minf  )  [static]

Definition at line 1669 of file dbl_binary.c.

References dbl_mipinfo::activenodes, dbl_mipinfo::bestx, dbl_mipinfo::branching_rule, dbl_ILL_MAXDOUBLE, dbl_STRONGBRANCH, dbl_mipinfo::depth, dbl_mipinfo::downpen, dbl_mipinfo::head_bbnode, ILLptrworld_init(), dbl_mipinfo::lastpivots, dbl_mipinfo::lower, dbl_mipinfo::lp, dbl_bbnode::next, dbl_mipinfo::objectivebound, dbl_mipinfo::pinf, dbl_bbnode::prev, dbl_mipinfo::ptrworld, dbl_mipinfo::que, dbl_mipinfo::totalnodes, dbl_mipinfo::totalpivots, dbl_mipinfo::uppen, dbl_mipinfo::upper, dbl_mipinfo::value, dbl_mipinfo::watch, and dbl_mipinfo::x.

Referenced by dbl_ILLmip_bfs().

Here is the call graph for this function:

static int dbl_plunge ( dbl_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 1407 of file dbl_binary.c.

References dbl_ILLlib_chgbnd(), dbl_ILLlib_optimize(), dbl_plunge_work(), DUAL_SIMPLEX, ILL_CLEANUP_IF, ILL_RETURN, dbl_mipinfo::lower, dbl_mipinfo::lp, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, dbl_mipinfo::pinf, dbl_mipinfo::upper, and dbl_mipinfo::watch.

Here is the call graph for this function:

static int dbl_plunge_work ( dbl_mipinfo minf,
int  depth,
itcnt_t itcnt 
) [static]

Definition at line 1458 of file dbl_binary.c.

References dbl_mipinfo::bestx, dbl_copy_x(), dbl_find_middle_branch(), dbl_ILL_INTTOL, dbl_ILL_MAXDOUBLE, dbl_ILLlib_chgbnd(), dbl_ILLlib_get_x(), dbl_ILLlib_objval(), dbl_ILLlib_optimize(), dbl_round_variables(), DUAL_SIMPLEX, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_RETURN, dbl_mipinfo::lower, dbl_mipinfo::lp, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, dbl_mipinfo::objectivebound, dbl_mipinfo::pinf, QS_LP_INFEASIBLE, QS_LP_OPTIMAL, QS_LP_UNSOLVED, dbl_mipinfo::upper, dbl_mipinfo::value, and dbl_mipinfo::x.

Referenced by dbl_plunge().

Here is the call graph for this function:

static int dbl_process_bfs_bbnode ( dbl_mipinfo minf,
dbl_bbnode active,
itcnt_t itcnt 
) [static]

Definition at line 432 of file dbl_binary.c.

References dbl_mipinfo::activenodes, dbl_bbnode::bound, dbl_bbnode::bound_cnt, dbl_bbnode::bound_indx, dbl_bbnode::bounds, dbl_ILL_MAXDOUBLE, dbl_ILLlib_chgbnds(), dbl_ILLlp_basis_init(), dbl_bbnode::id, ILL_CLEANUP_IF, dbl_mipinfo::lastpivots, dbl_mipinfo::lp, dbl_bbnode::lu, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, dbl_mipinfo::objectivebound, dbl_mipinfo::orig_lower, dbl_mipinfo::orig_upper, t, dbl_mipinfo::totalpivots, dbl_mipinfo::value, and dbl_mipinfo::watch.

Referenced by dbl_run_bfs().

Here is the call graph for this function:

static void dbl_put_bbnode ( dbl_mipinfo minf,
dbl_bbnode b 
) [static]

Definition at line 980 of file dbl_binary.c.

References dbl_mipinfo::head_bbnode, dbl_bbnode::next, and dbl_bbnode::prev.

Referenced by dbl_child_work().

static void dbl_remove_bbnode ( dbl_bbnode b  )  [static]

Definition at line 991 of file dbl_binary.c.

References dbl_bbnode::next, and dbl_bbnode::prev.

Referenced by dbl_run_bfs().

static int dbl_round_variables ( dbl_mipinfo minf,
int *  count,
double *  tol 
) [static]

Definition at line 1614 of file dbl_binary.c.

References dbl_ILLlib_chgbnd(), ILL_CLEANUP_IF, dbl_ILLlpdata::intmarker, dbl_mipinfo::lower, dbl_mipinfo::lp, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, dbl_mipinfo::upper, and dbl_mipinfo::x.

Referenced by dbl_plunge_work().

Here is the call graph for this function:

static int dbl_run_bfs ( dbl_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 409 of file dbl_binary.c.

References dbl_mipinfo::activenodes, dbl_best_bbnode(), dbl_free_bbnode(), dbl_process_bfs_bbnode(), dbl_remove_bbnode(), dbl_mipinfo::head_bbnode, ILL_CLEANUP_IF, ILL_RETURN, dbl_bbnode::next, and dbl_mipinfo::ptrworld.

Referenced by dbl_ILLmip_bfs().

Here is the call graph for this function:

static int dbl_startup_mip ( dbl_mipinfo minf,
dbl_lpinfo lp,
dbl_price_info pinf,
double *  lpval,
itcnt_t itcnt 
) [static]

Definition at line 274 of file dbl_binary.c.

References dbl_ILL_MAXDOUBLE, dbl_ILL_MINDOUBLE, dbl_ILLlib_iter(), dbl_ILLlib_objval(), dbl_ILLlib_optimize(), DUAL_SIMPLEX, ILL_CLEANUP_IF, dbl_ILLlpdata::intmarker, dbl_ILLlpdata::lower, dbl_ILLlpdata::nstruct, dbl_lpinfo::O, dbl_ILLlpdata::structmap, dbl_mipinfo::totalpivots, and dbl_ILLlpdata::upper.

Referenced by dbl_ILLmip_bfs().

Here is the call graph for this function:

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

Definition at line 132 of file dbl_binary.c.

References QS_PRICE_DSTEEP, and QS_PRICE_PSTEEP.


Variable Documentation

int TRACE = 0 [static]

Definition at line 24 of file dbl_binary.c.


Generated on Thu Mar 29 09:33:12 2012 for QSopt_ex by  doxygen 1.4.7