aik7 / rma Goto Github PK

Rectangular maximum agreement problem (RMA)

C++ 98.28% Shell 0.56% CMake 1.16%

rma's Introduction

RMA

RMA is a solver to find an axis-parallel box containing the maximum net weight of positivly minus negativly covered observations or vice versa when each observation has a positive or negative weight.

Software Requirement:

You need to install

CMake (version >= 3.0)
C++ compiler (g++)
OpenMPI 2.1.1 (openmpi-bin, libopenmpi-dev)

The following packages are installed by running scripts/build.sh as described below

PEBBL

Note

The build was tested on Ubuntu 18.04 (Bionic) as shown in our TravisCI file

The description and user guide of RMA

How to clone and build PEBBL and RMA

Recursive clone the RMA repository (PEBBL is a submodule in this repository)

git clone --recursive https://github.com/aik7/RMA.git

Build RMA with PEBBL (Note: assuming that all commands are executed in the RMA main directory)

sh scripts/build.sh

If you want to build RMA and PEBBL with the debug mode

sh scripts/build.sh -d true

Example commands to run RMA:

Serial implementation

./build/rma <data_filename>

Parallel implementation

mpirun -np 4 ./build/rma <data_filename>

Example script

sh scripts/driver.sh  # at the RMA root directory

Parameters

parameters	description	data type	range	default value
isPebblRMA	whether or not to solve RMA using PEBBL	bool	true or false	true
isGreedyRMA	whether or not to solve RMA using the greedy method	bool	true or false	true
isInitGuess	whether or not to set the PEBBL's initial solution as the greedy RMA solution	bool	true or false	true
fracCachedCutPts	the threshold of cached cutpoints caching which is the fraction of the total cutpoints	double	[0, infinity)	0
isMinMaxGreedy	whether or not to solve the greedy RMA by min-then-max order; if false, it will solve the greedy RMA by max-then-min order	bool	true or false	true
isPrintBBdetails	whether or not to print out the PEBBL's branch and bound information	bool	true or false	false
nonUniformWt	if you set a non-uniform weight file for a given dataset, the code solves the RMA problem using the weight	string		""
delta	it is a factor of the epsilon integerization method	double		0.005

Class Diagram

A solid arrow indicates an inheritance relationship
A dashed arrow indicates a composition relationship

Source files at src directory

├── argRMA.cpp       : a file contains RMA argument class
├── argRMA.h
├── baseRMA.cpp      : a file contains a base class for a SolveRMA class
├── baseRMA.h
├── dataRMA.cpp      : a file contains RMA data classes
├── dataRMA.h
├── driver.cpp       : a driver file
├── greedyRMA.cpp    : a file contains greedy RMA class
├── greedyRMA.h
├── parRMA.cpp       : a file contains parallel RMA class
├── parRMA.h
├── serRMA.cpp       : a file contains serial RMA class
├── serRMA.h
├── Time.h           : a header file for time
├── solveRMA.cpp     : a file contains SolveRMA class
├── solveRMA.h
├── utility.cpp      : a file contains RMA utility functions
└── utility.h

Reference

@phdthesis{AiThesis,
  author       = {Ai Kagawa},
  title        = {The Rectangular Maximum Agreement Problem: Applications and Parallel Solution},
  school       = {Rutgers University},
  year         = 2018
}

rma's People

Contributors

rma's Issues

Fix the PEBBL's global solution

The PEBBL's global objective value is correct, but the lower and upper bounds are wrong.

MPI_UB is no longer supported in Open MPI 4.0.3

The default Open MPI version in Ubuntu 20.04.1 LTS is 4.0.3, and it does not support MPI_UB.

Check integerization with different datasets

A stack trace disabled

[0] /home/kagawa/Projects/thesis/installpebbl/include/pebbl/utilib/stl_auxiliary.h:320: !is: operator>> - unpack problem.(PN0)
[0] [stack trace disabled: compile with UTILIB_HAVE_EXECINFO_H]

It happens sometimes in parallel RMA.

warning: comparison of unsigned expression >= 0 is always true

