mpf_binary.c File Reference

#include "qs_config.h"
#include "mpf_priority.h"
#include "mpf_sortrus.h"
#include "mpf_iqsutil.h"
#include "mpf_lpdata.h"
#include "mpf_lpdefs.h"
#include "mpf_simplex.h"
#include "mpf_binary.h"
#include "mpf_price.h"
#include "mpf_lib.h"
#include "mpf_qstruct.h"
#include "mpf_qsopt.h"

Include dependency graph for mpf_binary.c:

Go to the source code of this file.

Data Structures

struct  mpf_bbnode
struct  mpf_mipinfo

Defines

#define mpf_FIRSTBRANCH   1
#define mpf_ILL_BRANCH_PENALTY_VAL(v0, v1, f)
#define mpf_ILL_BRANCH_PENALTY_WEIGHT   (2)
#define mpf_ILL_BRANCH_STRONG_VAL(v0, v1)
#define mpf_ILL_BRANCH_STRONG_WEIGHT   (10)
#define mpf_ILL_INTTOL   mpf_PFEAS_TOLER
#define mpf_MIDDLEBRANCH   2
#define mpf_PENALTYBRANCH   4
#define mpf_STRONG_CANDIDATES   (10)
#define mpf_STRONG_PIVOTS   (50)
#define mpf_STRONGBRANCH   3

Functions

 ILL_PTRWORLD_ROUTINES (ILL_PTRWORLD_LISTFREE_ROUTINE(mpf_bbnode, bbnodealloc, bbnode_bulkalloc, bbnodefree)
static void mpf_best_bbnode (mpf_mipinfo *minf, mpf_bbnode **best)
static void mpf_check_integral (mpf_lpinfo *lp, mpf_t *x, int *yesno)
static int mpf_child_work (mpf_mipinfo *minf, mpf_bbnode *active, int bvar, int bdir, mpf_t *cval, int *cp, itcnt_t *itcnt)
static void mpf_cleanup_mip (mpf_mipinfo *minf)
static void mpf_copy_x (int nstruct, mpf_t *from_x, mpf_t *to_x)
static int mpf_find_branch (mpf_mipinfo *minf, mpf_t *x, mpf_t *lpval, int *bvar, itcnt_t *itcnt)
static void mpf_find_first_branch (mpf_lpinfo *lp, mpf_t *x, int *bvar)
static void mpf_find_middle_branch (mpf_lpinfo *lp, mpf_t *x, int *bvar)
static int mpf_find_penalty_branch (mpf_lpinfo *lp, mpf_price_info *pinf, mpf_t *x, mpf_t *downpen, mpf_t *uppen, mpf_t *lpval, int *bvar, itcnt_t *itcnt)
static int mpf_find_strong_branch (mpf_lpinfo *lp, mpf_price_info *pinf, mpf_t *x, int *bvar, itcnt_t *itcnt)
static int mpf_fix_variables (mpf_lpinfo *lp, mpf_t *bestval, mpf_bbnode *b, mpf_t *wupper, mpf_t *wlower, int *hit)
static void mpf_free_bbnode (mpf_bbnode *b)
static void mpf_free_mipinfo (mpf_mipinfo *minf)
int mpf_ILLmip_bfs (mpf_lpinfo *lp, mpf_t *val, mpf_t *x, itcnt_t *itcnt)
static void mpf_init_bbnode (mpf_bbnode *b)
static void mpf_init_mipinfo (mpf_mipinfo *minf)
static int mpf_plunge (mpf_mipinfo *minf, itcnt_t *itcnt)
static int mpf_plunge_work (mpf_mipinfo *minf, int depth, itcnt_t *itcnt)
static int mpf_process_bfs_bbnode (mpf_mipinfo *minf, mpf_bbnode *active, itcnt_t *itcnt)
static void mpf_put_bbnode (mpf_mipinfo *minf, mpf_bbnode *b)
static void mpf_remove_bbnode (mpf_bbnode *b)
static int mpf_round_variables (mpf_mipinfo *minf, int *count, mpf_t *tol)
static int mpf_run_bfs (mpf_mipinfo *minf, itcnt_t *itcnt)
static int mpf_startup_mip (mpf_mipinfo *minf, mpf_lpinfo *lp, mpf_price_info *pinf, mpf_t *lpval, itcnt_t *itcnt)

Variables

static int TRACE = 0


Define Documentation

#define mpf_FIRSTBRANCH   1

Definition at line 76 of file mpf_binary.c.

Referenced by mpf_find_branch().

#define mpf_ILL_BRANCH_PENALTY_VAL ( v0,
v1,
 ) 

