mpq_binary.c File Reference

#include "qs_config.h"
#include "mpq_priority.h"
#include "mpq_sortrus.h"
#include "mpq_iqsutil.h"
#include "mpq_lpdata.h"
#include "mpq_lpdefs.h"
#include "mpq_simplex.h"
#include "mpq_binary.h"
#include "mpq_price.h"
#include "mpq_lib.h"
#include "mpq_qstruct.h"
#include "mpq_qsopt.h"

Include dependency graph for mpq_binary.c:

Go to the source code of this file.

Data Structures

struct  mpq_bbnode
struct  mpq_mipinfo

Defines

#define mpq_FIRSTBRANCH   1
#define mpq_ILL_BRANCH_PENALTY_VAL(v0, v1, f)
#define mpq_ILL_BRANCH_PENALTY_WEIGHT   (2)
#define mpq_ILL_BRANCH_STRONG_VAL(v0, v1)
#define mpq_ILL_BRANCH_STRONG_WEIGHT   (10)
#define mpq_ILL_INTTOL   mpq_PFEAS_TOLER
#define mpq_MIDDLEBRANCH   2
#define mpq_PENALTYBRANCH   4
#define mpq_STRONG_CANDIDATES   (10)
#define mpq_STRONG_PIVOTS   (50)
#define mpq_STRONGBRANCH   3

Functions

 ILL_PTRWORLD_ROUTINES (ILL_PTRWORLD_LISTFREE_ROUTINE(mpq_bbnode, bbnodealloc, bbnode_bulkalloc, bbnodefree)
static void mpq_best_bbnode (mpq_mipinfo *minf, mpq_bbnode **best)
static void mpq_check_integral (mpq_lpinfo *lp, mpq_t *x, int *yesno)
static int mpq_child_work (mpq_mipinfo *minf, mpq_bbnode *active, int bvar, int bdir, mpq_t *cval, int *cp, itcnt_t *itcnt)
static void mpq_cleanup_mip (mpq_mipinfo *minf)
static void mpq_copy_x (int nstruct, mpq_t *from_x, mpq_t *to_x)
static int mpq_find_branch (mpq_mipinfo *minf, mpq_t *x, mpq_t *lpval, int *bvar, itcnt_t *itcnt)
static void mpq_find_first_branch (mpq_lpinfo *lp, mpq_t *x, int *bvar)
static void mpq_find_middle_branch (mpq_lpinfo *lp, mpq_t *x, int *bvar)
static int mpq_find_penalty_branch (mpq_lpinfo *lp, mpq_price_info *pinf, mpq_t *x, mpq_t *downpen, mpq_t *uppen, mpq_t *lpval, int *bvar, itcnt_t *itcnt)
static int mpq_find_strong_branch (mpq_lpinfo *lp, mpq_price_info *pinf, mpq_t *x, int *bvar, itcnt_t *itcnt)
static int mpq_fix_variables (mpq_lpinfo *lp, mpq_t *bestval, mpq_bbnode *b, mpq_t *wupper, mpq_t *wlower, int *hit)
static void mpq_free_bbnode (mpq_bbnode *b)
static void mpq_free_mipinfo (mpq_mipinfo *minf)
int mpq_ILLmip_bfs (mpq_lpinfo *lp, mpq_t *val, mpq_t *x, itcnt_t *itcnt)
static void mpq_init_bbnode (mpq_bbnode *b)
static void mpq_init_mipinfo (mpq_mipinfo *minf)
static int mpq_plunge (mpq_mipinfo *minf, itcnt_t *itcnt)
static int mpq_plunge_work (mpq_mipinfo *minf, int depth, itcnt_t *itcnt)
static int mpq_process_bfs_bbnode (mpq_mipinfo *minf, mpq_bbnode *active, itcnt_t *itcnt)
static void mpq_put_bbnode (mpq_mipinfo *minf, mpq_bbnode *b)
static void mpq_remove_bbnode (mpq_bbnode *b)
static int mpq_round_variables (mpq_mipinfo *minf, int *count, mpq_t *tol)
static int mpq_run_bfs (mpq_mipinfo *minf, itcnt_t *itcnt)
static int mpq_startup_mip (mpq_mipinfo *minf, mpq_lpinfo *lp, mpq_price_info *pinf, mpq_t *lpval, itcnt_t *itcnt)

Variables

static int TRACE = 0


Define Documentation

#define mpq_FIRSTBRANCH   1

Definition at line 76 of file mpq_binary.c.

Referenced by mpq_find_branch().

#define mpq_ILL_BRANCH_PENALTY_VAL ( v0,
v1,
 ) 

