16 template <
class T>
static inline T
17 VolMax(
register const T x,
register const T y) {
18 return ((x) > (y)) ? (x) : (y);
21 template <
class T>
static inline T
23 return ((x) > 0) ? (x) : -(x);
28 #if defined(VOL_DEBUG) && (VOL_DEBUG != 0) 29 #define VOL_TEST_INDEX(i, size) \ 31 if ((i) < 0 || (i) >= (size)) { \ 32 printf("bad VOL_?vector index\n"); \ 36 #define VOL_TEST_SIZE(size) \ 39 printf("bad VOL_?vector size\n"); \ 44 #define VOL_TEST_INDEX(i, size) 45 #define VOL_TEST_SIZE(size) 154 v =
new double[sz = s];
163 std::copy(x.
v, x.
v + sz, v);
170 inline int size()
const {
return sz;}
195 printf(
"bad VOL_dvector sizes\n");
198 double * p_v = v - 1;
199 const double * p_w = w.
v - 1;
200 const double *
const p_e = v + sz;
201 const double one_gamma = 1.0 - gamma;
202 while ( ++p_v != p_e ){
203 *p_v = one_gamma * (*p_v) + gamma * (*++p_w);
212 v =
new double[sz = s];
256 std::copy(x.
v, x.
v + sz, v);
265 inline int size()
const {
return sz; }
319 VOL_primal(
const int psize,
const int dsize) : x(psize), v(dsize) {}
321 value(primal.value), viol(primal.viol), x(primal.x), v(primal.v) {}
338 value = alpha * p.
value + (1.0 - alpha) * value;
361 lcost(dual.lcost), xrc(dual.xrc), u(dual.u) {}
372 void step(
const double target,
const double lambda,
396 lastgreeniter = lastyellowiter = lastrediter = 0;
402 const double lcost,
const double ascent,
const int iter) {
405 if (ascent > 0.0 && lcost > dual.
lcost + eps) {
407 lastgreeniter = iter;
411 if (ascent <= 0 && lcost > dual.
lcost) {
413 lastyellowiter = iter;
427 double lambdafactor = 1.0;
433 cons = iter -
VolMax(lastyellowiter, lastrediter);
435 printf(
" G: Consecutive Gs = %3d\n\n", cons);
437 lastgreeniter = lastyellowiter = lastrediter = iter;
440 printf(
"\n ---- increasing lamda to %g ----\n\n",
441 lambda * lambdafactor);
446 cons = iter -
VolMax(lastgreeniter, lastrediter);
448 printf(
" Y: Consecutive Ys = %3d\n\n", cons);
450 lastgreeniter = lastyellowiter = lastrediter = iter;
453 printf(
"\n **** increasing lamda to %g *****\n\n",
454 lambda * lambdafactor);
459 cons = iter -
VolMax(lastgreeniter, lastyellowiter);
461 printf(
" R: Consecutive Rs = %3d\n\n", cons);
463 lastgreeniter = lastyellowiter = lastrediter = iter;
466 printf(
"\n **** decreasing lamda to %g *****\n\n",
467 lambda * lambdafactor);
476 printf(
"**** G= %i, Y= %i, R= %i ****\n", ngs, nys, nrs);
495 const double alpha) {
498 register const double ll =
VolAbs(lcost);
499 const double x = ll > 10 ? (lcost-lastvalue)/ll : (lcost-lastvalue);
520 VOL_vh(
const double alpha,
604 void set_default_parm();
623 int solve(
VOL_user_hooks& hooks,
const bool use_preset_dual =
false);
676 int iter()
const {
return iter_; }
678 double alpha()
const {
return alpha_; }
680 double lambda()
const {
return lambda_; }
687 void read_params(
const char* filename);
690 int initialize(
const bool use_preset_dual);
693 void print_info(
const int iter,
699 double readjust_target(
const double oldtarget,
const double lcost)
const;
void swap(VOL_dvector &w)
swaps the vector with w.
#define VOL_TEST_SIZE(size)
double & operator[](const int i)
Return a reference to the i-th entry.
char * temp_dualfile
name of file for saving dual solution
VOL_dvector viol
violations (b-Ax) for the relaxed constraints
VOL_dvector dual_ub
upper bounds for the duals (if 0 length, then filled with +inf) (INPUT)
int iter_
iteration number
int * v
The array holding the vector.
VOL_ivector(const int s)
Construct a vector of size s.
VOL_dual(const int dsize)
void cond(const VOL_dual &dual, const double lcost, const double ascent, const int iter)
double alpha_
value of alpha
int sz
The size of the vector.
VOL_dvector(const VOL_dvector &x)
Copy constructor makes a replica of x.
double alphafactor
when little progress is being done, we multiply alpha by alphafactor
double * v
The array holding the vector.
double lfactor(const VOL_parms &parm, const double lambda, const int iter)
VOL_dvector psol
final primal solution (OUTPUT)
virtual ~VOL_user_hooks()
int & operator[](const int i)
Return a reference to the i-th entry.
double lambda() const
returns the value of lambda
VOL_dual(const VOL_dual &dual)
double gap_rel_precision
accept if rel gap is less than this
VOL_dual & operator=(const VOL_dual &p)
VOL_dvector dual_lb
lower bounds for the duals (if 0 length, then filled with -inf) (INPUT)
VOL_ivector()
Default constructor creates a vector of size 0.
VOL_ivector(const VOL_ivector &x)
Copy constructor makes a replica of x.
~VOL_dvector()
The destructor deletes the data array.
int ascent_first_check
when to check for sufficient relative ascent the first time
VOL_primal(const VOL_primal &primal)
double value
final lagrangian value (OUTPUT)
double alphainit
initial value of alpha
void clear()
Delete the content of the vector and replace it with a vector of length 0.
double gap_abs_precision
accept if abs gap is less than this
double alpha() const
returns the value of alpha
double primal_abs_precision
accept if max abs viol is less than this
int operator[](const int i) const
Return the i-th entry.
static T VolAbs(register const T x)
double lambdainit
initial value of lambda
void clear()
Delete the content of the vector and replace it with a vector of length 0.
This class holds every data for the Volume Algorithm and its solve method must be invoked to solve th...
int size() const
Return the size of the vector.
double minimum_rel_ascent
terminate if the relative increase in lcost through ascent_check_invl steps is less than this ...
void cc(const double alpha, const VOL_primal &p)
int psize
length of primal solution (INPUT)
int redtestinvl
how many consecutive red iterations are allowed before changing lambda
void allocate(const int s)
delete the current vector and allocate space for a vector of size s.
VOL_primal(const int psize, const int dsize)
int iter() const
returns the iteration number
int yellowtestinvl
how many consecutive yellow iterations are allowed before changing lambda
int dsize
length of dual solution (INPUT)
double lambda_
value of lambda
double ubinit
initial upper bound of the value of an integer solution
This class contains the parameters controlling the Volume Algorithm.
int greentestinvl
how many consecutive green iterations are allowed before changing lambda
VOL_primal & operator=(const VOL_primal &p)
double operator[](const int i) const
Return the i-th entry.
double granularity
terminate if best_ub - lcost < granularity
int ascent_check_invl
through how many iterations does the relative ascent have to reach a minimum
int heurinvl
controls how often we run the primal heuristic
VOL_dvector(const int s)
Construct a vector of size s.
#define VOL_TEST_INDEX(i, size)
int size() const
Return the size of the vector.
VOL_parms parm
The parameters controlling the Volume Algorithm (INPUT)
double factor(const VOL_parms &parm, const double lcost, const double alpha)
~VOL_ivector()
The destructor deletes the data array.
void swap(VOL_ivector &w)
swaps the vector with w.
void cc(const double gamma, const VOL_dvector &w)
Convex combination.
VOL_dvector dsol
final dual solution (INPUT/OUTPUT)
int printinvl
controls how often do we print
The user hooks should be overridden by the user to provide the problem specific routines for the volu...
int sz
The size of the vector.
int alphaint
number of iterations before we check if alpha should be decreased
static T VolMax(register const T x, register const T y)
double alphamin
minimum value for alpha
int printflag
controls the level of printing.
int maxsgriters
maximum number of iterations
void allocate(const int s)
delete the current vector and allocate space for a vector of size s.
VOL_dvector()
Default constructor creates a vector of size 0.