3
$\begingroup$

The problem below aims to minimize the cutting leftovers from each cut :

A company manufactures desks for kids gardens and primary schools, colleges and high schools. The leg of these desks all have the same diameter, but are of different lengths: 40cm for the smallest, 60cm for the medium and 70cm for the large. They are cut from 1.5m or 2m long steel bars.

This company receives an order from 108 small desks, 125 medium and 100 large.

How to carry out this order while minimizing the leftovers.
A. Formulate this optimization problem using an integer number linear program.
B. Use the Cplex solver to solve it.

Modeling the problem : The tables below represent every method and possibility for each leg length:

  1. Cutting cases and leftovers using 1.5m -150cm- steel bar :

| Case # /Leg length | --1-- | --2-- | --3-- | --4-- | --5-- | --6-- | Order |
|---------------------------|-------|-------|-------|--------|-------|--------|---------|
| Leg 1 -40cm--------- |.. 3 ..|.. 2 ..|.. 0 ...|.. 2 ....|.. 0 ..|.. 0 ....|.. 432 |
| Leg 2 -60cm--------- |.. 0 ..|.. 0 ..|.. 2 ...|.. 1 ....|.. 1 ..|.. 0 ....|.. 500 |
| Leg 3 -70cm--------- |.. 0 ..|.. 1 ..|.. 0 ...|.. 0 ....|.. 1 ..|.. 2 ....|.. 400 |
| Falls in cm----------- |.. 30 |.. 0 ..|.. 30 .|.. 10 ..|.. 20 |.. 10 ..|-------- |

For example :
The first column -case #1- means that with a 1.5m steel bar we can cut 3 legs of 40cm each with 30cm leftover.
The second column -case #2- means that with one bar steel of 1.5m we can cut 2 legs of 40cm and 1 leg of 70cm with no leftovers.

  1. Cutting cases and leftovers using 2m -200cm- steel bar :

| Case # /Leg length | --1-- | --2-- | --3-- | --4-- | --5-- | --6-- | --7-- | --8-- | --9------- | Order |
|---------------------------|-------|-------|-------|--------|-------|--------|---------|---------|---------|---------|
| Leg 1 -40cm--------- |.. 5 ..|.. 0 ..|.. 2 ...|.. 0 ....|.. 0 ..|.. 1 ....|.. 3 ....|.. 3 ....|.. 1 ....|.. 432 |
| Leg 2 -60cm--------- |.. 0 ..|.. 3 ..|.. 2 ...|.. 2 ....|.. 1 ..|.. 0 ....|.. 0 ....|.. 1 ....|.. 1 ....|.. 500 |
| Leg 3 -70cm--------- |.. 0 ..|.. 0 ..|.. 0 ...|.. 1 ....|.. 2 ..|.. 2 ....|.. 1 ....|.. 0 ....|.. 1 ....|.. 400 |
| Falls in cm----------- |.. 0 |.. 20 ..|.. 0 .|.. 10 ..|.. 20 |.. 10 ..|.. 10 ..|.. 20 ..|.. 30 ..|-------- |

Cplex code

//Variables definition : 
// x = a case that could be from both tables above 
// i = [1,2] : 1 => when we use the 1.5m steel bar, 2 => when we use 2m steel bar; 
// j = [1..9] : for every case from the tables above -for i=1; j=[1..6] | for i=2; j=[1..9]; 
// z = My objective function; 
// contrLEG* = constraints for each leg; 

dvar int x11;
dvar int x12;
dvar int x13;
dvar int x14;
dvar int x15;
dvar int x16;
dvar int x21;
dvar int x22;
dvar int x23;
dvar int x24;
dvar int x25;
dvar int x26;
dvar int x27;
dvar int x28;
dvar int x29;

dexpr int  z=30*x11+30*x13+10*x14+20*x15+10*x16+20*x22+10*x24+20*x26+10*x27+20*x28+30*x29;

minimize z;

subject to {
  contrLEG1:
   3*x11+2*x12+2*x14+5*x21+2*x23+x26+3*x27+3*x28+x29 >= 432;
   
  contrLE2:
  2*x13+x14+x15+3*x22+2*x23+2*x24+x25+x28+x29 >= 500;
  
  contrLEG3: 
  x12+x15+2*x16+x24+2*x25+2*x26+x27+x29 >=400;

//Cplex is returning the following values :
// X=200; 
// Y = 600; 
// Z = 36000;
  
  }

Question part

  1. Can anyone tells me if I'm doing it the right way?

  2. Can anyone confirm the values returned by Cplex?

  3. Does 200 and 600 means that the manufacturer needs 200 steel bar of 1.5m and 600 steel bar of 2m?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Would you try using the cutting stock problem which comes with CPLEX and can be found in its example directory? $\endgroup$
    – A.Omidi
    May 15, 2020 at 8:01

1 Answer 1

Reset to default
2
$\begingroup$

I think you have some errors when you wrote

Cutting method and falls using 2m -200cm- steel bar

The model is small enough for a naïve model without pattern:

