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));
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));
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_alpha_factor & operator=(const VOL_alpha_factor &)
double minimum_rel_ascent
terminate if the relative increase in lcost through ascent_check_invl steps is less than this ...
double lambdainit
initial value of lambda
static T VolMax(register const T x, register const T y)
double lambda() const
returns the value of lambda
The user hooks should be overridden by the user to provide the problem specific routines for the volu...
int solve(VOL_user_hooks &hooks, const bool use_preset_dual=false)
Solve the problem using the hooks.
int iter() const
returns the iteration number
VOL_dvector psol
final primal solution (OUTPUT)
VOL_primal & operator=(const VOL_primal &p)
VOL_primal(const int psize, const int dsize)
VOL_dvector()
Default constructor creates a vector of size 0.
VOL_dvector dsol
final dual solution (INPUT/OUTPUT)
void swap(VOL_dvector &w)
swaps the vector with w.
VOL_dvector dual_ub
upper bounds for the duals (if 0 length, then filled with +inf) (INPUT)
void cc(const double alpha, const VOL_primal &p)
This class holds every data for the Volume Algorithm and its solve method must be invoked to solve th...
double granularity
terminate if best_ub - lcost < granularity
int & operator[](const int i)
Return a reference to the i-th entry.
virtual ~VOL_user_hooks()
int ascent_check_invl
through how many iterations does the relative ascent have to reach a minimum
double ubinit
initial upper bound of the value of an integer solution
VOL_ivector()
Default constructor creates a vector of size 0.
void read_params(const char *filename)
Read in the parameters from the file filename.
~VOL_ivector()
The destructor deletes the data array.
VOL_indc & operator=(const VOL_indc &)
double power_heur(const VOL_primal &primal, const VOL_primal &pstar, const VOL_dual &dual) const
Here we decide the value of alpha1 to be used in the convex combination.
VOL_dvector & operator=(const VOL_dvector &w)
Copy w into the vector.
double alphafactor
when little progress is being done, we multiply alpha by alphafactor
#define VOL_TEST_INDEX(i, size)
enum VOL_swing::condition lastswing
int maxsgriters
maximum number of iterations
double & operator[](const int i)
Return a reference to the i-th entry.
double ascent(const VOL_dvector &v, const VOL_dvector &last_u) const
void clear()
Delete the content of the vector and replace it with a vector of length 0.
void allocate(const int s)
delete the current vector and allocate space for a vector of size s.
double factor(const VOL_parms &parm, const double lcost, const double alpha)
double value
final lagrangian value (OUTPUT)
double alphainit
initial value of alpha
void find_max_viol(const VOL_dvector &dual_lb, const VOL_dvector &dual_ub)
VOL_problem()
Default constructor.
double alpha_
value of alpha
VOL_ivector(const VOL_ivector &x)
Copy constructor makes a replica of x.
int dsize
length of dual solution (INPUT)
double operator[](const int i) const
Return the i-th entry.
void allocate(const int s)
delete the current vector and allocate space for a vector of size s.
int sz
The size of the vector.
int printflag
controls the level of printing.
int iter_
iteration number
double lambda_
value of lambda
VOL_swing & operator=(const VOL_swing &)
VOL_problem & operator=(const VOL_problem &)
VOL_ivector & operator=(const VOL_ivector &v)
Copy w into the vector.
double gap_abs_precision
accept if abs gap is less than this
VOL_primal(const VOL_primal &primal)
int alphaint
number of iterations before we check if alpha should be decreased
int size() const
Return the size of the vector.
double * v
The array holding the vector.
VOL_dvector(const VOL_dvector &x)
Copy constructor makes a replica of x.
int yellowtestinvl
how many consecutive yellow iterations are allowed before changing lambda
VOL_vh & operator=(const VOL_vh &)
static T VolAbs(register const T x)
VOL_indc(const VOL_indc &)
This class contains the parameters controlling the Volume Algorithm.
VOL_dvector dual_lb
lower bounds for the duals (if 0 length, then filled with -inf) (INPUT)
void clear()
Delete the content of the vector and replace it with a vector of length 0.
int heurinvl
controls how often we run the primal heuristic
VOL_dual(const VOL_dual &dual)
int greentestinvl
how many consecutive green iterations are allowed before changing lambda
int initialize(const bool use_preset_dual)
initializes duals, bounds for the duals, alpha, lambda
double gap_rel_precision
accept if rel gap is less than this
#define VOL_TEST_SIZE(size)
int psize
length of primal solution (INPUT)
int * v
The array holding the vector.
void swap(VOL_ivector &w)
swaps the vector with w.
int printinvl
controls how often do we print
~VOL_dvector()
The destructor deletes the data array.
char * temp_dualfile
name of file for saving dual solution
~VOL_problem()
Destruct the object.
double alpha() const
returns the value of alpha
double alphamin
minimum value for alpha
void compute_xrc(const VOL_dvector &pstarx, const VOL_dvector &primalx, const VOL_dvector &rc)
void cc(const double gamma, const VOL_dvector &w)
Convex combination.
virtual int compute_rc(const VOL_dvector &u, VOL_dvector &rc)=0
compute reduced costs
VOL_ivector(const int s)
Construct a vector of size s.
int ascent_first_check
when to check for sufficient relative ascent the first time
VOL_parms parm
The parameters controlling the Volume Algorithm (INPUT)
int redtestinvl
how many consecutive red iterations are allowed before changing lambda
void step(const double target, const double lambda, const VOL_dvector &dual_lb, const VOL_dvector &dual_ub, const VOL_dvector &v)
int size() const
Return the size of the vector.
int sz
The size of the vector.
double lfactor(const VOL_parms &parm, const double lambda, const int iter)
VOL_dvector(const int s)
Construct a vector of size s.
virtual int solve_subproblem(const VOL_dvector &dual, const VOL_dvector &rc, double &lcost, VOL_dvector &x, VOL_dvector &v, double &pcost)=0
Solve the subproblem for the subgradient step.
VOL_dvector viol
violations (b-Ax) for the relaxed constraints
VOL_dual(const int dsize)
int operator[](const int i) const
Return the i-th entry.
virtual int heuristics(const VOL_problem &p, const VOL_dvector &x, double &heur_val)=0
Starting from the primal vector x, run a heuristic to produce an integer solution.
double primal_abs_precision
accept if max abs viol is less than this
void cond(const VOL_dual &dual, const double lcost, const double ascent, const int iter)
void print_info(const int iter, const VOL_primal &primal, const VOL_primal &pstar, const VOL_dual &dual)
print volume info every parm.printinvl iterations
VOL_dual & operator=(const VOL_dual &p)
double readjust_target(const double oldtarget, const double lcost) const
Checks if lcost is close to the target, if so it increases the target.