7#ifndef __OSITESTSOLVER_HPP__
8#define __OSITESTSOLVER_HPP__
16#include "CoinFinite.hpp"
23template <
class T>
static inline T
25 return ((x) > (y)) ? (x) : (y);
28template <
class T>
static inline T
30 return ((x) > 0) ? (x) : -(x);
35#if defined(VOL_DEBUG) && (VOL_DEBUG != 0)
36#define VOL_TEST_INDEX(i, size) \
38 if ((i) < 0 || (i) >= (size)) { \
39 printf("bad VOL_?vector index\n"); \
43#define VOL_TEST_SIZE(size) \
46 printf("bad VOL_?vector size\n"); \
51#define VOL_TEST_INDEX(i, size)
52#define VOL_TEST_SIZE(size)
161 v =
new double[
sz = s];
170 std::copy(x.
v, x.
v +
sz,
v);
202 printf(
"bad VOL_dvector sizes\n");
205 double * p_v =
v - 1;
206 const double * p_w = w.
v - 1;
207 const double *
const p_e =
v +
sz;
208 const double one_gamma = 1.0 - gamma;
209 while ( ++p_v != p_e ){
210 *p_v = one_gamma * (*p_v) + gamma * (*++p_w);
219 v =
new double[
sz = s];
263 std::copy(x.
v, x.
v +
sz,
v);
379 void step(
const double target,
const double lambda,
409 const double lcost,
const double ascent,
const int iter) {
412 if (ascent > 0.0 && lcost > dual.
lcost + eps) {
418 if (ascent <= 0 && lcost > dual.
lcost) {
434 double lambdafactor = 1.0;
442 printf(
" G: Consecutive Gs = %3d\n\n", cons);
447 printf(
"\n ---- increasing lamda to %g ----\n\n",
448 lambda * lambdafactor);
455 printf(
" Y: Consecutive Ys = %3d\n\n", cons);
460 printf(
"\n **** increasing lamda to %g *****\n\n",
461 lambda * lambdafactor);
468 printf(
" R: Consecutive Rs = %3d\n\n", cons);
473 printf(
"\n **** decreasing lamda to %g *****\n\n",
474 lambda * lambdafactor);
483 printf(
"**** G= %i, Y= %i, R= %i ****\n",
ngs,
nys,
nrs);
502 const double alpha) {
505 const double ll =
VolAbs(lcost);
static T VolAbs(const T x)
#define VOL_TEST_INDEX(i, size)
static T VolMax(const T x, const T y)
#define VOL_TEST_SIZE(size)
double factor(const VOL_parms &parm, const double lcost, const double alpha)
VOL_alpha_factor(const VOL_alpha_factor &)
VOL_alpha_factor & operator=(const VOL_alpha_factor &)
void compute_xrc(const VOL_dvector &pstarx, const VOL_dvector &primalx, const VOL_dvector &rc)
void step(const double target, const double lambda, const VOL_dvector &dual_lb, const VOL_dvector &dual_ub, const VOL_dvector &v)
VOL_dual(const VOL_dual &dual)
double ascent(const VOL_dvector &v, const VOL_dvector &last_u) const
VOL_dual & operator=(const VOL_dual &p)
VOL_dual(const int dsize)
void cc(const double gamma, const VOL_dvector &w)
Convex combination.
void allocate(const int s)
delete the current vector and allocate space for a vector of size s.
double * v
The array holding the vector.
double & operator[](const int i)
Return a reference to the i-th entry.
VOL_dvector(const int s)
Construct a vector of size s.
double operator[](const int i) const
Return the i-th entry.
void clear()
Delete the content of the vector and replace it with a vector of length 0.
~VOL_dvector()
The destructor deletes the data array.
VOL_dvector(const VOL_dvector &x)
Copy constructor makes a replica of x.
VOL_dvector & operator=(const VOL_dvector &w)
Copy w into the vector.
VOL_dvector()
Default constructor creates a vector of size 0.
VOL_dvector & operator=(const double w)
Replace every entry in the vector with w.
void swap(VOL_dvector &w)
swaps the vector with w.
int sz
The size of the vector.
int size() const
Return the size of the vector.
VOL_indc(const VOL_indc &)
VOL_indc(const VOL_dvector &dual_lb, const VOL_dvector &dual_ub, const VOL_primal &primal, const VOL_primal &pstar, const VOL_dual &dual)
VOL_indc & operator=(const VOL_indc &)
VOL_ivector(const VOL_ivector &x)
Copy constructor makes a replica of x.
void swap(VOL_ivector &w)
swaps the vector with w.
~VOL_ivector()
The destructor deletes the data array.
VOL_ivector()
Default constructor creates a vector of size 0.
VOL_ivector & operator=(const VOL_ivector &v)
Copy w into the vector.
void clear()
Delete the content of the vector and replace it with a vector of length 0.
VOL_ivector & operator=(const int w)
Replace every entry in the vector with w.
int operator[](const int i) const
Return the i-th entry.
int * v
The array holding the vector.
VOL_ivector(const int s)
Construct a vector of size s.
int size() const
Return the size of the vector.
int sz
The size of the vector.
int & operator[](const int i)
Return a reference to the i-th entry.
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)
void find_max_viol(const VOL_dvector &dual_lb, const VOL_dvector &dual_ub)
VOL_primal & operator=(const VOL_primal &p)
VOL_primal(const VOL_primal &primal)
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 alpha_
value of alpha
double value
final lagrangian value (OUTPUT)
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_dvector psol
final primal solution (OUTPUT)
void read_params(const char *filename)
Read in the parameters from the file filename.
int dsize
length of dual solution (INPUT)
VOL_dvector dual_lb
lower bounds for the duals (if 0 length, then filled with -inf) (INPUT)
double lambda() const
returns the value of lambda
VOL_parms parm
The parameters controlling the Volume Algorithm (INPUT)
int iter() const
returns the iteration number
double alpha() const
returns the value of alpha
VOL_problem & operator=(const VOL_problem &)
double readjust_target(const double oldtarget, const double lcost) const
Checks if lcost is close to the target, if so it increases the target.
int initialize(const bool use_preset_dual)
initializes duals, bounds for the duals, alpha, lambda
VOL_problem(const VOL_problem &)
VOL_dvector viol
violations (b-Ax) for the relaxed constraints
VOL_problem(const char *filename)
Create a a VOL_problem object and read in the parameters from filename.
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_problem()
Default constructor.
VOL_dvector dual_ub
upper bounds for the duals (if 0 length, then filled with +inf) (INPUT)
int psize
length of primal solution (INPUT)
VOL_dvector dsol
final dual solution (INPUT/OUTPUT)
int solve(VOL_user_hooks &hooks, const bool use_preset_dual=false)
Solve the problem using the hooks.
double lambda_
value of lambda
int iter_
iteration number
~VOL_problem()
Destruct the object.
double lfactor(const VOL_parms &parm, const double lambda, const int iter)
enum VOL_swing::condition lastswing
VOL_swing & operator=(const VOL_swing &)
VOL_swing(const VOL_swing &)
void cond(const VOL_dual &dual, const double lcost, const double ascent, const int iter)
The user hooks should be overridden by the user to provide the problem specific routines for the volu...
virtual int compute_rc(const VOL_dvector &u, VOL_dvector &rc)=0
compute reduced costs
virtual ~VOL_user_hooks()
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.
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
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_vh & operator=(const VOL_vh &)
This class contains the parameters controlling the Volume Algorithm.
int printflag
controls the level of printing.
double lambdainit
initial value of lambda
double gap_abs_precision
accept if abs gap is less than this
char * temp_dualfile
name of file for saving dual solution
double alphamin
minimum value for alpha
int greentestinvl
how many consecutive green iterations are allowed before changing lambda
int maxsgriters
maximum number of iterations
double minimum_rel_ascent
terminate if the relative increase in lcost through ascent_check_invl steps is less than this
int heurinvl
controls how often we run the primal heuristic
double granularity
terminate if best_ub - lcost < granularity
int alphaint
number of iterations before we check if alpha should be decreased
int redtestinvl
how many consecutive red iterations are allowed before changing lambda
int printinvl
controls how often do we print
double alphafactor
when little progress is being done, we multiply alpha by alphafactor
double gap_rel_precision
accept if rel gap is less than this
int ascent_first_check
when to check for sufficient relative ascent the first time
double alphainit
initial value of alpha
int ascent_check_invl
through how many iterations does the relative ascent have to reach a minimum
double primal_abs_precision
accept if max abs viol is less than this
int yellowtestinvl
how many consecutive yellow iterations are allowed before changing lambda
double ubinit
initial upper bound of the value of an integer solution