range R=1..3;

int sizes[R]=[40,60,70];
int demand[R]=[108,125,100];


range M=1..2;
int steelbars[M]=[150,200];

int nbMaxBarOfEach=200;
range B=1..nbMaxBarOfEach;

// how many shape r in R do we cut in bar b in B of size m in M
dvar int+ cut[M][B][R];
// leftover on bar b in B size m in M
dvar int+ leftOver[M][B];
// total leftover
dvar int totalLeftOver;

minimize totalLeftOver;
subject to
{

  totalLeftOver==sum(m in M,b in B) leftOver[m][b]-sum(m in M) steelbars[m]*sum(b in B) (0==sum(r in R)cut[m][b][r]) ;

  forall(m in M,b in B) ctBar:leftOver[m][b]+sum(r in R)sizes[r]*cut[m][b][r]>=steelbars[m];

  forall(r in R) ctDemand:sum(m in M, b in B) cut[m][b][r]==demand[r];
}

int isUsed[m in M][b in B]=(0!=sum(r in R)cut[m][b][r]);

execute display
{
  for(var m in M)
  {
    writeln();
    writeln("For size ",m);
    for (var b in B) if (isUsed[m][b])
    {
      writeln();
      for(var r in R) if (cut[m][b][r]!=0) write(cut[m][b][r], " times ",sizes[r]," ");
    }
    writeln();
  }
}

which gives 0 as the minimum leftover

Your model

dvar int+ x11;
dvar int+ x12;
dvar int+ x13;
dvar int+ x14;
dvar int+ x15;
dvar int+ x16;
dvar int+ x21;
dvar int+ x22;
dvar int+ x23;
dvar int+ x24;
dvar int+ x25;
dvar int+ x26;
dvar int+ x27;
dvar int+ x28;
dvar int+ x29;

dexpr int  z=30*x11+30*x13+10*x14+20*x15+10*x16+20*x22+10*x24+10*x26+10*x27+20*x28+30*x29;

minimize z;

subject to {




  contrLEG1:
   3*x11+2*x12+2*x14+5*x21+2*x23+x26+3*x27+3*x28+x29 >= 108;

  contrLE2:
  2*x13+x14+x15+3*x22+2*x23+2*x24+x25+x28+x29 >= 125;

  contrLEG3: 
  x12+x15+2*x16+x24+2*x25+2*x26+x27+x29 >=100;



  }

also gives 0 leftover

NB:

What you could do is minimize the number of bars.

For that you may use lexicographic multiobjective:

You may change

minimize z;

into

minimize staticLex(z,x11+x12+x13+x14+x15+x16+x21+x22+x23+x24+x25+x26+x27+x28+x29);

And you could also be a bit more generic if you generate the patterns in the CPLEX model:

// 3 sizes
range R=1..3;

int sizes[R]=[40,60,70];
int demand[R]=[108,125,100];

// 2 bars
range M=1..2;
int steelbars[M]=[150,200];

tuple pattern
{
  int a;
  int b;
  int c;
  int leftover;
}

int K=max(m in M) steelbars[m] div min(r in R) sizes[r];

{pattern} patterns[m in M]={<a,b,c,steelbars[m]-a*sizes[1]-b*sizes[2]-c*sizes[3]> | a,b,c in 0..K
 : 0<=steelbars[m]-a*sizes[1]-b*sizes[2]-c*sizes[3] < 40};

{pattern} allPatterns=union(m in M) patterns[m]; 
int qty[p in allPatterns][r in R]=(r==1)?p.a:((r==2)?p.b:p.c);

tuple option
{
  int m;
  pattern p;
}


{option} options={<m,p> | m in M,p in patterns[m]};

dvar int+ cut[options];

dexpr int leftover=sum(o in options) cut[o]*o.p.leftover;

minimize staticLex(leftover,sum(o in options) cut[o]);

subject to
{
  forall(r in R) demand[r]<=sum(o in options)cut[o]*qty[o.p][r];
} 

execute display
{
  for(var o in options) if (cut[o]!=0) 
  {
    write(cut[o]," patterns - ");
    for(var r in R)  if (qty[o.p][r]!=0) write(qty[o.p][r]," * ",sizes[r]," - ");
    write(" in ",steelbars[o.m]);
    writeln();
  }
}
Improve this answer
$\endgroup$
3
  • $\begingroup$ Sorry for the typo errors, my apologies. I tried to run your code and it returns the exact same values for X,Y,Z as my code returns and I confirm your saying . My question now is if my code returns the same values as yours, then whats the difference between both of them ? $\endgroup$
    – JirenOppaik
    May 15, 2020 at 22:24
  • 1
    $\begingroup$ If you take your original model and change all dvar int into dvar int+ you ll get zero letfover too $\endgroup$
    – Alex Fleischer
    May 16, 2020 at 7:17
  • $\begingroup$ Thank you very much sir, your help was needed to me so I can reach my wanted results. I really do appreciate your help $\endgroup$
    – JirenOppaik
    May 28, 2020 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.