[CHiPPS] Differencing scheme with ALPS

[Yan Xu]

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