Databases
StackOverflow2013
Postsdbo
POBranch and bound algorithm implementation
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POBranch and bound algorithm implementation
    primarykey
    data
    text
    <p>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. </p> <p>I'd like to know what is the way to approach this problem.</p> <p>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,...</p> <p>So I am asking if someone would be so kind to put me in the right way to approach the problem.</p> <p>here's the code I have so far, working for first iteration, sorry but comments are in italian:</p> <pre><code>// // main.cpp // prova1 // // Created by Marco Braglia on 13/02/12. // Copyright (c) 2012 __MyCompanyName__. All rights reserved. // #include &lt;fstream&gt; #include &lt;iostream&gt; #include &lt;vector&gt; 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 &gt;&gt; distanze[i]; } // visualizza l'array per controllo //for(int i=0; i&lt;360; i++){ //cout &lt;&lt; distanze[i] &lt;&lt; "\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 &gt;&gt; slot[i]; } for(int i=0; i&lt;112; i++){ slot_cum[i]=0; } for(int i=1; i&lt;112; i++){ slot_cum[i]=slot_cum[i-1]+slot[i]; } // visualizza l'array per controllo // for(int i=0; i&lt;111; i++){ // cout &lt;&lt; slot[i] &lt;&lt; "\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 &gt;&gt; COIp[i]; } // visualizza l'array per controllo //for(int i=0; i&lt;111; i++){ // cout &lt;&lt; COIp[i] &lt;&lt; "\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 &gt;&gt; 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&lt;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&lt;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&lt;112;i++){ dm=0; for(int j=1;j&lt;=slot_cum[i];j++){ dm=dm+distanze[j]; } dm=dm/slot_cum[i]; D=0; for(int k=1;k&lt;=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&gt;n_1[i].Z_U) (n_1[i].fathomed=true); //fathoming Rule 3 (LB &gt; UB) if (n_1[i].Z_U&lt;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&lt;112; i++){ if (n_1[i].fathomed==false) (livello1 &lt;&lt;"("&lt;&lt; i &lt;&lt;","&lt;&lt;n_1[i].last_slot&lt;&lt;")"&lt;&lt; " LB=" &lt;&lt; n_1[i].Z_L &lt;&lt; " UB=" &lt;&lt; n_1[i].Z_U &lt;&lt; " g=" &lt;&lt; n_1[i].g &lt;&lt;'\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&lt;112; i++){ q[i]=q[i-1]+slot[i]; } //Calcolo S_pigreco for(int i=0;i&lt;112;i++){ S[i]=0; } for(int i=n.last_prod +2;i&lt;112;i++){ for(int j=n.last_prod +1;j&lt;=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&lt;112;i++){ d[i]=0; } for(int j=n.last_prod + 1;j&lt;112;j++){ for(int i=n.last_slot + 1; i&lt;n.last_slot + 1 + S[j]; i++){ d[j]=d[j]+distanze[i]; } } //calcolo dmin_pigreco for(int i=n.last_prod +1; i&lt;112; i++){ dmin[i]= d[i]/S[i]; } D=0; for(int i=n.last_prod +1; i&lt;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&lt;112;i++){ S[i]=0; } for(int i=n.last_prod +2;i&lt;112;i++){ for(int j=n.last_prod +1;j&lt;=i;j++){ S[j]=S[j-1]+slot[j]; } } //calcolo Ud for(int i=0;i&lt;112;i++){ d[i]=0; } int t=n.last_slot; for(int i=n.last_prod +1;i&lt;112;i++){ for(int j=t + 1; j&lt;=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&lt;112;i++){ Ud=Ud + 2*(d[i]*domanda[i]); } //calcolo Ur dm=0; for(int i=n.last_slot +1; i&lt;361; i++){ dm=dm+distanze[i]; } dm=dm/(360-n.last_slot); D=0; for(int i=n.last_prod +1; i&lt;112; i++){ D=D+domanda[i]; } Ur=2*dm*D; return min(Ur,Ud); } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USMarcoBi
    1. USMarcoBi
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POBranch and bound algorithm implementation
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POBranch and bound algorithm implementation
      1. This table or related slice is empty.
      1. VTUpMod
    1. COpost what you have for the first iteration, so we can see what we are working with.
      singulars
      1. POBranch and bound algorithm implementation
      1. USHunter McMillen
    2. CO@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.
      singulars
      1. POBranch and bound algorithm implementation
      1. USMarcoBi
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload