Go to the documentation of this file.
21 template <
class T>
static inline T
22 VolMax(
register const T x,
register const T y) {
23 return ((x) > (y)) ? (x) : (y);
26 template <
class T>
static inline T
28 return ((x) > 0) ? (x) : -(x);
33 #if defined(VOL_DEBUG) && (VOL_DEBUG != 0)
34 #define VOL_TEST_INDEX(i, size) \
36 if ((i) < 0 || (i) >= (size)) { \
37 printf("bad VOL_?vector index\n"); \
41 #define VOL_TEST_SIZE(size) \
44 printf("bad VOL_?vector size\n"); \
49 #define VOL_TEST_INDEX(i, size)
50 #define VOL_TEST_SIZE(size)
159 v =
new double[
sz = s];
168 std::memcpy(
v, x.
v,
sz *
sizeof(
double));
175 inline int size()
const {
return sz;}
191 inline void clear() {
200 printf(
"bad VOL_dvector sizes\n");
203 double * p_v =
v - 1;
204 const double * p_w = w.
v - 1;
205 const double *
const p_e =
v +
sz;
206 const double one_gamma = 1.0 - gamma;
207 while ( ++p_v != p_e ){
208 *p_v = one_gamma * (*p_v) + gamma * (*++p_w);
217 v =
new double[
sz = s];
261 std::memcpy(
v, x.
v,
sz *
sizeof(
int));
270 inline int size()
const {
return sz; }
285 inline void clear() {
324 VOL_primal(
const int psize,
const int dsize) :
x(psize),
v(dsize) {}
342 inline void cc(
const double alpha,
const VOL_primal& p) {
364 VOL_dual(
const int dsize) :
u(dsize) {
u = 0.0;}
377 void step(
const double target,
const double lambda,
407 const double lcost,
const double ascent,
const int iter) {
410 if (ascent > 0.0 && lcost > dual.
lcost + eps) {
416 if (ascent <= 0 && lcost > dual.
lcost) {
432 double lambdafactor = 1.0;
440 printf(
" G: Consecutive Gs = %3d\n\n", cons);
445 printf(
"\n ---- increasing lamda to %g ----\n\n",
446 lambda * lambdafactor);
453 printf(
" Y: Consecutive Ys = %3d\n\n", cons);
458 printf(
"\n **** increasing lamda to %g *****\n\n",
459 lambda * lambdafactor);
466 printf(
" R: Consecutive Rs = %3d\n\n", cons);
471 printf(
"\n **** decreasing lamda to %g *****\n\n",
472 lambda * lambdafactor);
481 printf(
"**** G= %i, Y= %i, R= %i ****\n",
ngs,
nys,
nrs);
500 const double alpha) {
503 register const double ll =
VolAbs(lcost);
525 VOL_vh(
const double alpha,
704 double readjust_target(
const double oldtarget,
const double lcost)
const;
VOL_primal(const int psize, const int dsize)
double readjust_target(const double oldtarget, const double lcost) const
double alphamin
minimum value for alpha
void cc(const double gamma, const VOL_dvector &w)
VOL_dvector dual_ub
upper bounds for the duals (if 0 length, then filled with +inf) (INPUT)
VOL_swing & operator=(const VOL_swing &)
VOL_parms parm
The parameters controlling the Volume Algorithm (INPUT)
VOL_primal & operator=(const VOL_primal &p)
This class holds every data for the Volume Algorithm and its solve method must be invoked to solve th...
double power_heur(const VOL_primal &primal, const VOL_primal &pstar, const VOL_dual &dual) const
int ascent_check_invl
through how many iterations does the relative ascent have to reach a minimum
double ascent(const VOL_dvector &v, const VOL_dvector &last_u) const
double * v
The array holding the vector.
int sz
The size of the vector.
VOL_dvector viol
violations (b-Ax) for the relaxed constraints
void print_info(const int iter, const VOL_primal &primal, const VOL_primal &pstar, const VOL_dual &dual)
double value
final lagrangian value (OUTPUT)
int sz
The size of the vector.
double factor(const VOL_parms &parm, const double lcost, const double alpha)
double lambdainit
initial value of lambda
virtual int compute_rc(const VOL_dvector &u, VOL_dvector &rc)=0
int iter_
iteration number
int solve(VOL_user_hooks &hooks, const bool use_preset_dual=false)
void cc(const double alpha, const VOL_primal &p)
double granularity
terminate if best_ub - lcost < granularity
double alphafactor
when little progress is being done, we multiply alpha by alphafactor
The user hooks should be overridden by the user to provide the problem specific routines for the volu...
int maxsgriters
maximum number of iterations
VOL_ivector & operator=(const VOL_ivector &v)
VOL_dual & operator=(const VOL_dual &p)
This class contains the parameters controlling the Volume Algorithm.
int & operator[](const int i)
VOL_vh(const double alpha, const VOL_dvector &dual_lb, const VOL_dvector &dual_ub, const VOL_dvector &v, const VOL_dvector &vstar, const VOL_dvector &u)
VOL_dvector psol
final primal solution (OUTPUT)
VOL_alpha_factor & operator=(const VOL_alpha_factor &)
void swap(VOL_ivector &w)
VOL_dvector dsol
final dual solution (INPUT/OUTPUT)
void find_max_viol(const VOL_dvector &dual_lb, const VOL_dvector &dual_ub)
double gap_abs_precision
accept if abs gap is less than this
double lfactor(const VOL_parms &parm, const double lambda, const int iter)
double ubinit
initial upper bound of the value of an integer solution
void allocate(const int s)
VOL_dual(const int dsize)
void cond(const VOL_dual &dual, const double lcost, const double ascent, const int iter)
#define VOL_TEST_SIZE(size)
#define VOL_TEST_INDEX(i, size)
VOL_dvector & operator=(const VOL_dvector &w)
void read_params(const char *filename)
static T VolAbs(register const T x)
virtual int heuristics(const VOL_problem &p, const VOL_dvector &x, double &heur_val)=0
int printflag
controls the level of printing.
int alphaint
number of iterations before we check if alpha should be decreased
int heurinvl
controls how often we run the primal heuristic
double alphainit
initial value of alpha
int * v
The array holding the vector.
double alpha_
value of alpha
void step(const double target, const double lambda, const VOL_dvector &dual_lb, const VOL_dvector &dual_ub, const VOL_dvector &v)
virtual int solve_subproblem(const VOL_dvector &dual, const VOL_dvector &rc, double &lcost, VOL_dvector &x, VOL_dvector &v, double &pcost)=0
virtual ~VOL_user_hooks()
int yellowtestinvl
how many consecutive yellow iterations are allowed before changing lambda
int dsize
length of dual solution (INPUT)
VOL_problem & operator=(const VOL_problem &)
double lambda_
value of lambda
VOL_indc(const VOL_dvector &dual_lb, const VOL_dvector &dual_ub, const VOL_primal &primal, const VOL_primal &pstar, const VOL_dual &dual)
double gap_rel_precision
accept if rel gap is less than this
VOL_vh & operator=(const VOL_vh &)
void compute_xrc(const VOL_dvector &pstarx, const VOL_dvector &primalx, const VOL_dvector &rc)
int greentestinvl
how many consecutive green iterations are allowed before changing lambda
int ascent_first_check
when to check for sufficient relative ascent the first time
char * temp_dualfile
name of file for saving dual solution
VOL_indc & operator=(const VOL_indc &)
double primal_abs_precision
accept if max abs viol is less than this
VOL_dvector dual_lb
lower bounds for the duals (if 0 length, then filled with -inf) (INPUT)
double & operator[](const int i)
void allocate(const int s)
int initialize(const bool use_preset_dual)
enum VOL_swing::condition lastswing
static T VolMax(register const T x, register const T y)
int redtestinvl
how many consecutive red iterations are allowed before changing lambda
int printinvl
controls how often do we print
double minimum_rel_ascent
terminate if the relative increase in lcost through ascent_check_invl steps is less than this
int psize
length of primal solution (INPUT)
void swap(VOL_dvector &w)