TomSym Cutting Sheet Metal

From TomWiki
Jump to navigationJump to search

Notice.png

This page is part of the TomSym Manual. See TomSym Manual.

Problem description

A sheet metal workshop cuts pieces of sheet metal from large rectangular sheets of 48 decimeters × 96 decimeters (dm). It has received an order for 8 rectangular pieces of 36 dm × 50 dm, 13 sheets of 24 dm × 36 dm, 5 sheets of 20 dm × 60 dm, and 15 sheets of 18 dm × 30 dm. Theses pieces of sheet metal need to be cut from the available large pieces. How can this order by satisfied by using the least number of large sheets?

Variables

patterns                   Each column represent a possible sheet.
demand                     Wanted rectangles

Reference

Applications of optimization... Gueret, Prins, Seveaux

% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$
% Written Oct 7, 2005.   Last modified Apr 8, 2009.

% Have to manually evaluate all the possible patterns.

Problem setup

patterns = [1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0;...
    2 1 0 2 1 0 3 2 1 0 5 4 3 2 1 0;...
    0 0 0 2 2 2 1 1 1 1 0 0 0 0 0 0;...
    0 1 3 0 1 3 0 2 3 5 0 1 3 5 6 8];
demand = [8;13;5;15];

p = size(patterns,2);
use = tom('use',p,1,'int');

% Bounds
bnds = {0 <= use};

% Minimum demand must be met
con = {patterns*use >= demand};

% Objective
objective = sum(use);

constraints = {bnds, con};
options = struct;
options.solver = 'cplex';
options.name   = 'Cutting Sheet Metal';
sol = ezsolve(objective,constraints,[],options);

PriLev = 1;
if PriLev > 0
    x      = sol.use;
    idx    = find(x);
    order  = [x(idx) idx];
    for i = 1:length(idx),
        disp(['cut ' num2str([order(i,1)]) ' sheet(s) in pattern ' num2str([order(i,2)])])
    end
end

% MODIFICATION LOG
%
% 051010 med   Created.
% 060112 per   Added documentation.
% 060125 per   Moved disp to end
% 090308 med   Converted to tomSym
Problem type appears to be: mip
Time for symbolic processing: 0.0082153 seconds
Starting numeric solver
===== * * * =================================================================== * * *
TOMLAB - TOMLAB Development license  999007. Valid to 2011-12-31
=====================================================================================
Problem: ---  1: Cutting Sheet Metal            f_k      11.000000000000002000
                                              f(x_0)      0.000000000000000000

Solver: CPLEX.  EXIT=0.  INFORM=101.
CPLEX Branch-and-Cut MIP solver
Optimal integer solution found

FuncEv   10 
CPU time: 0.015600 sec. Elapsed time: 0.004000 sec. 
cut 3 sheet(s) in pattern 1
cut 5 sheet(s) in pattern 3
cut 2 sheet(s) in pattern 4
cut 1 sheet(s) in pattern 7