Branch and bound algorithm implementation

Question

I'd need to implement a branch and bound algorithm to prove the effectiveness of an allocating strategy for storage management in my bachelor thesis. I'm not a programmer, I have some little know-how in C, but I can realize this algorithm can't be written straight away, because it is kind of artificial intelligence and needs to make decisions.

I'd like to know what is the way to approach this problem.

I have working code for iteration 1, so that it calculates everything I need for each node, but I'm storing data in a simple array of structures representing the nodes of level 1. The problem is that now, if x is the number of level nodes, I have to create x-1,x-2,x-3,.... new nodes respectively starting from nodes 1,2,3,...

So I am asking if someone would be so kind to put me in the right way to approach the problem.

here's the code I have so far, working for first iteration, sorry but comments are in italian:

//
//  main.cpp
//  prova1
//
//  Created by Marco Braglia on 13/02/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

// definizione nuova struttura per i nodi dell'albero decisionale
struct nodo{
  int last_prod;
  int last_slot;
  float Z_L;
  float Z_U;
  float g;
  bool fathomed;
 };

// dichiarazione variabili
float distanze[361];
int   slot[112];
int slot_cum[112];
float COIp[112];
int domanda[112];
struct nodo n_0;
struct nodo n_1[112];
struct nodo n_2[111][111];
float Zb;

float LowerBound(struct nodo n);
float UpperBound(struct nodo n);

int main()
{



// lettura dati input
// distanze slot

ifstream dist_file ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/dati/distanze.txt" );


if ( !dist_file.is_open() ) {
    // il file non può essere aperto
}
else {
    // leggi i dati nell'array distanze[]
    for(int i=1; !dist_file.eof(); i++){
        dist_file >> distanze[i];
    }

   // visualizza l'array per controllo
   //for(int i=0; i<360; i++){
     //cout << distanze[i] << "\n ";
    //}
}

//slot necessari per prodotto

ifstream slot_file ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/dati/slot.txt" );

if ( !slot_file.is_open() ) {
    // il file non può essere aperto
}
else {
    // leggi i dati nell'array slot[]
    for(int i=1; !slot_file.eof(); i++){
        slot_file >> slot[i];
    }

    for(int i=0; i<112; i++){
        slot_cum[i]=0;
    }

    for(int i=1; i<112; i++){
        slot_cum[i]=slot_cum[i-1]+slot[i];
    }
    // visualizza l'array per controllo
  //  for(int i=0; i<111; i++){
  //  cout << slot[i] << "\n ";
  // }
 //   cin.get();
}

// COIp

ifstream coi_file ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/dati/COIp.txt" );

if ( !coi_file.is_open() ) {
    // il file non può essere aperto
}
else {
    // leggi i dati nell'array COIp[]
    for(int i=1; !coi_file.eof(); i++){
        coi_file >> COIp[i];
    }

    // visualizza l'array per controllo
    //for(int i=0; i<111; i++){
    //    cout << COIp[i] << "\n ";
  //  }
}

ifstream d_file ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/dati/domanda.txt" );

if ( !d_file.is_open() ) {
    // il file non può essere aperto
}
else {
    // leggi i dati nell'array COIp[]
    for(int i=1; !d_file.eof(); i++){
        d_file >> domanda[i];
    }
}


//inizializzazione nodi
n_0.last_prod=0;
n_0.last_slot=0;
n_0.Z_L = 0;
n_0.Z_U = 0;
n_0.g = 0;
n_0.fathomed = false;
    for (int j=0; j<112; j++){

            n_1[j].last_prod = 0;
            n_1[j].last_slot = 0;
            n_1[j].Z_L = 0;
            n_1[j].Z_U = 0;
            n_1[j].g = 0;
            n_1[j].fathomed = false;
        }


//inizializzazione soluzione obiettivo ad infinito
Zb=999999999999;

//calcolo bounds per nodi al livello 1
for(int i=1;i<112;i++){
        n_1[i].last_prod=i;
        n_1[i].last_slot=slot_cum[i];
        n_1[i].Z_L=LowerBound(n_1[i]);
        n_1[i].Z_U=UpperBound(n_1[i]);

    //calcolo g_c
    float dm;
    int D;
    for(int i=1;i<112;i++){
        dm=0;
        for(int j=1;j<=slot_cum[i];j++){
            dm=dm+distanze[j];
        }
        dm=dm/slot_cum[i];
        D=0;
        for(int k=1;k<=n_1[i].last_prod;k++){
            D=D+domanda[k];
        }            
        n_1[i].g=2*dm*D;
    }
    if (i==111) (n_1[i].fathomed=true);                         //fathoming Rule 1 (ultimo prodotto)
    if (n_1[i].Z_L>n_1[i].Z_U) (n_1[i].fathomed=true);          //fathoming Rule 3 (LB > UB)
    if (n_1[i].Z_U<Zb) (Zb=n_1[i].Z_U);                         //aggiorna UB migliore

}

ofstream livello1 ( "/Users/MarcoBi/Desktop/TESI di LAUREA/Xcode/risultati/livello1.txt" );

for(int i=1; i<112; i++){
   if (n_1[i].fathomed==false)
        (livello1 <<"("<< i <<","<<n_1[i].last_slot<<")"<< " LB=" << n_1[i].Z_L << " UB=" << n_1[i].Z_U << " g=" << n_1[i].g <<'\n');
}

}

