Branch and bound algorithm implementation
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);
}
Answer
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.