ldbl_binary.c File Reference

#include "qs_config.h"
#include "ldbl_priority.h"
#include "ldbl_sortrus.h"
#include "ldbl_iqsutil.h"
#include "ldbl_lpdata.h"
#include "ldbl_lpdefs.h"
#include "ldbl_simplex.h"
#include "ldbl_binary.h"
#include "ldbl_price.h"
#include "ldbl_lib.h"
#include "ldbl_qstruct.h"
#include "ldbl_qsopt.h"

Include dependency graph for ldbl_binary.c:

Go to the source code of this file.

Data Structures

struct  ldbl_bbnode
struct  ldbl_mipinfo

Defines

#define ldbl_FIRSTBRANCH   1
#define ldbl_ILL_BRANCH_PENALTY_VAL(v0, v1, f)
#define ldbl_ILL_BRANCH_PENALTY_WEIGHT   (2)
#define ldbl_ILL_BRANCH_STRONG_VAL(v0, v1)
#define ldbl_ILL_BRANCH_STRONG_WEIGHT   (10)
#define ldbl_ILL_INTTOL   ldbl_PFEAS_TOLER
#define ldbl_MIDDLEBRANCH   2
#define ldbl_PENALTYBRANCH   4
#define ldbl_STRONG_CANDIDATES   (10)
#define ldbl_STRONG_PIVOTS   (50)
#define ldbl_STRONGBRANCH   3

Functions

 ILL_PTRWORLD_ROUTINES (ILL_PTRWORLD_LISTFREE_ROUTINE(ldbl_bbnode, bbnodealloc, bbnode_bulkalloc, bbnodefree)
static void ldbl_best_bbnode (ldbl_mipinfo *minf, ldbl_bbnode **best)
static void ldbl_check_integral (ldbl_lpinfo *lp, long double *x, int *yesno)
static int ldbl_child_work (ldbl_mipinfo *minf, ldbl_bbnode *active, int bvar, int bdir, long double *cval, int *cp, itcnt_t *itcnt)
static void ldbl_cleanup_mip (ldbl_mipinfo *minf)
static void ldbl_copy_x (int nstruct, long double *from_x, long double *to_x)
static int ldbl_find_branch (ldbl_mipinfo *minf, long double *x, long double *lpval, int *bvar, itcnt_t *itcnt)
static void ldbl_find_first_branch (ldbl_lpinfo *lp, long double *x, int *bvar)
static void ldbl_find_middle_branch (ldbl_lpinfo *lp, long double *x, int *bvar)
static int ldbl_find_penalty_branch (ldbl_lpinfo *lp, ldbl_price_info *pinf, long double *x, long double *downpen, long double *uppen, long double *lpval, int *bvar, itcnt_t *itcnt)
static int ldbl_find_strong_branch (ldbl_lpinfo *lp, ldbl_price_info *pinf, long double *x, int *bvar, itcnt_t *itcnt)
static int ldbl_fix_variables (ldbl_lpinfo *lp, long double *bestval, ldbl_bbnode *b, long double *wupper, long double *wlower, int *hit)
static void ldbl_free_bbnode (ldbl_bbnode *b)
static void ldbl_free_mipinfo (ldbl_mipinfo *minf)
int ldbl_ILLmip_bfs (ldbl_lpinfo *lp, long double *val, long double *x, itcnt_t *itcnt)
static void ldbl_init_bbnode (ldbl_bbnode *b)
static void ldbl_init_mipinfo (ldbl_mipinfo *minf)
static int ldbl_plunge (ldbl_mipinfo *minf, itcnt_t *itcnt)
static int ldbl_plunge_work (ldbl_mipinfo *minf, int depth, itcnt_t *itcnt)
static int ldbl_process_bfs_bbnode (ldbl_mipinfo *minf, ldbl_bbnode *active, itcnt_t *itcnt)
static void ldbl_put_bbnode (ldbl_mipinfo *minf, ldbl_bbnode *b)
static void ldbl_remove_bbnode (ldbl_bbnode *b)
static int ldbl_round_variables (ldbl_mipinfo *minf, int *count, long double *tol)
static int ldbl_run_bfs (ldbl_mipinfo *minf, itcnt_t *itcnt)
static int ldbl_startup_mip (ldbl_mipinfo *minf, ldbl_lpinfo *lp, ldbl_price_info *pinf, long double *lpval, itcnt_t *itcnt)

Variables

static int TRACE = 0


Define Documentation

#define ldbl_FIRSTBRANCH   1

Definition at line 76 of file ldbl_binary.c.

Referenced by ldbl_find_branch().

#define ldbl_ILL_BRANCH_PENALTY_VAL ( v0,
v1,
 ) 