Value:

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

Definition at line 68 of file mpf_binary.c.

#define mpf_ILL_BRANCH_PENALTY_WEIGHT   (2)

Definition at line 67 of file mpf_binary.c.

#define mpf_ILL_BRANCH_STRONG_VAL ( v0,
v1   ) 

Value:

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

Definition at line 62 of file mpf_binary.c.

#define mpf_ILL_BRANCH_STRONG_WEIGHT   (10)

Definition at line 61 of file mpf_binary.c.

#define mpf_ILL_INTTOL   mpf_PFEAS_TOLER

Definition at line 56 of file mpf_binary.c.

Referenced by mpf_check_integral(), mpf_child_work(), mpf_find_first_branch(), mpf_find_penalty_branch(), mpf_find_strong_branch(), mpf_fix_variables(), and mpf_plunge_work().

#define mpf_MIDDLEBRANCH   2

Definition at line 77 of file mpf_binary.c.

Referenced by mpf_find_branch().

#define mpf_PENALTYBRANCH   4

Definition at line 79 of file mpf_binary.c.

Referenced by mpf_find_branch(), and mpf_ILLmip_bfs().

#define mpf_STRONG_CANDIDATES   (10)

Definition at line 59 of file mpf_binary.c.

Referenced by mpf_find_strong_branch().

#define mpf_STRONG_PIVOTS   (50)

Definition at line 58 of file mpf_binary.c.

#define mpf_STRONGBRANCH   3

Definition at line 78 of file mpf_binary.c.

Referenced by mpf_find_branch(), and mpf_init_mipinfo().


Function Documentation

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

Definition at line 132 of file mpf_binary.c.

References QS_PRICE_DSTEEP, and QS_PRICE_PSTEEP.

static void mpf_best_bbnode ( mpf_mipinfo minf,
mpf_bbnode **  best 
) [static]

Definition at line 955 of file mpf_binary.c.

References mpf_bbnode::bound, mpf_mipinfo::head_bbnode, mpf_ILL_MAXDOUBLE, mpf_ILLutil_priority_deletemin(), mpf_bbnode::next, and mpf_mipinfo::que.

Referenced by mpf_run_bfs().

Here is the call graph for this function:

static void mpf_check_integral ( mpf_lpinfo lp,
mpf_t *  x,
int *  yesno 
) [static]

Definition at line 1373 of file mpf_binary.c.

References mpf_ILLlpdata::intmarker, mpf_ILL_INTTOL, mpf_ILLlpdata::nstruct, and mpf_lpinfo::O.

Referenced by mpf_child_work().

static int mpf_child_work ( mpf_mipinfo minf,
mpf_bbnode active,
int  bvar,
int  bdir,
mpf_t *  cval,
int *  cp,
itcnt_t itcnt 
) [static]

Definition at line 691 of file mpf_binary.c.

References mpf_mipinfo::bestx, mpf_bbnode::bound, mpf_bbnode::bound_cnt, mpf_bbnode::bound_indx, mpf_bbnode::bounds, mpf_bbnode::cstat, mpf_bbnode::depth, mpf_price_info::dII_price, DUAL_SIMPLEX, mpf_bbnode::id, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_SAFE_MALLOC, mpf_mipinfo::lastpivots, mpf_mipinfo::lp, mpf_bbnode::lu, mpf_check_integral(), mpf_copy_x(), mpf_ILL_INTTOL, mpf_ILL_MAXDOUBLE, mpf_ILLlib_chgbnd(), mpf_ILLlib_getbasis(), mpf_ILLlib_getbnd(), mpf_ILLlib_getrownorms(), mpf_ILLlib_iter(), mpf_ILLlib_objval(), mpf_ILLlib_optimize(), mpf_ILLutil_priority_insert(), mpf_init_bbnode(), mpf_put_bbnode(), mpf_lpinfo::nrows, mpf_ILLlpdata::nstruct, mpf_lpinfo::O, mpf_mipinfo::objectivebound, mpf_mipinfo::pinf, mpf_mipinfo::ptrworld, QS_LP_INFEASIBLE, QS_LP_UNSOLVED, QS_PRICE_DSTEEP, mpf_mipinfo::que, mpf_bbnode::rownorms, mpf_bbnode::rstat, mpf_mipinfo::totalnodes, mpf_mipinfo::totalpivots, mpf_mipinfo::value, and mpf_mipinfo::x.