Value:

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

Definition at line 68 of file mpq_binary.c.

#define mpq_ILL_BRANCH_PENALTY_WEIGHT   (2)

Definition at line 67 of file mpq_binary.c.

#define mpq_ILL_BRANCH_STRONG_VAL ( v0,
v1   ) 

Value:

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

Definition at line 62 of file mpq_binary.c.

#define mpq_ILL_BRANCH_STRONG_WEIGHT   (10)

Definition at line 61 of file mpq_binary.c.

#define mpq_ILL_INTTOL   mpq_PFEAS_TOLER

Definition at line 56 of file mpq_binary.c.

Referenced by mpq_check_integral(), mpq_child_work(), mpq_find_first_branch(), mpq_find_penalty_branch(), mpq_find_strong_branch(), mpq_fix_variables(), and mpq_plunge_work().

#define mpq_MIDDLEBRANCH   2

Definition at line 77 of file mpq_binary.c.

Referenced by mpq_find_branch().

#define mpq_PENALTYBRANCH   4

Definition at line 79 of file mpq_binary.c.

Referenced by mpq_find_branch(), and mpq_ILLmip_bfs().

#define mpq_STRONG_CANDIDATES   (10)

Definition at line 59 of file mpq_binary.c.

Referenced by mpq_find_strong_branch().

#define mpq_STRONG_PIVOTS   (50)

Definition at line 58 of file mpq_binary.c.

#define mpq_STRONGBRANCH   3

Definition at line 78 of file mpq_binary.c.

Referenced by mpq_find_branch(), and mpq_init_mipinfo().


Function Documentation

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

Definition at line 132 of file mpq_binary.c.

References QS_PRICE_DSTEEP, and QS_PRICE_PSTEEP.

static void mpq_best_bbnode ( mpq_mipinfo minf,
mpq_bbnode **  best 
) [static]

Definition at line 955 of file mpq_binary.c.

References mpq_bbnode::bound, mpq_mipinfo::head_bbnode, mpq_ILL_MAXDOUBLE, mpq_ILLutil_priority_deletemin(), mpq_bbnode::next, and mpq_mipinfo::que.

Referenced by mpq_run_bfs().

Here is the call graph for this function:

static void mpq_check_integral ( mpq_lpinfo lp,
mpq_t *  x,
int *  yesno 
) [static]

Definition at line 1373 of file mpq_binary.c.

References mpq_ILLlpdata::intmarker, mpq_ILL_INTTOL, mpq_ILLlpdata::nstruct, and mpq_lpinfo::O.

Referenced by mpq_child_work().

static int mpq_child_work ( mpq_mipinfo minf,
mpq_bbnode active,
int  bvar,
int  bdir,
mpq_t *  cval,
int *  cp,
itcnt_t itcnt 
) [static]

Definition at line 691 of file mpq_binary.c.

References mpq_mipinfo::bestx, mpq_bbnode::bound, mpq_bbnode::bound_cnt, mpq_bbnode::bound_indx, mpq_bbnode::bounds, mpq_bbnode::cstat, mpq_bbnode::depth, mpq_price_info::dII_price, DUAL_SIMPLEX, mpq_bbnode::id, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_SAFE_MALLOC, mpq_mipinfo::lastpivots, mpq_mipinfo::lp, mpq_bbnode::lu, mpq_check_integral(), mpq_copy_x(), mpq_ILL_INTTOL, mpq_ILL_MAXDOUBLE, mpq_ILLlib_chgbnd(), mpq_ILLlib_getbasis(), mpq_ILLlib_getbnd(), mpq_ILLlib_getrownorms(), mpq_ILLlib_iter(), mpq_ILLlib_objval(), mpq_ILLlib_optimize(), mpq_ILLutil_priority_insert(), mpq_init_bbnode(), mpq_put_bbnode(), mpq_lpinfo::nrows, mpq_ILLlpdata::nstruct, mpq_lpinfo::O, mpq_mipinfo::objectivebound, mpq_mipinfo::pinf, mpq_mipinfo::ptrworld, QS_LP_INFEASIBLE, QS_LP_UNSOLVED, QS_PRICE_DSTEEP, mpq_mipinfo::que, mpq_bbnode::rownorms, mpq_bbnode::rstat, mpq_mipinfo::totalnodes, mpq_mipinfo::totalpivots, mpq_mipinfo::value, and mpq_mipinfo::x.