Value:

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

Definition at line 68 of file ldbl_binary.c.

#define ldbl_ILL_BRANCH_PENALTY_WEIGHT   (2)

Definition at line 67 of file ldbl_binary.c.

#define ldbl_ILL_BRANCH_STRONG_VAL ( v0,
v1   ) 

Value:

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

Definition at line 62 of file ldbl_binary.c.

#define ldbl_ILL_BRANCH_STRONG_WEIGHT   (10)

Definition at line 61 of file ldbl_binary.c.

#define ldbl_ILL_INTTOL   ldbl_PFEAS_TOLER

Definition at line 56 of file ldbl_binary.c.

Referenced by ldbl_check_integral(), ldbl_child_work(), ldbl_find_first_branch(), ldbl_find_penalty_branch(), ldbl_find_strong_branch(), ldbl_fix_variables(), and ldbl_plunge_work().

#define ldbl_MIDDLEBRANCH   2

Definition at line 77 of file ldbl_binary.c.

Referenced by ldbl_find_branch().

#define ldbl_PENALTYBRANCH   4

Definition at line 79 of file ldbl_binary.c.

Referenced by ldbl_find_branch(), and ldbl_ILLmip_bfs().

#define ldbl_STRONG_CANDIDATES   (10)

Definition at line 59 of file ldbl_binary.c.

Referenced by ldbl_find_strong_branch().

#define ldbl_STRONG_PIVOTS   (50)

Definition at line 58 of file ldbl_binary.c.

#define ldbl_STRONGBRANCH   3

Definition at line 78 of file ldbl_binary.c.

Referenced by ldbl_find_branch(), and ldbl_init_mipinfo().


Function Documentation

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

Definition at line 132 of file ldbl_binary.c.

References QS_PRICE_DSTEEP, and QS_PRICE_PSTEEP.

static void ldbl_best_bbnode ( ldbl_mipinfo minf,
ldbl_bbnode **  best 
) [static]

Definition at line 955 of file ldbl_binary.c.

References ldbl_bbnode::bound, ldbl_mipinfo::head_bbnode, ldbl_ILL_MAXDOUBLE, ldbl_ILLutil_priority_deletemin(), ldbl_bbnode::next, and ldbl_mipinfo::que.

Referenced by ldbl_run_bfs().

Here is the call graph for this function:

static void ldbl_check_integral ( ldbl_lpinfo lp,
long double *  x,
int *  yesno 
) [static]

Definition at line 1373 of file ldbl_binary.c.

References ldbl_ILLlpdata::intmarker, ldbl_ILL_INTTOL, ldbl_ILLlpdata::nstruct, and ldbl_lpinfo::O.

Referenced by ldbl_child_work().

static int ldbl_child_work ( ldbl_mipinfo minf,
ldbl_bbnode active,
int  bvar,
int  bdir,
long double *  cval,
int *  cp,
itcnt_t itcnt 
) [static]

Definition at line 691 of file ldbl_binary.c.

References ldbl_mipinfo::bestx, ldbl_bbnode::bound, ldbl_bbnode::bound_cnt, ldbl_bbnode::bound_indx, ldbl_bbnode::bounds, ldbl_bbnode::cstat, ldbl_bbnode::depth, ldbl_price_info::dII_price, DUAL_SIMPLEX, ldbl_bbnode::id, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_SAFE_MALLOC, ldbl_mipinfo::lastpivots, ldbl_check_integral(), ldbl_copy_x(), ldbl_ILL_INTTOL, ldbl_ILL_MAXDOUBLE, ldbl_ILLlib_chgbnd(), ldbl_ILLlib_getbasis(), ldbl_ILLlib_getbnd(), ldbl_ILLlib_getrownorms(), ldbl_ILLlib_iter(), ldbl_ILLlib_objval(), ldbl_ILLlib_optimize(), ldbl_ILLutil_priority_insert(), ldbl_init_bbnode(), ldbl_put_bbnode(), ldbl_mipinfo::lp, ldbl_bbnode::lu, ldbl_lpinfo::nrows, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, ldbl_mipinfo::objectivebound, ldbl_mipinfo::pinf, ldbl_mipinfo::ptrworld, QS_LP_INFEASIBLE, QS_LP_UNSOLVED, QS_PRICE_DSTEEP, ldbl_mipinfo::que, ldbl_bbnode::rownorms, ldbl_bbnode::rstat, ldbl_mipinfo::totalnodes, ldbl_mipinfo::totalpivots, ldbl_mipinfo::value, and ldbl_mipinfo::x.

