[CHiPPS] Differencing scheme with ALPS

[Khoa Vo]

Hi Yan,

Sounds good! As time is quite critical now (I need to fix the bug, run
the test extensively and submit the results next week), can you tell me
more details how to implement so I don't have to dig into the code?
1. In particular, in the AlpsTreeNode::process() or ::branch(), how can
I get its parent node? 
2. If the parent node is located in another process (or processor after
load balancing), does ALPS layer support getting its information
transparently? That means I just call something like this->parent() and
get its parent?
3. It would be good if you can tell me some classes/functions where I
can take as samples.

Thanks,
Khoa

-----Original Message-----
From: Yan Xu [mailto:Yan.Xu at sas.com] 
Sent: Thursday, February 14, 2008 7:26 PM
To: Khoa Vo
Cc: cops at list.coin-or.org
Subject: RE: Differencing scheme with ALPS

Khoa,

The differencing is introduced at BiCePS level. However, it looks to me
that you can design your own difference scheme. Basically, at a child,
you want to store what are different with its parent and recover to a
full node description when process it next time. For instances, it is
possible that only a few of the "PNode** maPNode" of a child are
different with its parent, then you can add members like

class PartialLabeling
{
        // number of different
          int numDiff;
        // which are different
        int diffIndices;
        // Different nodes
        PNode** diffNodes;
}


At root, you can store a full description (numDiff=-1), then at children
you store difference and recover by tracing back to root or a node with
full description.


Yan




-----Original Message-----
From: Khoa Vo [mailto:khoa.vo at informatik.uni-heidelberg.de]
Sent: Wednesday, February 13, 2008 5:46 PM
To: Yan Xu
Cc: cops at list.coin-or.org
Subject: Differencing scheme with ALPS

Hi Yan,

I didn't succeed setting ALPS parameters to reduce the memory.
I think about the differencing scheme you mentioned with BICEPS and
BLIS. Is it supported in ALPS? The problem is summarized below.

1. I have a struct PNode storing status of graph nodes (not search tree
node).
struct PNode{
        int firstPos;
        int lastPos;
        int rightDistance;   // distance from the node set fixed on the
right
        int leftDistance;    // distance from the node set fixed on the
left
        char updated;
      int bestPos;         // to save an heuristic solution when found
};

2. For each search node born along the search tree, a class
PartialLabeling is created, member variable is init with an array of
node status, e.g. maPNode = new PNode[N];
class PartialLabeling
{
        //labeling
        PNode** maPNode;
}
Note that PNode status can be change at any i with 1<=i<=N, so at the
moment I have to pass all the current node status to the child node. The
child in turn has to hold all these statuses as well, because it needs
status of all graph nodes to process, but this is very expensive. So you
understand why memory is allocated so quickly.
For example, if N=100, then each node takes 100 x 11byte = 1100bytes
already, where 11byte is size of PNode.

Any hint or suggestion will be appreciated.
Thanks,
Khoa


-----Original Message-----
From: Yan Xu [mailto:Yan.Xu at sas.com]
Sent: Monday, February 11, 2008 7:36 PM
To: Khoa Vo
Cc: cops at list.coin-or.org
Subject: RE: Setting physical memory limit

Khoa,

first make sure that Alps_hubWorkClusterSizeLimit is not specified
(which means hub never works like a worker), then try to reduce
Alps_hubInitNodeNum

or

increase Alps_hubNum


I am curiously why hub generate a lots of nodes.

Yan