solver freeze/loop with big data and int or bin vars

[Trigun87]

hello, i wanna solve a big model but i have a problem when i try to use the var as int or bin i get result if i don't add the int or bin but as soon i add that i never get a result (after 2 hrs was still stucked) here the model

[benhannel]

I'd also like to use this to solve a large integer program. It's possible your problem is just hard- integer programming is NP complete in the general case. Is it possible to generate a smaller variant of your problem to see how it scales?

[Trigun87]

i make the model with this JS code (this should be the 1 that generated the model i sent last time)

<script src="https://unpkg.com/javascript-lp-solver/src/solver.js"></script> 
<script>    
dip = ["u1","u2","u3","u4"];
temps = []; 
temps4 = []; 
temp5 = {};
for (j=0;j<7;j++){
  temp3 = [];  
  for (k=0;k<dip.length;k++){ 
    temps2 = [];           
    for (t=8;t<17;t++){               
      for (i=13;i<=40-t;i++){ 
          temps2.push(dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2));  
          temps4[k] = stringOrEmpty(temps4[k]) + ((t/2)+ " " + dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2)) + " + ";
          temp5[dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2)] = 1;
          //temps.push("0 <= " + dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2) + " <= 1");
          for (l=0;l<=t;l++){                                                       
            temp3[i+l] =  stringOrEmpty(temp3[i+l]) + (dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2)) + " + ";
          }
      }
    }
    temps.push(temps2.join(" + ") + " <= 1");   //la somma dei turni deve esser uguale a 1 (non può fare 2 turni lo stesso giorno)   
  }
  for (i=13;i<=40;i++){
    temps.push(temp3[i].slice(0,-3) + " >= 1");  //la fascia oraria è coperta da x=1 persona (va cambiato con dati presi da db)
  }
}

for (k=0;k<dip.length;k++){  
    temps.push(temps4[k].slice(0,-3) +" - "+ dip[k] + "_extra = 40");    
}
temps.unshift("min: " + dip.join("_extra + ") + "_extra");    
//temps.push("int "+ temps4.join(", "));

function stringOrEmpty( entity ) {
    return entity || "";
}   
function timeChange( x ) {
    return Math.floor(x) + "_" + ((x - Math.floor(x)) * 60);
}                                            

var model = solver.ReformatLP(temps);
//model.binaries = temp5;      
console.log(model);
document.getElementById("demo").innerHTML = solver.ReformatLP(model);
//document.getElementById("demo2").innerHTML = JSON.stringify(model);
document.getElementById("demo2").innerHTML = JSON.stringify(solver.Solve(model),null, 2);

</script> 

this will make a smaller model

<script src="https://unpkg.com/javascript-lp-solver/src/solver.js"></script> 
<script>    
dip = ["u1"];
temps = []; 
temps4 = []; 
temp5 = {};
for (j=0;j<1;j++){
  temp3 = [];  
  for (k=0;k<dip.length;k++){ 
    temps2 = [];           
    for (t=8;t<9;t++){               
      for (i=13;i<=22-t;i++){ 
          temps2.push(dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2));  
          temps4[k] = stringOrEmpty(temps4[k]) + ((t/2)+ " " + dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2)) + " + ";
          temp5[dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2)] = 1;
          //temps.push("0 <= " + dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2) + " <= 1");
          for (l=0;l<=t;l++){                                                       
            temp3[i+l] =  stringOrEmpty(temp3[i+l]) + (dip[k]+"_"+j+"_"+timeChange(i/2)+"_"+timeChange((i+t)/2)) + " + ";
          }
      }
    }
    temps.push(temps2.join(" + ") + " <= 1");   //la somma dei turni deve esser uguale a 1 (non può fare 2 turni lo stesso giorno)   
  }
  for (i=13;i<=22;i++){
    temps.push(temp3[i].slice(0,-3) + " >= 1");  //la fascia oraria è coperta da x=1 persona (va cambiato con dati presi da db)
  }
}

for (k=0;k<dip.length;k++){  
    temps.push(temps4[k].slice(0,-3) +" - "+ dip[k] + "_extra = 10");    
}
temps.unshift("min: " + dip.join("_extra + ") + "_extra");    
//temps.push("int "+ temps4.join(", "));

function stringOrEmpty( entity ) {
    return entity || "";
}   
function timeChange( x ) {
    return Math.floor(x) + "_" + ((x - Math.floor(x)) * 60);
}                                            

var model = solver.ReformatLP(temps);
//model.binaries = temp5;      
console.log(model);
document.getElementById("demo").innerHTML = solver.ReformatLP(model);
//document.getElementById("demo2").innerHTML = JSON.stringify(model);
document.getElementById("demo2").innerHTML = JSON.stringify(solver.Solve(model),null, 2);

</script> 

by changing the for and the dip dimensions it can freely scale (the int is commented )

[Trigun87]

@JWally u have an idea how i can solve this problem? :-D i have X employees that need to be split in a week for cover the daily necessity. what i'm doing is to generate all the possible turns from 6 am to 8 pm for each employee, but this means i have a turn from 6 to 10, 6.30 to 10.30 .... 6 to 11 .... 6 to 12 ... etc this for every day of the week

for (t=8;t<17;t++){  //t = 30 min so a turn from 4 to 8 hrs             
      for (i=13;i<=40-t;i++){ // from 6,30 to 20-t 

and what should find is the best allocation of resources for have the timezone covered by X number of employees

  for (i=13;i<=40;i++){
    temps.push(temp3[i].slice(0,-3) + " >= 1");  // "1" is a db value for each 30 min 
  }

and get the min of the extra hours of works

for (k=0;k<dip.length;k++){  
    temps.push(temps4[k].slice(0,-3) +" - "+ dip[k] + "_extra = 40"); //hours of works for each employees in the contract (find the extra hours)   
}
temps.unshift("min: " + dip.join("_extra + ") + "_extra");    //min of the extra works of hours 

the problem is that i have something like 10k vars :-) and the solver die in the process if you have int or bin vars https://jsfiddle.net/z5v8cnxL/ here u can see that line 45 is commented and if u remove the comment the page will freeze