Here is the call graph for this function:

static void ldbl_cleanup_mip ( ldbl_mipinfo minf  )  [static]

Definition at line 389 of file ldbl_binary.c.

References ldbl_ILL_MAX, ldbl_ILL_MIN, ldbl_mipinfo::lp, ldbl_lpinfo::ncols, ldbl_lpinfo::O, ldbl_ILLlpdata::obj, ldbl_ILLlpdata::objsense, and ldbl_mipinfo::objsense.

Referenced by ldbl_ILLmip_bfs().

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

Definition at line 1656 of file ldbl_binary.c.

Referenced by ldbl_child_work(), ldbl_ILLmip_bfs(), and ldbl_plunge_work().

static int ldbl_find_branch ( ldbl_mipinfo minf,
long double *  x,
long double *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 999 of file ldbl_binary.c.

References ldbl_mipinfo::branching_rule, ldbl_mipinfo::downpen, ILL_CLEANUP_IF, ILL_RETURN, ldbl_find_first_branch(), ldbl_find_middle_branch(), ldbl_find_penalty_branch(), ldbl_find_strong_branch(), ldbl_FIRSTBRANCH, ldbl_MIDDLEBRANCH, ldbl_PENALTYBRANCH, ldbl_STRONGBRANCH, ldbl_mipinfo::lp, ldbl_mipinfo::pinf, and ldbl_mipinfo::uppen.

Here is the call graph for this function:

static void ldbl_find_first_branch ( ldbl_lpinfo lp,
long double *  x,
int *  bvar 
) [static]

Definition at line 1037 of file ldbl_binary.c.

References ldbl_ILLlpdata::intmarker, ldbl_ILL_INTTOL, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, and t.

Referenced by ldbl_find_branch().

static void ldbl_find_middle_branch ( ldbl_lpinfo lp,
long double *  x,
int *  bvar 
) [static]

Definition at line 1068 of file ldbl_binary.c.

References ldbl_ILLlpdata::intmarker, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, and t.

Referenced by ldbl_find_branch(), and ldbl_plunge_work().

static int ldbl_find_penalty_branch ( ldbl_lpinfo lp,
ldbl_price_info pinf,
long double *  x,
long double *  downpen,
long double *  uppen,
long double *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1117 of file ldbl_binary.c.

References ILL_SAFE_MALLOC, ldbl_ILLlpdata::intmarker, ldbl_ILL_INTTOL, ldbl_ILL_MINDOUBLE, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, and t.

Referenced by ldbl_find_branch().

static int ldbl_find_strong_branch ( ldbl_lpinfo lp,
ldbl_price_info pinf,
long double *  x,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1238 of file ldbl_binary.c.

References ILL_SAFE_MALLOC, ILLutil_sprand(), ldbl_ILLlpdata::intmarker, ldbl_ILL_INTTOL, ldbl_ILL_MINDOUBLE, ldbl_STRONG_CANDIDATES, ldbl_ILLlpdata::nstruct, and ldbl_lpinfo::O.

Referenced by ldbl_find_branch().

Here is the call graph for this function:

static int ldbl_fix_variables ( ldbl_lpinfo lp,
long double *  bestval,
ldbl_bbnode b,
long double *  wupper,
long double *  wlower,
int *  hit 
) [static]

Definition at line 846 of file ldbl_binary.c.

References ldbl_bbnode::bound_cnt, ldbl_bbnode::bound_indx, ldbl_bbnode::bounds, ILL_CLEANUP_IF, ILL_SAFE_MALLOC, ldbl_ILLlpdata::intmarker, ldbl_ILL_INTTOL, ldbl_ILL_MAXDOUBLE, ldbl_ILLlib_chgbnd(), ldbl_ILLlib_objval(), ldbl_ILLlib_solution(), ldbl_bbnode::lu, ldbl_ILLlpdata::nstruct, and ldbl_lpinfo::O.

Here is the call graph for this function:

static void ldbl_free_bbnode ( ldbl_bbnode b  )  [static]

Definition at line 1748 of file ldbl_binary.c.

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

Referenced by ldbl_run_bfs().

static void ldbl_free_mipinfo ( ldbl_mipinfo minf  )  [static]

Definition at line 1700 of file ldbl_binary.c.

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

Referenced by ldbl_ILLmip_bfs().

Here is the call graph for this function:

int ldbl_ILLmip_bfs ( ldbl_lpinfo lp,
long double *  val,
long double *  x,
itcnt_t itcnt 
)

Definition at line 176 of file ldbl_binary.c.

References ldbl_mipinfo::activenodes, ldbl_mipinfo::bestx, ldbl_bbnode::bound, ldbl_mipinfo::branching_rule, ldbl_bbnode::cstat, ldbl_bbnode::depth, ldbl_price_info::dII_price, ldbl_mipinfo::head_bbnode, ldbl_price_info::htrigger, ldbl_bbnode::id, ILL_CLEANUP_IF, ILL_IFFREE, ILL_RETURN, ILL_SAFE_MALLOC, ILLutil_zeit(), ldbl_cleanup_mip(), ldbl_copy_x(), ldbl_free_mipinfo(), ldbl_ILL_MAX, ldbl_ILL_MAXDOUBLE, ldbl_ILLlib_getbasis(), ldbl_ILLlib_getrownorms(), ldbl_ILLprice_free_pricing_info(), ldbl_ILLprice_init_pricing_info(), ldbl_ILLutil_priority_free(), ldbl_ILLutil_priority_init(), ldbl_ILLutil_priority_insert(), ldbl_init_bbnode(), ldbl_init_mipinfo(), ldbl_PENALTYBRANCH, ldbl_run_bfs(), ldbl_startup_mip(), ldbl_bbnode::next, ldbl_lpinfo::nrows, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, ldbl_mipinfo::objsense, ldbl_mipinfo::ptrworld, QS_PRICE_DSTEEP, ldbl_mipinfo::que, ldbl_bbnode::rownorms, ldbl_bbnode::rstat, ldbl_mipinfo::totalnodes, ldbl_mipinfo::totalpivots, and ldbl_mipinfo::value.

Referenced by ldbl_solver_main().

Here is the call graph for this function:

static void ldbl_init_bbnode ( ldbl_bbnode b  )  [static]

Definition at line 1726 of file ldbl_binary.c.

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

Referenced by ldbl_child_work(), and ldbl_ILLmip_bfs().

static void ldbl_init_mipinfo ( ldbl_mipinfo minf  )  [static]

Definition at line 1669 of file ldbl_binary.c.

References ldbl_mipinfo::activenodes, ldbl_mipinfo::bestx, ldbl_mipinfo::branching_rule, ldbl_mipinfo::depth, ldbl_mipinfo::downpen, ldbl_mipinfo::head_bbnode, ILLptrworld_init(), ldbl_mipinfo::lastpivots, ldbl_ILL_MAXDOUBLE, ldbl_STRONGBRANCH, ldbl_mipinfo::lower, ldbl_mipinfo::lp, ldbl_bbnode::next, ldbl_mipinfo::objectivebound, ldbl_mipinfo::pinf, ldbl_bbnode::prev, ldbl_mipinfo::ptrworld, ldbl_mipinfo::que, ldbl_mipinfo::totalnodes, ldbl_mipinfo::totalpivots, ldbl_mipinfo::uppen, ldbl_mipinfo::upper, ldbl_mipinfo::value, ldbl_mipinfo::watch, and ldbl_mipinfo::x.

Referenced by ldbl_ILLmip_bfs().

Here is the call graph for this function:

static int ldbl_plunge ( ldbl_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 1407 of file ldbl_binary.c.

References DUAL_SIMPLEX, ILL_CLEANUP_IF, ILL_RETURN, ldbl_ILLlib_chgbnd(), ldbl_ILLlib_optimize(), ldbl_plunge_work(), ldbl_mipinfo::lower, ldbl_mipinfo::lp, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, ldbl_mipinfo::pinf, ldbl_mipinfo::upper, and ldbl_mipinfo::watch.

Here is the call graph for this function:

static int ldbl_plunge_work ( ldbl_mipinfo minf,
int  depth,
itcnt_t itcnt 
) [static]

Definition at line 1458 of file ldbl_binary.c.

References ldbl_mipinfo::bestx, DUAL_SIMPLEX, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_RETURN, ldbl_copy_x(), ldbl_find_middle_branch(), ldbl_ILL_INTTOL, ldbl_ILL_MAXDOUBLE, ldbl_ILLlib_chgbnd(), ldbl_ILLlib_get_x(), ldbl_ILLlib_objval(), ldbl_ILLlib_optimize(), ldbl_round_variables(), ldbl_mipinfo::lower, ldbl_mipinfo::lp, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, ldbl_mipinfo::objectivebound, ldbl_mipinfo::pinf, QS_LP_INFEASIBLE, QS_LP_OPTIMAL, QS_LP_UNSOLVED, ldbl_mipinfo::upper, ldbl_mipinfo::value, and ldbl_mipinfo::x.

Referenced by ldbl_plunge().

Here is the call graph for this function:

static int ldbl_process_bfs_bbnode ( ldbl_mipinfo minf,
ldbl_bbnode active,
itcnt_t itcnt 
) [static]

Definition at line 432 of file ldbl_binary.c.

References ldbl_mipinfo::activenodes, ldbl_bbnode::bound, ldbl_bbnode::bound_cnt, ldbl_bbnode::bound_indx, ldbl_bbnode::bounds, ldbl_bbnode::id, ILL_CLEANUP_IF, ldbl_mipinfo::lastpivots, ldbl_ILL_MAXDOUBLE, ldbl_ILLlib_chgbnds(), ldbl_ILLlp_basis_init(), ldbl_mipinfo::lp, ldbl_bbnode::lu, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, ldbl_mipinfo::objectivebound, ldbl_mipinfo::orig_lower, ldbl_mipinfo::orig_upper, t, ldbl_mipinfo::totalpivots, ldbl_mipinfo::value, and ldbl_mipinfo::watch.

Referenced by ldbl_run_bfs().

Here is the call graph for this function:

static void ldbl_put_bbnode ( ldbl_mipinfo minf,
ldbl_bbnode b 
) [static]

Definition at line 980 of file ldbl_binary.c.

References ldbl_mipinfo::head_bbnode, ldbl_bbnode::next, and ldbl_bbnode::prev.

Referenced by ldbl_child_work().

static void ldbl_remove_bbnode ( ldbl_bbnode b  )  [static]

Definition at line 991 of file ldbl_binary.c.

References ldbl_bbnode::next, and ldbl_bbnode::prev.

Referenced by ldbl_run_bfs().

static int ldbl_round_variables ( ldbl_mipinfo minf,
int *  count,
long double *  tol 
) [static]

Definition at line 1614 of file ldbl_binary.c.

References ILL_CLEANUP_IF, ldbl_ILLlpdata::intmarker, ldbl_ILLlib_chgbnd(), ldbl_mipinfo::lower, ldbl_mipinfo::lp, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, ldbl_mipinfo::upper, and ldbl_mipinfo::x.

Referenced by ldbl_plunge_work().

Here is the call graph for this function:

static int ldbl_run_bfs ( ldbl_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 409 of file ldbl_binary.c.

References ldbl_mipinfo::activenodes, ldbl_mipinfo::head_bbnode, ILL_CLEANUP_IF, ILL_RETURN, ldbl_best_bbnode(), ldbl_free_bbnode(), ldbl_process_bfs_bbnode(), ldbl_remove_bbnode(), ldbl_bbnode::next, and ldbl_mipinfo::ptrworld.

Referenced by ldbl_ILLmip_bfs().

Here is the call graph for this function:

static int ldbl_startup_mip ( ldbl_mipinfo minf,
ldbl_lpinfo lp,
ldbl_price_info pinf,
long double *  lpval,
itcnt_t itcnt 
) [static]

Definition at line 274 of file ldbl_binary.c.

References DUAL_SIMPLEX, ILL_CLEANUP_IF, ldbl_ILLlpdata::intmarker, ldbl_ILL_MAXDOUBLE, ldbl_ILL_MINDOUBLE, ldbl_ILLlib_iter(), ldbl_ILLlib_objval(), ldbl_ILLlib_optimize(), ldbl_ILLlpdata::lower, ldbl_ILLlpdata::nstruct, ldbl_lpinfo::O, ldbl_ILLlpdata::structmap, ldbl_mipinfo::totalpivots, and ldbl_ILLlpdata::upper.

Referenced by ldbl_ILLmip_bfs().

Here is the call graph for this function:


Variable Documentation

int TRACE = 0 [static]

Definition at line 24 of file ldbl_binary.c.


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