Here is the call graph for this function:

static void mpf_cleanup_mip ( mpf_mipinfo minf  )  [static]

Definition at line 389 of file mpf_binary.c.

References mpf_mipinfo::lp, mpf_ILL_MAX, mpf_ILL_MIN, mpf_lpinfo::ncols, mpf_lpinfo::O, mpf_ILLlpdata::obj, mpf_ILLlpdata::objsense, and mpf_mipinfo::objsense.

Referenced by mpf_ILLmip_bfs().

static void mpf_copy_x ( int  nstruct,
mpf_t *  from_x,
mpf_t *  to_x 
) [static]

Definition at line 1656 of file mpf_binary.c.

Referenced by mpf_child_work(), mpf_ILLmip_bfs(), and mpf_plunge_work().

static int mpf_find_branch ( mpf_mipinfo minf,
mpf_t *  x,
mpf_t *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 999 of file mpf_binary.c.

References mpf_mipinfo::branching_rule, mpf_mipinfo::downpen, ILL_CLEANUP_IF, ILL_RETURN, mpf_mipinfo::lp, mpf_find_first_branch(), mpf_find_middle_branch(), mpf_find_penalty_branch(), mpf_find_strong_branch(), mpf_FIRSTBRANCH, mpf_MIDDLEBRANCH, mpf_PENALTYBRANCH, mpf_STRONGBRANCH, mpf_mipinfo::pinf, and mpf_mipinfo::uppen.

Here is the call graph for this function:

static void mpf_find_first_branch ( mpf_lpinfo lp,
mpf_t *  x,
int *  bvar 
) [static]

Definition at line 1037 of file mpf_binary.c.

References mpf_ILLlpdata::intmarker, mpf_ILL_INTTOL, mpf_ILLlpdata::nstruct, mpf_lpinfo::O, and t.

Referenced by mpf_find_branch().

static void mpf_find_middle_branch ( mpf_lpinfo lp,
mpf_t *  x,
int *  bvar 
) [static]

Definition at line 1068 of file mpf_binary.c.

References mpf_ILLlpdata::intmarker, mpf_ILLlpdata::nstruct, mpf_lpinfo::O, and t.

Referenced by mpf_find_branch(), and mpf_plunge_work().

static int mpf_find_penalty_branch ( mpf_lpinfo lp,
mpf_price_info pinf,
mpf_t *  x,
mpf_t *  downpen,
mpf_t *  uppen,
mpf_t *  lpval,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1117 of file mpf_binary.c.

References ILL_SAFE_MALLOC, mpf_ILLlpdata::intmarker, mpf_ILL_INTTOL, mpf_ILL_MINDOUBLE, mpf_ILLlpdata::nstruct, mpf_lpinfo::O, and t.

Referenced by mpf_find_branch().

static int mpf_find_strong_branch ( mpf_lpinfo lp,
mpf_price_info pinf,
mpf_t *  x,
int *  bvar,
itcnt_t itcnt 
) [static]

Definition at line 1238 of file mpf_binary.c.

References ILL_SAFE_MALLOC, ILLutil_sprand(), mpf_ILLlpdata::intmarker, mpf_ILL_INTTOL, mpf_ILL_MINDOUBLE, mpf_STRONG_CANDIDATES, mpf_ILLlpdata::nstruct, and mpf_lpinfo::O.

Referenced by mpf_find_branch().

Here is the call graph for this function:

static int mpf_fix_variables ( mpf_lpinfo lp,
mpf_t *  bestval,
mpf_bbnode b,
mpf_t *  wupper,
mpf_t *  wlower,
int *  hit 
) [static]

Definition at line 846 of file mpf_binary.c.

References mpf_bbnode::bound_cnt, mpf_bbnode::bound_indx, mpf_bbnode::bounds, ILL_CLEANUP_IF, ILL_SAFE_MALLOC, mpf_ILLlpdata::intmarker, mpf_bbnode::lu, mpf_ILL_INTTOL, mpf_ILL_MAXDOUBLE, mpf_ILLlib_chgbnd(), mpf_ILLlib_objval(), mpf_ILLlib_solution(), mpf_ILLlpdata::nstruct, and mpf_lpinfo::O.

Here is the call graph for this function:

static void mpf_free_bbnode ( mpf_bbnode b  )  [static]

Definition at line 1748 of file mpf_binary.c.

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

Referenced by mpf_run_bfs().

static void mpf_free_mipinfo ( mpf_mipinfo minf  )  [static]

Definition at line 1700 of file mpf_binary.c.

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

Referenced by mpf_ILLmip_bfs().

Here is the call graph for this function:

int mpf_ILLmip_bfs ( mpf_lpinfo lp,
mpf_t *  val,
mpf_t *  x,
itcnt_t itcnt 
)

Definition at line 176 of file mpf_binary.c.

References mpf_mipinfo::activenodes, mpf_mipinfo::bestx, mpf_bbnode::bound, mpf_mipinfo::branching_rule, mpf_bbnode::cstat, mpf_bbnode::depth, mpf_price_info::dII_price, mpf_mipinfo::head_bbnode, mpf_price_info::htrigger, mpf_bbnode::id, ILL_CLEANUP_IF, ILL_IFFREE, ILL_RETURN, ILL_SAFE_MALLOC, ILLutil_zeit(), mpf_cleanup_mip(), mpf_copy_x(), mpf_free_mipinfo(), mpf_ILL_MAX, mpf_ILL_MAXDOUBLE, mpf_ILLlib_getbasis(), mpf_ILLlib_getrownorms(), mpf_ILLprice_free_pricing_info(), mpf_ILLprice_init_pricing_info(), mpf_ILLutil_priority_free(), mpf_ILLutil_priority_init(), mpf_ILLutil_priority_insert(), mpf_init_bbnode(), mpf_init_mipinfo(), mpf_PENALTYBRANCH, mpf_run_bfs(), mpf_startup_mip(), mpf_bbnode::next, mpf_lpinfo::nrows, mpf_ILLlpdata::nstruct, mpf_lpinfo::O, mpf_mipinfo::objsense, mpf_mipinfo::ptrworld, QS_PRICE_DSTEEP, mpf_mipinfo::que, mpf_bbnode::rownorms, mpf_bbnode::rstat, mpf_mipinfo::totalnodes, mpf_mipinfo::totalpivots, and mpf_mipinfo::value.

Referenced by mpf_solver_main().

Here is the call graph for this function:

static void mpf_init_bbnode ( mpf_bbnode b  )  [static]

Definition at line 1726 of file mpf_binary.c.

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

Referenced by mpf_child_work(), and mpf_ILLmip_bfs().

static void mpf_init_mipinfo ( mpf_mipinfo minf  )  [static]

Definition at line 1669 of file mpf_binary.c.

References mpf_mipinfo::activenodes, mpf_mipinfo::bestx, mpf_mipinfo::branching_rule, mpf_mipinfo::depth, mpf_mipinfo::downpen, mpf_mipinfo::head_bbnode, ILLptrworld_init(), mpf_mipinfo::lastpivots, mpf_mipinfo::lower, mpf_mipinfo::lp, mpf_ILL_MAXDOUBLE, mpf_STRONGBRANCH, mpf_bbnode::next, mpf_mipinfo::objectivebound, mpf_mipinfo::pinf, mpf_bbnode::prev, mpf_mipinfo::ptrworld, mpf_mipinfo::que, mpf_mipinfo::totalnodes, mpf_mipinfo::totalpivots, mpf_mipinfo::uppen, mpf_mipinfo::upper, mpf_mipinfo::value, mpf_mipinfo::watch, and mpf_mipinfo::x.

Referenced by mpf_ILLmip_bfs().

Here is the call graph for this function:

static int mpf_plunge ( mpf_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 1407 of file mpf_binary.c.

References DUAL_SIMPLEX, ILL_CLEANUP_IF, ILL_RETURN, mpf_mipinfo::lower, mpf_mipinfo::lp, mpf_ILLlib_chgbnd(), mpf_ILLlib_optimize(), mpf_plunge_work(), mpf_ILLlpdata::nstruct, mpf_lpinfo::O, mpf_mipinfo::pinf, mpf_mipinfo::upper, and mpf_mipinfo::watch.

Here is the call graph for this function:

static int mpf_plunge_work ( mpf_mipinfo minf,
int  depth,
itcnt_t itcnt 
) [static]

Definition at line 1458 of file mpf_binary.c.

References mpf_mipinfo::bestx, DUAL_SIMPLEX, ILL_CLEANUP, ILL_CLEANUP_IF, ILL_RETURN, mpf_mipinfo::lower, mpf_mipinfo::lp, mpf_copy_x(), mpf_find_middle_branch(), mpf_ILL_INTTOL, mpf_ILL_MAXDOUBLE, mpf_ILLlib_chgbnd(), mpf_ILLlib_get_x(), mpf_ILLlib_objval(), mpf_ILLlib_optimize(), mpf_round_variables(), mpf_ILLlpdata::nstruct, mpf_lpinfo::O, mpf_mipinfo::objectivebound, mpf_mipinfo::pinf, QS_LP_INFEASIBLE, QS_LP_OPTIMAL, QS_LP_UNSOLVED, mpf_mipinfo::upper, mpf_mipinfo::value, and mpf_mipinfo::x.

Referenced by mpf_plunge().

Here is the call graph for this function:

static int mpf_process_bfs_bbnode ( mpf_mipinfo minf,
mpf_bbnode active,
itcnt_t itcnt 
) [static]

Definition at line 432 of file mpf_binary.c.

References mpf_mipinfo::activenodes, mpf_bbnode::bound, mpf_bbnode::bound_cnt, mpf_bbnode::bound_indx, mpf_bbnode::bounds, mpf_bbnode::id, ILL_CLEANUP_IF, mpf_mipinfo::lastpivots, mpf_mipinfo::lp, mpf_bbnode::lu, mpf_ILL_MAXDOUBLE, mpf_ILLlib_chgbnds(), mpf_ILLlp_basis_init(), mpf_ILLlpdata::nstruct, mpf_lpinfo::O, mpf_mipinfo::objectivebound, mpf_mipinfo::orig_lower, mpf_mipinfo::orig_upper, t, mpf_mipinfo::totalpivots, mpf_mipinfo::value, and mpf_mipinfo::watch.

Referenced by mpf_run_bfs().

Here is the call graph for this function:

static void mpf_put_bbnode ( mpf_mipinfo minf,
mpf_bbnode b 
) [static]

Definition at line 980 of file mpf_binary.c.

References mpf_mipinfo::head_bbnode, mpf_bbnode::next, and mpf_bbnode::prev.

Referenced by mpf_child_work().

static void mpf_remove_bbnode ( mpf_bbnode b  )  [static]

Definition at line 991 of file mpf_binary.c.

References mpf_bbnode::next, and mpf_bbnode::prev.

Referenced by mpf_run_bfs().

static int mpf_round_variables ( mpf_mipinfo minf,
int *  count,
mpf_t *  tol 
) [static]

Definition at line 1614 of file mpf_binary.c.

References ILL_CLEANUP_IF, mpf_ILLlpdata::intmarker, mpf_mipinfo::lower, mpf_mipinfo::lp, mpf_ILLlib_chgbnd(), mpf_ILLlpdata::nstruct, mpf_lpinfo::O, mpf_mipinfo::upper, and mpf_mipinfo::x.

Referenced by mpf_plunge_work().

Here is the call graph for this function:

static int mpf_run_bfs ( mpf_mipinfo minf,
itcnt_t itcnt 
) [static]

Definition at line 409 of file mpf_binary.c.

References mpf_mipinfo::activenodes, mpf_mipinfo::head_bbnode, ILL_CLEANUP_IF, ILL_RETURN, mpf_best_bbnode(), mpf_free_bbnode(), mpf_process_bfs_bbnode(), mpf_remove_bbnode(), mpf_bbnode::next, and mpf_mipinfo::ptrworld.

Referenced by mpf_ILLmip_bfs().

Here is the call graph for this function:

static int mpf_startup_mip ( mpf_mipinfo minf,
mpf_lpinfo lp,
mpf_price_info pinf,
mpf_t *  lpval,
itcnt_t itcnt 
) [static]

Definition at line 274 of file mpf_binary.c.

References DUAL_SIMPLEX, ILL_CLEANUP_IF, mpf_ILLlpdata::intmarker, mpf_ILLlpdata::lower, mpf_ILL_MAXDOUBLE, mpf_ILL_MINDOUBLE, mpf_ILLlib_iter(), mpf_ILLlib_objval(), mpf_ILLlib_optimize(), mpf_ILLlpdata::nstruct, mpf_lpinfo::O, mpf_ILLlpdata::structmap, mpf_mipinfo::totalpivots, and mpf_ILLlpdata::upper.

Referenced by mpf_ILLmip_bfs().

Here is the call graph for this function:


Variable Documentation

int TRACE = 0 [static]

Definition at line 24 of file mpf_binary.c.


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