Here is the call graph for this function:

static void mpq_cleanup_mip ( mpq_mipinfo minf  )  [static]

Definition at line 389 of file mpq_binary.c.

References mpq_mipinfo::lp, mpq_ILL_MAX, mpq_ILL_MIN, mpq_lpinfo::ncols, mpq_lpinfo::O, mpq_ILLlpdata::obj, mpq_ILLlpdata::objsense, and mpq_mipinfo::objsense.

Referenced by mpq_ILLmip_bfs().

static void mpq_copy_x ( int  nstruct,
mpq_t *  from_x,
mpq_t *  to_x 
) [static]

Definition at line 1656 of file mpq_binary.c.

Referenced by mpq_child_work(), mpq_ILLmip_bfs(), and mpq_plunge_work().

static int mpq_find_branch ( mpq_mipinfo minf,
mpq_t *  x,
mpq_t *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 999 of file mpq_binary.c.

References mpq_mipinfo::branching_rule, mpq_mipinfo::downpen, ILL_CLEANUP_IF, ILL_RETURN, mpq_mipinfo::lp, mpq_find_first_branch(), mpq_find_middle_branch(), mpq_find_penalty_branch(), mpq_find_strong_branch(), mpq_FIRSTBRANCH, mpq_MIDDLEBRANCH, mpq_PENALTYBRANCH, mpq_STRONGBRANCH, mpq_mipinfo::pinf, and mpq_mipinfo::uppen.

Here is the call graph for this function:

static void mpq_find_first_branch ( mpq_lpinfo lp,
mpq_t *  x,
int *  bvar 
) [static]

Definition at line 1037 of file mpq_binary.c.

References mpq_ILLlpdata::intmarker, mpq_ILL_INTTOL, mpq_ILLlpdata::nstruct, mpq_lpinfo::O, and t.

Referenced by mpq_find_branch().

static void mpq_find_middle_branch ( mpq_lpinfo lp,
mpq_t *  x,
int *  bvar 
) [static]

Definition at line 1068 of file mpq_binary.c.

References mpq_ILLlpdata::intmarker, mpq_ILLlpdata::nstruct, mpq_lpinfo::O, and t.

Referenced by mpq_find_branch(), and mpq_plunge_work().

static int mpq_find_penalty_branch ( mpq_lpinfo lp,
mpq_price_info pinf,
mpq_t *  x,
mpq_t *  downpen,
mpq_t *  uppen,
mpq_t *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1117 of file mpq_binary.c.

References ILL_SAFE_MALLOC, mpq_ILLlpdata::intmarker, mpq_ILL_INTTOL, mpq_ILL_MINDOUBLE, mpq_ILLlpdata::nstruct, mpq_lpinfo::O, and t.

Referenced by mpq_find_branch().

static int mpq_find_strong_branch ( mpq_lpinfo lp,
mpq_price_info pinf,
mpq_t *  x,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1238 of file mpq_binary.c.

References ILL_SAFE_MALLOC, ILLutil_sprand(), mpq_ILLlpdata::intmarker, mpq_ILL_INTTOL, mpq_ILL_MINDOUBLE, mpq_STRONG_CANDIDATES, mpq_ILLlpdata::nstruct, and mpq_lpinfo::O.

Referenced by mpq_find_branch().

Here is the call graph for this function:

static int mpq_fix_variables ( mpq_lpinfo lp,
mpq_t *  bestval,
mpq_bbnode b,
mpq_t *  wupper,
mpq_t *  wlower,
int *  hit 
) [static]

Definition at line 846 of file mpq_binary.c.

References mpq_bbnode::bound_cnt, mpq_bbnode::bound_indx, mpq_bbnode::bounds, ILL_CLEANUP_IF, ILL_SAFE_MALLOC, mpq_ILLlpdata::intmarker, mpq_bbnode::lu, mpq_ILL_INTTOL, mpq_ILL_MAXDOUBLE, mpq_ILLlib_chgbnd(), mpq_ILLlib_objval(), mpq_ILLlib_solution(), mpq_ILLlpdata::nstruct, and mpq_lpinfo::O.

Here is the call graph for this function:

static void mpq_free_bbnode ( mpq_bbnode b  )  [static]

Definition at line 1748 of file mpq_binary.c.

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

Referenced by mpq_run_bfs().

static void mpq_free_mipinfo ( mpq_mipinfo minf  )  [static]

Definition at line 1700 of file mpq_binary.c.

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

Referenced by mpq_ILLmip_bfs().

Here is the call graph for this function:

int mpq_ILLmip_bfs ( mpq_lpinfo lp,
mpq_t *  val,
mpq_t *  x,
itcnt_t itcnt 
)

Definition at line 176 of file mpq_binary.c.

References mpq_mipinfo::activenodes, mpq_mipinfo::bestx, mpq_bbnode::bound, mpq_mipinfo::branching_rule, mpq_bbnode::cstat, mpq_bbnode::depth, mpq_price_info::dII_price, mpq_mipinfo::head_bbnode, mpq_price_info::htrigger, mpq_bbnode::id, ILL_CLEANUP_IF, ILL_IFFREE, ILL_RETURN, ILL_SAFE_MALLOC, ILLutil_zeit(), mpq_cleanup_mip(), mpq_copy_x(), mpq_free_mipinfo(), mpq_ILL_MAX, mpq_ILL_MAXDOUBLE, mpq_ILLlib_getbasis(), mpq_ILLlib_getrownorms(), mpq_ILLprice_free_pricing_info(), mpq_ILLprice_init_pricing_info(), mpq_ILLutil_priority_free(), mpq_ILLutil_priority_init(), mpq_ILLutil_priority_insert(), mpq_init_bbnode(), mpq_init_mipinfo(), mpq_PENALTYBRANCH, mpq_run_bfs(), mpq_startup_mip(), mpq_bbnode::next, mpq_lpinfo::nrows, mpq_ILLlpdata::nstruct, mpq_lpinfo::O, mpq_mipinfo::objsense, mpq_mipinfo::ptrworld, QS_PRICE_DSTEEP, mpq_mipinfo::que, mpq_bbnode::rownorms, mpq_bbnode::rstat, mpq_mipinfo::totalnodes, mpq_mipinfo::totalpivots, and mpq_mipinfo::value.

Referenced by mpq_solver_main().

Here is the call graph for this function:

static void mpq_init_bbnode ( mpq_bbnode b  )  [static]

Definition at line 1726 of file mpq_binary.c.

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

Referenced by mpq_child_work(), and mpq_ILLmip_bfs().

static void mpq_init_mipinfo ( mpq_mipinfo minf  )  [static]

Definition at line 1669 of file mpq_binary.c.

References mpq_mipinfo::activenodes, mpq_mipinfo::bestx, mpq_mipinfo::branching_rule, mpq_mipinfo::depth, mpq_mipinfo::downpen, mpq_mipinfo::head_bbnode, ILLptrworld_init(), mpq_mipinfo::lastpivots, mpq_mipinfo::lower, mpq_mipinfo::lp, mpq_ILL_MAXDOUBLE, mpq_STRONGBRANCH, mpq_bbnode::next, mpq_mipinfo::objectivebound, mpq_mipinfo::pinf, mpq_bbnode::prev, mpq_mipinfo::ptrworld, mpq_mipinfo::que, mpq_mipinfo::totalnodes, mpq_mipinfo::totalpivots, mpq_mipinfo::uppen, mpq_mipinfo::upper, mpq_mipinfo::value, mpq_mipinfo::watch, and mpq_mipinfo::x.

Referenced by mpq_ILLmip_bfs().

Here is the call graph for this function:

static int mpq_plunge ( mpq_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 1407 of file mpq_binary.c.

References DUAL_SIMPLEX, ILL_CLEANUP_IF, ILL_RETURN, mpq_mipinfo::lower, mpq_mipinfo::lp, mpq_ILLlib_chgbnd(), mpq_ILLlib_optimize(), mpq_plunge_work(), mpq_ILLlpdata::nstruct, mpq_lpinfo::O, mpq_mipinfo::pinf, mpq_mipinfo::upper, and mpq_mipinfo::watch.

Here is the call graph for this function:

static int mpq_plunge_work ( mpq_mipinfo minf,
int  depth,
itcnt_t itcnt 
) [static]

Definition at line 1458 of file mpq_binary.c.

References mpq_mipinfo::bestx, DUAL_SIMPLEX, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_RETURN, mpq_mipinfo::lower, mpq_mipinfo::lp, mpq_copy_x(), mpq_find_middle_branch(), mpq_ILL_INTTOL, mpq_ILL_MAXDOUBLE, mpq_ILLlib_chgbnd(), mpq_ILLlib_get_x(), mpq_ILLlib_objval(), mpq_ILLlib_optimize(), mpq_round_variables(), mpq_ILLlpdata::nstruct, mpq_lpinfo::O, mpq_mipinfo::objectivebound, mpq_mipinfo::pinf, QS_LP_INFEASIBLE, QS_LP_OPTIMAL, QS_LP_UNSOLVED, mpq_mipinfo::upper, mpq_mipinfo::value, and mpq_mipinfo::x.

Referenced by mpq_plunge().

Here is the call graph for this function:

static int mpq_process_bfs_bbnode ( mpq_mipinfo minf,
mpq_bbnode active,
itcnt_t itcnt 
) [static]

Definition at line 432 of file mpq_binary.c.

References mpq_mipinfo::activenodes, mpq_bbnode::bound, mpq_bbnode::bound_cnt, mpq_bbnode::bound_indx, mpq_bbnode::bounds, mpq_bbnode::id, ILL_CLEANUP_IF, mpq_mipinfo::lastpivots, mpq_mipinfo::lp, mpq_bbnode::lu, mpq_ILL_MAXDOUBLE, mpq_ILLlib_chgbnds(), mpq_ILLlp_basis_init(), mpq_ILLlpdata::nstruct, mpq_lpinfo::O, mpq_mipinfo::objectivebound, mpq_mipinfo::orig_lower, mpq_mipinfo::orig_upper, t, mpq_mipinfo::totalpivots, mpq_mipinfo::value, and mpq_mipinfo::watch.

Referenced by mpq_run_bfs().

Here is the call graph for this function:

static void mpq_put_bbnode ( mpq_mipinfo minf,
mpq_bbnode b 
) [static]

Definition at line 980 of file mpq_binary.c.

References mpq_mipinfo::head_bbnode, mpq_bbnode::next, and mpq_bbnode::prev.

Referenced by mpq_child_work().

static void mpq_remove_bbnode ( mpq_bbnode b  )  [static]

Definition at line 991 of file mpq_binary.c.

References mpq_bbnode::next, and mpq_bbnode::prev.

Referenced by mpq_run_bfs().

static int mpq_round_variables ( mpq_mipinfo minf,
int *  count,
mpq_t *  tol 
) [static]

Definition at line 1614 of file mpq_binary.c.

References ILL_CLEANUP_IF, mpq_ILLlpdata::intmarker, mpq_mipinfo::lower, mpq_mipinfo::lp, mpq_ILLlib_chgbnd(), mpq_ILLlpdata::nstruct, mpq_lpinfo::O, mpq_mipinfo::upper, and mpq_mipinfo::x.

Referenced by mpq_plunge_work().

Here is the call graph for this function:

static int mpq_run_bfs ( mpq_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 409 of file mpq_binary.c.

References mpq_mipinfo::activenodes, mpq_mipinfo::head_bbnode, ILL_CLEANUP_IF, ILL_RETURN, mpq_best_bbnode(), mpq_free_bbnode(), mpq_process_bfs_bbnode(), mpq_remove_bbnode(), mpq_bbnode::next, and mpq_mipinfo::ptrworld.

Referenced by mpq_ILLmip_bfs().

Here is the call graph for this function:

static int mpq_startup_mip ( mpq_mipinfo minf,
mpq_lpinfo lp,
mpq_price_info pinf,
mpq_t *  lpval,
itcnt_t itcnt 
) [static]

Definition at line 274 of file mpq_binary.c.

References DUAL_SIMPLEX, ILL_CLEANUP_IF, mpq_ILLlpdata::intmarker, mpq_ILLlpdata::lower, mpq_ILL_MAXDOUBLE, mpq_ILL_MINDOUBLE, mpq_ILLlib_iter(), mpq_ILLlib_objval(), mpq_ILLlib_optimize(), mpq_ILLlpdata::nstruct, mpq_lpinfo::O, mpq_ILLlpdata::structmap, mpq_mipinfo::totalpivots, and mpq_ILLlpdata::upper.

Referenced by mpq_ILLmip_bfs().

Here is the call graph for this function:


Variable Documentation

int TRACE = 0 [static]

Definition at line 24 of file mpq_binary.c.


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