/ccs/home/aik07/RMA/src/serRMA.cpp:1368:25: warning: comparison of unsigned expression >= 0 is always true [-Wtautological-compare]
  for (i = numEC - 1; i >= 0; --i) {
                      ~ ^  ~

Replace baseRMA with PEBBL code

message

Fixed how RMA reads the data file

If a data file has blank lines, the RMA code is still counting towards the number of the observations. This has to be fixed.

In iteration 1 for cool.dat (p=2), greedy finds a better solution than RMA

Confusing observation indices

When using dataOrigTrain, dataIntTrain, dataStandTrain, make sure to use indTrain(idx) to get the proper observation index.

In RMA, we remove zero-weight observations from the training set, but we should still integerize and standardize all data.

Use the greedy RMA solution as the initial solution of PEBBL RMA

It used to work, but not working anymore.

Combine the max and min versions in the greedy RMA

Need to copy PEBBL parameters

`
// RMA constructor
RMA::RMA(pebblParams *param) : workingSol(this), numCC_SP(0) { //, numTotalCutPts(0)

this->debug = param->debug;
this->maxCPUMinutes = param->maxCPUMinutes;
`

A problem with parallel RMA

This problem was due to setup() function.

the incumbent does not work if you set --initialGuess=false

$ ./rma --initGuess=false --debug=0 ../data/cleveland.dat 
User-specified solver options: 
initGuess false
debug 0

(mxn): 297	35
m^+ m^-: 137	160
Using default values for all solver options
ERMA Solution: inf	CPU time: 0.018902	Num of Nodes: 1

$ ./rma --initGuess=true --debug=0 ../data/cleveland.dat 
User-specified solver options: 
initGuess true
debug 0

(mxn): 297	35
m^+ m^-: 137	160
Using default values for all solver options
GRMA Solution: -0.329966	CPU Time: 0.004389
ERMA Solution: 0.329966	CPU time: 0.335751	Num of Nodes: 206

error: 'MPI_UB’ was not declared in this scope on Caliburn

module load cmake/3.11.2
module load openmpi/1.10.4
sh scripts/build.sh

/home1/ak907/RMA/src/serRMA.cpp:125:38: error: ‘MPI_UB’ was not declared in this scope

An error occurred in MPI_Testsome

[e3c-167:21948] *** An error occurred in MPI_Testsome
[e3c-167:21948] *** reported by process [140737472954369,1]
[e3c-167:21948] *** on communicator MPI_COMM_WORLD
[e3c-167:21948] *** MPI_ERR_TRUNCATE: message truncated
[e3c-167:21948] *** MPI_ERRORS_ARE_FATAL (processes in this communicator will now abort,
[e3c-167:21948] ***    and potentially your MPI job)

setPebblParameters is really ugly

The setPebblParameters routine is really ugly -- we shouldn't need something like this. Try to rethink how the parameters are structured.

Parallel RMA: sometimes slower than serial RMA

$ ./build/rma  ../../data/paper/skin.data
Using default values for all solver options
(mxn): 245057	3
m^+ m^-: 194198	50859
Using default values for all solver options
GRMA Solution: +0.674843	CPU Time: 0.022393
#5 pool=3  inc=0.6748430 bnd=0.7843400 gap=13.960%

Best Solution:  Value = 0.67484299571120176520

Subproblems
-----------
Created            280  100.0%
Started Bounding   280  100.0%
Bounded            280  100.0%
Started Splitting  185   66.1%
Split              185   66.1%
Dead                95   33.9%

CPU run time          = 19.3 seconds
CPU total time        = 19.3 seconds
Wall clock total time = 19.3 seconds

x2<=170, 
ERMA Solution: 0.674843	CPU time: 19.281	Num of Nodes: 280

$ mpirun -np 2 ./build/rma  ../../data/paper/skin.data
Using default values for all solver options
(mxn): 245057	3
m^+ m^-: 194198	50859
[0] Using default values for all solver options

PEBBL Configuration:
-------------------
1 cluster of size 2
2 processors
1 pure worker  ( 50.0%)
1 worker-hub   ( 50.0%)

Target timeslice: 0.01 seconds.

[0] GRMA Solution: +0.674843	CPU Time: 0.02843
[0] h#3 pool=2  inc=0.674843 bnd=0.7912 gap=14.706%
[0] h#109 pool=28  inc=0.674843 bnd=0.68654 gap=1.704%


Best Solution:  Value = 0.6748429957112017652

x2<=170, 
Subproblems
-----------
Created                    276  100.0%
Started Bounding           276  100.0%
Bounded                    276  100.0%
Started Splitting          190   68.8%
Split                      190   68.8%
Dead                        86   31.2%

Bounded during ramp up       2    0.7%
In pool at end of ramp up    1    0.4%
Tokens at Hub              124   44.9%
Scattered to Hub            44   15.9%
Rebalanced to Hub           80   29.0%
Dispatched from a Hub      124   44.9%
Moved between Workers       52   18.8%

Average search time (CPU)           24.4 seconds.
Maximum search time (CPU)           24.4 seconds.
Average search time (Wall clock)    30.8 seconds.
Maximum search time (Wall clock)    30.8 seconds.

0 quiescence polls, 1 termination check.

                           Average   % of % where       Messages   % of
Thread/Function     Number Seconds  Total  Active   COV Received   Msgs
------------------- ------ ------- ------ ------- ----- -------- ------
Problem Broadcast        2     0.1   0.4%    0.4%  0.24        2   0.5%
Preprocessing            2     0.0   0.0%    0.0%  0.00        0   0.0%
Ramp-up                  2     6.4  26.3%   26.3%  0.00       33   8.9%
Worker                   2    16.4  67.1%   67.1%  0.09        0   0.0%
Hub                      1     0.0   0.0%    0.0%  0.00      186  50.1%
Incumbent Broadcast      2     0.0   0.0%    0.0%  0.00        0   0.0%
Subproblem Receiver      2     0.0   0.0%    0.0%  0.07       49  13.2%
Subproblem Server        2     0.0   0.0%    0.0%  1.00       51  13.7%
Termination Check        1     0.0   0.0%    0.0%  0.00        1   0.3%
Worker Auxiliary         1     0.0   0.0%    0.0%  0.00       44  11.9%
Cut Point Receiver       2     0.0   0.0%    0.0%  0.29        4   1.1%
Scheduler                2     0.5   2.1%    2.1%  0.99        0   0.0%
Solution Output          2     0.0   0.0%    0.0%  0.65        1   0.3%
Other Overhead           2     0.0   0.0%    0.0%  0.37        0   0.0%
Idle                     2     1.0   3.9%    3.9%  1.00        0   0.0%
                                   ------               -------- ------
Total                    2    24.4 100.0%  100.0%  0.00      371 100.0%

Messages per subproblem: 1.34
Hub loading factor: 2%

[0] ERMA Solution: 0.674843	CPU time: 24.2982	Num of Nodes: 276

'std::runtime_error' : Attempt to destruct a solution with refCounter=1 -- use dispose() instead of delete

In pebbl_sol branch, added the following line at /src/solveRMA.cpp

+      delete rma;

I get the following error.

terminate called after throwing an instance of 'std::runtime_error'
  what():  /home/aik/RMA/external/pebbl/src/pebbl/bb/branching.h:661: Attempt to destruct a solution with refCounter=1 -- use dispose() instead of delete(PN0)

If I try,

+      rma->workingSol.dispose();
+
+      delete rma;

I get this error.

free(): invalid pointer
[eckstein-enthoo:07700] *** Process received signal ***
[eckstein-enthoo:07700] Signal: Aborted (6)
[eckstein-enthoo:07700] Signal code:  (-6)

Error: bad_alloc for parallel RMA with printBBdetails=true

$ mpirun -np 2 ./build/rma --branchSelection=1 --perCachedCutPts=1  --printBBdetails=true ../../data/paper/spam.data 
User-specified solver options: 
branchSelection 1
perCachedCutPts 1
printBBdetails true

(mxn): 4601	40
m^+ m^-: 2788	1813
[0] Using default values for all solver options

PEBBL Configuration:
-------------------
1 cluster of size 2
2 processors
1 pure worker  ( 50.0%)
1 worker-hub   ( 50.0%)

Target timeslice: 0.01 seconds.

[0] GRMA Solution: +0.430559	CPU Time: 0.003221


Best Solution:  Value = 0.46142143012388614487

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
[LCC-155978:07566] *** Process received signal ***
[LCC-155978:07566] Signal: Aborted (6)
[LCC-155978:07566] Signal code:  (-6)
[LCC-155978:07566] [ 0] /lib/x86_64-linux-gnu/libpthread.so.0(+0x128a0)[0x7f7a1e75a8a0]
[LCC-155978:07566] [ 1] /lib/x86_64-linux-gnu/libc.so.6(gsignal+0xc7)[0x7f7a1e395f47]
[LCC-155978:07566] [ 2] /lib/x86_64-linux-gnu/libc.so.6(abort+0x141)[0x7f7a1e3978b1]
[LCC-155978:07566] [ 3] /usr/lib/x86_64-linux-gnu/libstdc++.so.6(+0x8c957)[0x7f7a1efa9957]
[LCC-155978:07566] [ 4] /usr/lib/x86_64-linux-gnu/libstdc++.so.6(+0x92ae6)[0x7f7a1efafae6]
[LCC-155978:07566] [ 5] /usr/lib/x86_64-linux-gnu/libstdc++.so.6(+0x92b21)[0x7f7a1efafb21]
[LCC-155978:07566] [ 6] /usr/lib/x86_64-linux-gnu/libstdc++.so.6(+0x92d54)[0x7f7a1efafd54]
[LCC-155978:07566] [ 7] /usr/lib/x86_64-linux-gnu/libstdc++.so.6(+0x932dc)[0x7f7a1efb02dc]
[LCC-155978:07566] [ 8] ./build/rma(_ZNSt6vectorIjSaIjEE17_M_default_appendEm+0xc3)[0x55e631178e03]
[LCC-155978:07566] [ 9] ./build/rma(_ZrsIjERN6utilib12UnPackBufferES2_RSt6vectorIT_SaIS4_EE+0x5bb)[0x55e631188c9b]
[LCC-155978:07566] [10] ./build/rma(_ZTv0_n112_N8pebblRMA11rmaSolution14unpackContentsERN6utilib12UnPackBufferE+0x2e)[0x55e631191b5e]
[LCC-155978:07566] [11] ./build/rma(_ZN5pebbl8solution6unpackERN6utilib12UnPackBufferE+0x98)[0x55e6311a4928]
[LCC-155978:07566] [12] ./build/rma(_ZN5pebbl17parallelBranching14unpackSolutionERN6utilib12UnPackBufferE+0x19b)[0x55e6311ca1db]
[LCC-155978:07566] [13] ./build/rma(_ZN5pebbl17parallelBranching11getSolutionEi+0x2a4)[0x55e631221544]
[LCC-155978:07566] [14] ./build/rma(_ZN5pebbl17parallelBranching13printSolutionEPKcS2_RSo+0x45)[0x55e6312242c5]
[LCC-155978:07566] [15] ./build/rma(_ZN5pebbl17parallelBranching14solutionToFileEv+0x189)[0x55e6312201a9]
[LCC-155978:07566] [16] ./build/rma(_ZN5pebbl17parallelBranching5solveEv+0xcb)[0x55e6311c870b]
[LCC-155978:07566] [17] ./build/rma(_ZN3rma9DriverRMA13solveExactRMAEv+0x11d)[0x55e63117a36d]
[LCC-155978:07566] [18] ./build/rma(_ZN3rma9DriverRMA8solveRMAEv+0x473)[0x55e63117ab73]
[LCC-155978:07566] [19] ./build/rma(main+0x33)[0x55e6311637e3]
[LCC-155978:07566] [20] /lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xe7)[0x7f7a1e378b97]
[LCC-155978:07566] [21] ./build/rma(_start+0x2a)[0x55e63116460a]
[LCC-155978:07566] *** End of error message ***
--------------------------------------------------------------------------
mpirun noticed that process rank 0 with PID 0 on node LCC-155978 exited on signal 6 (Aborted).
--------------------------------------------------------------------------