[eclipse-clp-users] Linear Optimization Problem

From: Igor Kondrasovas <igor_at_...186...>
Date: Wed, 26 Aug 2009 12:51:29 -0300
Hello All,


This is my first project using CLP and looking at the sample projects on the
Eclipse page I couldn't find something similar to the problem I must solve,
so I would like to gently ask you for some support or guidance. Hopefully
with your help I will be improving my skills and performing more complex


Basically what I would like to do is to optimize the cuttings of linear
materials (pipes, tubes, bars, etc) in order to maximize the material usage.


So, my input data would be the size of the raw bars. For example 6 meters,
12 meters, etc.. and the size of every single piece I must cut from this
bars ( 50 cm, 10 cm, 90 cm, etc). 


To start, what I could successfully do is to maximize the material usage
allocating the maximum amount of pieces in a single bar. So I created and
array of pieces [piece1, piece2, piece3,..] and the domain for every piece
could be either 0 or 1, indicating if this piece was or wasn't place in that
bar. Something like the code above:


:- lib(ic), lib(branch_and_bound).


linear(BarSize, Cuttings) :-

    % Piece length used in the example

    Piece1Length = 500,

    Piece2Length = 400,

    Piece3Length = 100,

    Piece4Length = 300,

    Piece5Length = 100,

    Piece6Length = 50,

    Piece7Length = 800,

    Piece8Length = 150,

    Piece9Length = 100,

    Piece10Length = 500,



    % Boolean variable to indicate if the pice will or not be used

    Cuttings = [ Piece1, Piece2, Piece3, Piece4, Piece5, Piece6, Piece7,
Piece8, Piece9, Piece10],


    Cuttings #:: 0..1,


    % The wasted material should be the minimum and greater than zero.

    Waste #= BarSize - (Piece1 * Piece1Length + 

               Piece2* Piece2Length + 

               Piece3* Piece3Length + 

               Piece4* Piece4Length + 

               Piece5* Piece5Length + 

               Piece6* Piece6Length + 

               Piece7* Piece7Length + 

               Piece8* Piece8Length + 

               Piece9* Piece9Length + 

               Piece10* Piece10Length), 

    Waste #>= 0,


    minimize(labeling(Cuttings), Waste).


So calling "linear(1000, P)." will retrieve the results properly.



This works relatively fine, however in order to support multiple  Bars (with
different sizes) I was thinking to increase the domain for the "Cuttings" in
order to make its value indicate the bar where every piece is allocated,
since it can only be allocated in one bar. However, I don't know how can I
change the constraints in order to respect the bar length.


I would appreciate any help.


Thanks in Advance,


Igor Kondrasovas.


Received on Wed Aug 26 2009 - 16:09:00 CEST

This archive was generated by hypermail 2.3.0 : Mon Jul 22 2019 - 12:14:57 CEST