float LowerBound(struct nodo n){
 int S[112];
 float d[112];
 float dmin[112];
 int q[112];
 float D;
 float LB;

 for(int i=1; i<112; i++){
    q[i]=q[i-1]+slot[i];
 }

//Calcolo S_pigreco
for(int i=0;i<112;i++){
    S[i]=0;
}

for(int i=n.last_prod +2;i<112;i++){
    for(int j=n.last_prod +1;j<=i;j++){
        S[j]=S[j-1]+slot[j];
    }
}
S[110]=S[109] + slot[110];
S[111]=S[110] + slot[111];

//calcolo somma distanze da slot j+1 a q
for(int i=0;i<112;i++){
    d[i]=0;
}

for(int j=n.last_prod + 1;j<112;j++){
    for(int i=n.last_slot + 1; i<n.last_slot + 1 + S[j]; i++){
        d[j]=d[j]+distanze[i];
    }
}

//calcolo dmin_pigreco
for(int i=n.last_prod +1; i<112; i++){
    dmin[i]= d[i]/S[i];
}

D=0;
for(int i=n.last_prod +1; i<112; i++){
    D=D+dmin[i]*domanda[i];
}
LB=(2*D);
    return LB;
}

float UpperBound(struct nodo n){
 float Ud;
 float Ur;
 int S[112];
 float d[112];
 float dm;
 int D;

for(int i=0;i<112;i++){
    S[i]=0;
}
for(int i=n.last_prod +2;i<112;i++){
    for(int j=n.last_prod +1;j<=i;j++){
        S[j]=S[j-1]+slot[j];
    }
}

//calcolo Ud
for(int i=0;i<112;i++){
    d[i]=0;
}

int t=n.last_slot;

for(int i=n.last_prod +1;i<112;i++){
    for(int j=t + 1; j<=t + slot[i]; j++){
        d[i]=d[i]+distanze[j];
    }
    t=t+slot[i];
    d[i]=d[i]/slot[i];
}
Ud=0;
Ur=0;

for(int i=n.last_prod +1;i<112;i++){
    Ud=Ud + 2*(d[i]*domanda[i]);
}

//calcolo Ur
dm=0;
for(int i=n.last_slot +1; i<361; i++){
    dm=dm+distanze[i];
}

dm=dm/(360-n.last_slot);

D=0;

for(int i=n.last_prod +1; i<112; i++){
    D=D+domanda[i];
}

Ur=2*dm*D;

return min(Ur,Ud);
}

post what you have for the first iteration, so we can see what we are working with. — Hunter McMillen, Feb 21 '12 at 00:15
@HunterMcMillen posted code. Is kind of a mess, but as I said is my first experience in C++. I know all the cycles are starting from index 1st instead of 0th, I'll fix it right now. — marcob8986, Feb 21 '12 at 10:07

score 1 · Accepted Answer · answered Feb 21 '12 at 00:38

1

It sounds like you need to dynamically allocate arrays of your structs and then link them to nodes in your structs. To do this, you would add a pointer to the struct type in the struct itself, and then allocate a new array of structs and assign the resulting address to the pointer in your original struct. Then you can navigate from node to node as necessary when going through your search space.

Your example is a bit more complicated than the linked list examples above, because it will become a tree as you work through the search space, but you can use it to get the basics of dynamic data structures in C then you should be able to adapt it to your situation.

answered Feb 21 '12 at 00:38

BillRobertson42

12,602
4
40
57

I think my nodes need to be single items, not in arrays. starting from the root node I'll need to create new nodes until a certain conditions occurs, and then reiterate for each of the new nodes created. nodes created on the same iteration need to refer to the same node (the father). How can I achieve that? – marcob8986 Feb 21 '12 at 19:34
1

Add a back pointer to the parent and you're good to go, there are examples of doubley linked lists on rosetta code which are similar in notion. Also, not having arrays makes it easier too, then a pointer can only point to a single node, and you just allocate enough memory for one of your structs. In case this is *really* new to you, you will apply the sizeof operator to one of your structs to know how much memory to allocate. – BillRobertson42 Feb 21 '12 at 21:05
just did. I implemented a double linked "tree". each node has a pointer to the next one in navigating order and to the parent as well. thx btw – marcob8986 Feb 21 '12 at 22:03

Branch and bound algorithm implementation

1 Answers1