OR Spektrum (1998) 20:251-258

0Rf trum@ Springer-Vedag 1998

Optimal scrap combination for steel production
Klaus-P. Bernatzki ~, Michael R. Bussieck 2, Thomas Lindner:, Marco E. Liibbecke 2
1 H~ittenwerkeKrupp Mannesmann, Duisburg, Deutschland
2 TU Braunsctlweig,MatbematischeOptimierung, Pockelsstrage 14, D-38106 Braunschweig, Deutschland
Received: 13 March 1998 / Accepted: 15 October 1998

Abstract. In steel production, scrap metal is used for cooling the enormous quantity of heat produced by blowing oxygen on hot metal. Scrap differs in regard to the content ofiron and of some tramp elements. The price of the scrap
depends on these attributes. Each melting bath unit of steel
has its own material constraints for the amount of iron andtramp elements in order to guarantee the desired quality. In
addition, the transportation of scrap is restricted because it
needs time and space: the scrap is kept in some railroad carsin the scrap hall; empty cars must leave the hall, filled carsmust be taken from several railroad tracks in the scrap yard
and assembled to a train before transportation to the hall.
There are upper limits for the number of cars in the hall andin the train, also for the number of railroad tracks used for
assembly.
Our objective is to find a minimum cost scrap combination for each melting bath unit of steel that obeys the material
and transportation constraints. We model the problem usinga MIP (mixed integer linear programming) approach. Reallife situations are solved with the commercial MIP-solver
CPLEX. We present computational results which show significant improvement compared to the strategy applied today.
Zusammenfassung. In der Stahlproduktion wird zur Ktihlung des fliissigen Roheisens Metallschrott hinzugefiigt. Dabei wird Schrott mit unterschiedlichem Gehalt an Eisensowie an Spurenelementen eingesetzt. Abh~ingig von dieser
Zusammensetzung variiert der Einkaufspreis fiJr den Schrott.
Ftir jeden produzierten Stahltyp sind gewisse Grenzwerte fiir
Eisenanteil und den Gehalt an Spurenelementen im Stahleinzuhalten, um die geforderte Qualitfit zu erreichen. Der
Schrott wird in Eisenbahnwaggons gelagert. Dadurch, dab
Ztige aus diesen Waggons gebildet werden miissen und diese
Zfige die Werkshalle auf dem vorgegebenen Gleisnetz erreichen bzw. verlassen mtissen, entstehen zus~tzlich zu den
Materialrestriktionen auch noch Transportrestriktionen.
Unser Ziel ist es, fiir jeden Produktionsprozeg die kostengiinstigste Schrottzusammenstellung zu linden, so dab alle
Material- und Transportrestriktionen eingehalten werden.
Wir modellieren das Problem mit Hilfe eines gemischt-ganzCorrespondence to: T. Lindner (e-mail: T.Lindner@tu-bs.de)zahligen linearen Programms (MIP) und 16sen es mit dem
kommerziellen MIP-L6ser CPLEX. Unsere Rechenergebnisse ftir reale Produktionsserien zeigen bemerkenswerte
Einsparungen gegeniiber dem zur Zeit verwendeten Verfahren.
Key words: Mixed integer programming - Steel production

Schliisselw~irter: Gemischt-ganzzahlige lineare Programmierung - Stahlproduktion

1 Problem
Situation

HtRtenwerke Krupp Mannesmann (HKM) produce slabs andround bars by casting about 60 melting bath units of steel
per day. There are more than 1,500 different steel types
according to the various purposes of subsequent treatments.
Therefore, each melting bath unit has its own lower and/or
upper limits for the chemical composition with regard to
more than 30 elements, especially the tramp elements copper(Cu), chrome (Cr), nickel (Ni), molybdenum (Mo), and tin(Sn).
Each melting bath unit, further on called "process", isproduced in one of the two so-called "converters" by blowing more than 10,000 m 3 oxygen on about 200 t of hot metal
within less than 20 minutes. The hot metal, supplied fromthe blast furnaces, has a temperature of at least 1,300~
The carbon in the hot metal and the oxygen burn to a gas(CO), which leaves the converter. This oxidation produces
an enormous quantity of heat, resulting in a heating up of
more than 600~ A computer model calculates the particular temperature needed at the end of the blowing process
in order to avoid problems with the temperature during thecasting process starting 60-120 minutes later. This particular temperature ranges between 1,600 and 1,800~ In order
to meet the desired temperature, before the liquid steel istapped into a ladle, the oxidation heat must be reduced by252
using scrap metal and iron ore. Metallurgical models calculate the particular amount of scrap and iron ore needed
for cooling for up to 30 charges in advance. The amount ofscrap ranges between 25 and 90 t for each process.
Scrap is a valuable material and costs much more thaniron ore. The carloads come from different sources:- some are collected as residuary products in H K M ' s own
production process, for example at the casting machines
and in the finishing shop,- some are obtained as waste products from other companies of the steel industry, e.g. rolling mills,- some are bought from scrap dealers, who got the scrap
by the demolition of halls and machines.
The received scrap is divided into several classes, called
A, B, C and so on. All classes are assumed to have the same
cooling effect (at the moment), but different relative iron andtramp element amounts, and prices. The cheaper scrap has a
low content of iron and/or high content of tramp elements.
For most charges the cheapest scrap does not comply to theupper limits for the chemical composition, so that anotherscrap class or a combination of different scrap classes must
be used. For some classes, the chemical behavior during theblowing process is especially difficult to handle, so that only
few tons of them may be chosen.
Scrap can be substituted by a mixture of iron ore andadditional hot metal, because one unit of iron ore and threeunits of hot metal have the same cooling effect as four unitsof scrap. As this substitution leads to about 10% less amountof iron, the formula must be multiplied by 1.1. For example,
3.3 t of iron ore and 9.9 t of hot metal can be chosen insteadof 12 t of scrap. The substitution is limited by a maximumof 9 t of iron ore, because iron ore must be added in small
portions during the blowing process.
Scrap must completely be filled in the converter ahead of
the hot metal. For each charge it is supplied from the scrap
hall by using cranes and transport containers. In the hall, thescrap is kept in railroad cars on two tracks. When all cars on
one track are empty, a transport company is under contract
to remove the cars and to fetch new filled cars from several
parallel railroad tracks at the scrap yard. This situation happens every 90-180 minutes. Before transportation to the hallthe filled cars must be assembled to a train, whose lengthmust comply to the capacity of the hall. That is why a train
must not exceed 8 cars. On the other hand, transportationneeds so much time that the maximum number of cars isdesired in order to ensure the supply.
Each filled car at the scrap yard contains between 30 and
50 t of one particular class of scrap. For each train the cars
have to be chosen according to the planned production program and the suitable classes of scrap. They may be locatedon several tracks, but the locomotive can only work on up to
three tracks. The tracks are divided into "single-class" and"multi-class". On single-class tracks, all cars contain scrap of
the same class. From these, cars may be selected only fromthe front, whereas those from the multi-class tracks may be
selected from any position. These transportation constraints
must be obeyed in order to guarantee that the train will arriveat the hall in time.

K.-P. Bernatzki et al.: Optimal scrap combinationfor steel production
I to the converter~~~transportcontainers/vu

tJtttttttlltltttH
ttlttltllttJttA\q-u
scrap hallFig. 1. Scrap hall and scrap yard

scrapyardtracks

Fig. 2. Railroad cars containingscrap

Operations
Steel is produced day and night, even at weekends. Therefore
one of the so-called "scrap dispatchers" must take care thatthe scrap needed for each process is available without delay
at any time. The scrap dispatcher works in a control post in
the scrap hall and has to execute three main operations:- check the cars coming to the scrap yard and determine
the scrap class for each car,- decide when the transport company has to fetch new
filled cars from the scrap yard and which cars shall beassembled to a train,- decide when and how much scrap of the different classes
in the hall has to be filled into the transport containers
for each charge.
A camera takes several pictures of each car before it
arrives at the scrap yard. At the same time the dispatcher
can see the pictures on a monitor, judge the scrap and thus
implement the quality control. Scrap not matching the orderis sent back to the supplier.
An information system shows the scrap supply, i.e. allcars, located in the hall or at the scrap yard, including theirpositions, classes and amounts of scrap. This is shown in
Fig. 3: There are three columns for each track indicating car
number, scrap class and scrap amount. As one can see, there
are tracks containing one class of scrap whereas other tracks
contain different classes.
Also, the information system shows the scrap demand,
i.e. all initiations of blowing processes, planned in the future production schedule, including the particular kind of

K.-P. Bernatzki et al.: Optimal scrap combination for steel production
S651 H A R F 4 1 . . . . . . . .
W a g g o n s in der G l e i s h a r f eletzge A k t u a l i s i e r u n g : 20.01 11:54
G5022 0 7 2 4 t o G5024 0676to G5025 0181to G5026 8896to
WNR
K l a s to W N R
Klas to W N R
Klas to W N R
Kias to5524 c198 39 9869 C197 41 1288 W199 56 9494 C197 47
7339 C198 40 0902 C197 38 2987 W199 57 7118 C197 443288 C197 43 7030 C197 38 7338 B199 51 4468 C197 41
0386 C197 48 8349 C197 40 0493 B199 59 1417 C197 49
2543 C197 53 1483 C197 36 0886 D197 42 1652 C197 43
4799 C187 49 2342 C187 46 1661 D197 41 5718 A199 45
8655 C 1 9 8 24 9658 C197 42 1756 D197 34 3313 Y188 2?
0517 C 1 9 8 28 8696 C497 39 4080 D197 42 6599 C197 56
2389 C197 30 8366 C197 36
6599 C197 56
0498 C198 50 1605 C197 35
1586 C197 59
0602 C197 28 9665 C197 364842 C187 51
1707 C198 28 9287 C197 13
8587 C197 57
8752 C 1 9 8 58 0911 C197 33
7064 C187 56
1157 C 1 9 8 57 7233 C197 32
1806 C197 58
5929 C 1 9 8 49 0029 Ci97 32
1222 C197 51
8139 C197 34 8258 C197 30
3216 C197 57
8965 C197 36 6327 C197 34
4321 C197 51
0953 C198 31 4173 C198 55
0209 C197 52

250

20.01

G5027 0483to
WNR
Klas to6561 C197 37
4498 C197 53
7416 C197 52
0810 C197 45
0650 C197 43
2770 C197 38
4132 C197 32
5055 C197 38
5055 C197 38
0079 C197 82

253

12:46

03/04
01/01
G6003 0367to
WNR
Klas to0340 C199 82
1773 C198 87
2616 C198 55
1752 C187 232879 C197 425106 C198 54
4782 C199 54

Fig. 3. Screenshot of a part of the scrap yard

steel type, the calculated amount of hot metal and cooling material, and a recommended scrap class combination(cf. Fig. 4). Every line corresponds to one process. The firsttwo coluns show the number of the used converter and aprocess identification number. The column entitled "Guete"holds a character determining the steel type (and therefore
the material constraints), the columns "Aufteilung in Schrottklasse/Menge" represent the scrap combination recommendation.

Optimization
At the moment, there is a simple strategy henceforth named
HKM heuristic) to determine the recommendation: for eachsteel type, one of eight different predetermined scrap classcombinations is chosen by rules regarding the material constraints. The scrap supply and the transport constraints arecompletely ignored. Therefore, the dispatcher often has todeviate from the recommendation, if a particular scrap classis not available at the scrap yard or is blocked due to thetransport constraints.
If the assembly of a train with cars containing scrap combinations proposed by the H K M heuristic is impossible, thescrap dispatcher has to decide for an alternative scrap combination, which generally results in scrap of higher quality
but also higher cost. Since there is no time for complex
calculations at that moment, the quality and the cost of achosen scrap combination depend on the personal experience of the dispatcher. An analysis of this partially manual
process yields the option of a significant reduction of costs.
Therefore, H K M aims at solving the following optimization problem:
Find a minimal cost combination of scrap classes andiron ore for the next 5-8 blowing processes, starting withthe first process which must be supplied from the scrap yard.
The combination must satisfy the following constraints:- the calculated cooling effect for each process is ensured,
the material constraints for each process are not violated,- the transport constraints for each train are obeyed.

$631 ....................

K
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
i
2
1

PLANR
94417
33860
88633
27292
33878
88641
93716
88658
27300
33886
88666
93724
88674
27318
83732
33613
27375
33621
65896
27383

Schrott

Disposition:

150

20.01

12:45

01/02

SEP: 12:43
S R D Nah: 12:44
S R D Fern: 12:44
Guete
B B E G 1.R.Esto A u f t e i l u n g in S c h r o t t k l a s s e / M e n g e :V 1 3 M N C 13:07 237 56E C.
46 D... 09 L... 02 . . . . . . . . . . . .
P 4 0 M N C 13:26 2 3 6 6 9 E C .
88 L...
02 . . . . . . . . . . . . . . . . . .
C.
62 Y...
15 . . . . . . . . . . . . . . . . . .
S30/D7 13:46 2 3 5 7 7
S35/ 1 14:05 2 3 6 7 2
C.
72 . . . . . . . . . . . . . . . . . . . . . . . .
P40MNC 14:36 2 3 6 7 3
C.
72 L...
02 . . . . . . . . . . . . . . . . . .
$30/d7 14:55 2 3 5 8OC.
64 Y...
16 . . . . . . . . . . . . . . . . . .
C67/ 3 15:14 2 3 4 6 2
B.
62 . . . . . . . . . . . . . . . . . . . . . . . .
$30/D7 15:33 2 3 8 8 1
C.
64 Y.,.
16 . . . . . . . . . . . . . . . . . .
C.
76 . . . . . . . . . . . . . . . . . . . . . . . .
$85/ 1 15:52 2 3 8 7 6
P40MNC 16:12 2 3 6 6 9C.
68 L.,.
O2 . . . . . . . . . . . . . . . . . .
C...
63 Y.,.
16 . . . . . . . . . . . . . . . . . .
$30/D7 16:31 2 3 5 7 9
C67/ 3 16:51 2 3 4 6 4
B.
64 . . . . . . . . . . . . . . . . . . . . . . . .
837/M3 17:15 2 3 7 7 9C...
63 D...
16 . . . . . . . . . . . . . . . . . .
$35/ 1 17:34 2 3 6 7 4
C...
74 . . . . . . . . . . . . . . . . . . . . . . . .
C67/ 3 18:31 2 3 4 6 4
B...
64 . . . . . . . . . . . . . . . . . . . . . . . .
F36/ 3 19:19 2 3 7 6 9C...
56 D...
14 . . . . . . . . . . . . . . . . . .
V 2 5 C R N 20:17 2 3 8 6 6D...
61 L.,.
05 . . . . . . . . . . . . . . . . . .
C...
57 D...
14 . . . . . . . . . . . . . . . . . .
P36/ 3 20:51 2 8 7 7 2
F47/ 6 21:38 2 3 4 6 5
B.
63 L.,
O2 . . . . . . . . . . . . . . . . . .
C...
55 D...
14 . . . . . . . . . . . . . . . . . .
$528/
21:57 2 3 7 6 9

Fig. 4. Screenshot of the planned converter processes
The optimization result is needed within 20 seconds inorder to meet a total response time of the whole information
system, which will be accepted by the dispatcher.

2

C o n s t r a i n t s

A process requires a particular amount of cooling material.
Cooling material consists of scrap and a combination of ironore and hot metal according to the substitution formula.

Cooling effect constraints
For each process:--the cooling material must meet the calculated cooling
effect, expressed in scrap units,
if iron ore is chosen instead of scrap, the cooling materialmust obey the substitution formula: 1.1 unit of iron ore+ 3.3 units of hot metal = 4 units of scrap.

Material constraints
For each process:the relative amount of the tramp element Cr in the produced steel must not exceed a given level (the same
for Cu, Ni, Mo and Sn). The loss of parts of the input tramp elements due to oxidation during the process
is reflected by a so called output factor, expressing therelative amount that remains,
the relative amount of iron (Fe) in the produced steel
must observe a given lower limit,
the amount of iron ore must not exceed the given upper
limit of 9 t,
- the amount of scrap for each class must not exceed agiven upper limit.

-

-

-

Transportation constraints-

Since every 20-25 minutes a process is started at a converter, 5 - 8 charges represent 100-200 minutes production
time. This is called a process series in the sequel.

For each train from the scrap yard to the hall:- up to eight cars may be used,- cars may be assembled from three tracks or less,- cars in single-class tracks may be selected only from thefront.

254

K.-P. Bernatzki et al.: Optimal scrap combination for steel production

3 ModelCooling effect constraints (for all 1 < k < K )In order to solve the problem of finding a minimum cost
scrap and iron ore combination, we use a mixed integer linear programming model (MIP).
Our model determines the minimum cost combination
based on material costs while ignoring the transport costs.
Continuous variables will determine the scrap, iron ore andadditional hot metal amount while binary variables will givethe decision which cars to take from the scrap yard.
Small (Roman or German) letters are used for indicesand Variables, capital letters for constants.

10/1 le~ + 10/1 l r k + ~Xg,p,k = Jkg,P3ek = rk

The first equation ensures that the right amount of cooling material is used. The second one leads to the desired ironore ! additional hot metal proportion (remember that for one
unit of iron ore, there must be three units of additional hot
metal).

Material constraints (for all 1 < k < K )Constants
The following constants influence the optimization (to simplify our exposition, we only mention chrome (Cr) as tramp
element, there are equivalent constraints for other elements
like Cu, Mo, Ni, Sn):K
number of processes for the train
number of tracks on the scrap yardG%number of cars on track g

Acr (ekCrE +(l~k + rk)CrR + Z(Xg,p&Cr~.p) )
9,P

g,P

/

ekFeE + (Rk + rk)Fen + Z(Xg,p,kFe%.p)g,P

set of all scrap classes
class of scrap in car p of track g
scrap amount in car p of track 9fll~,P

Mg,p

g,P

ek<9

&

desired cooling effect (in scrap units) of processkinitial hot metal amount for process k (this has
to be distinguished from the additional hot metal
amount that is to be determined by our model)

RkP~

price of 1 t of scrap of class ~ (also: PE for ironore, PR for hot metal)Crt~

relative amount of Cr in scrap of class t~ (also:
CrE for iron ore, CrR for hot metal)
output factor of Cr
maximum allowed relative amount of Cr in thesteel produced in process kminimum required relative amount of Fe in thesteel produced in process kmaximum allowed absolute amount of scrap ofclass t~ in one process

Act

Crk
Fek

N~

Variables
Xg,p,k
ek
~k
Wg, p

Sg

scrap amount from track g, car p for process kiron ore amount for process kadditional hot metal amount for process k(binary) indicator that car p from track g is used
for the train(binary) indicator that track g is used for the train

Constraints
When describing the model constraints, we will use ~g,pas an abbreviation for EGO__1Ep~i"Z

Xg,p,k ~ N ~for all classes t~ C J~

The first set of inequalities gives the maximum relative
tramp element amount, the second set the minimum relativeiron amount. The last ones take care that from iron ore andfrom every scrap class, only the specific maximum absoluteamount is used.

Transportation constraints

Wg,p <_8g,P~-~ Sg <<_3gwg,p <_wg,p 1

for single-class tracks g

As we have described earlier, a train can have up to eightcars which must come from no more than three different
tracks. On single-class tracks, cars can only be taken fromthe front (so that if you wish to take the second car on the
track, you must also order the first one).
We now need to link the binary variables for cars andtracks with the continuous variables for the respective scrap
amounts. This is done in the following way and explained
below (see [8]):K

Z xg,p,k <_wg,pMg,pall (g, P)

k=l

Z ~ Xg,P,k <_Sg.
k=l p=l

Mg,p
\p=l

all 9

K.-P. Bernatzki et al.: Optimal scrap combination for steel production

255

The reader may take a look at the first set of inequalities.
If a car is chosen for the train (i.e. w9,p = 1), then up to Mg,punits of scrap can be taken from this car. On the other hand,
if Wg,p = 0, we have ~g,p,k Xg,p,k = 0 and finally Xg,p,k = 0
for 1 < k < K .

Objective function
Our objective function is the cost function for the demanded
scrap, iron ore and additional hot iron. It can be expressed
as follows:

The first sum gives the iron ore and additional hot metal
costs, the second one the costs of scrap in the chosen cars.
Note that even if only a part of the scrap of a car is used,
the whole car has to be paid for.

4 Solving the MIPs
The MIPs resulting from the discussed model have beensolved with the commercial LP/MIP solver CPLEX (version
4.0.7 for HP-9000/735-125 workstations) [1], representing
an efficient implementation of the linear programming based
branch-and-bound algorithm [8]. In particular, CPLEX has
been successfully used for solving problems arising fromacademic as well as from real-life applications. Furthermore,this solver is available on a broad variety of computer systems (including MS-DOS and many UNIX systems).
CPLEX accepts data in standard formats like MPS-files.
We implemented perl scripts which convert the HKM steelworks data into a CPLEX readable file (perl is a "script
language" like awk or sed, it is usually known from UNIXsystems, but also available for MS-DOS).
We have also implemented a CPLEX/LEDA (LEDA isa C++ library providing common complex data types andgraph drawing routines, [7]) based graphic output solution
software called OSCAR. A screenshot is shown in Fig. 5.
On the top window, a train and the scrap mixture for the
next series is shown. The bottom window gives the scrap
yard track status: The highlighted cars are suggested for the
next train. Multi-class tracks are marked with the keyword" S A M M E L " (for the German word "Sammelgleis").

5 Accelerating the MIP solution process
Progress in computer technology and in design of efficientalgorithms and their implementation together with mathematical advance lead in some cases to satisfactory MIP solution times. Unfortunately the MIP of the pure problem
formulation described above can not be solved in the desired time of 20 seconds. We briefly present some model
improvements, which lead to sufficient solution times. These
techniques are primarily based on techniques of polyhedral
optimization. We improve the relaxation of the MIP by valid
inequalities or cuts and do some preprocessing which results

Fig. 5. Screenshot of the optimization software OSCAR

in coefficient reduction and fixing or elimination of variables(cf. [4]). In the last decade, these techniques which provide acloser linear description of the polytope associated with the
MIP, were applied to programs with combinatorial structure [3]. The success of these methods additionally are due
to improvements of the simplex algorithm and interior point
methods for solving linear programs (LP). For an investigation of preprocessing techniques, we refer to [9].

Variable fixing and eliminating
To reduce the size of MIPs, it is often helpful to take a closer
look at the problem structure. Sometimes, there are variables
whose values in an optimal solution can be easily determinedin advance. Thus, they can be replaced by constant values.
This process is called variable fixing.
Consider a single-class track with a scrap class ~ with asmall value of N~ (i.e. only few tons of this scrap can beused in a process). If the first n cars on the track containK 9 N~ or more tons of scrap, cars behind these are neverneeded (which leads to Wg,n+ 1 . . . . .
Wg,Z9 = 0).
A similar strategy can be applied for single-class tracks
containing an expensive scrap class which obeys all material restrictions. Furthermore variables Wp,g with p > 8 forsingle-class tracks can be fixed to 0, because of the limited
number of cars in the train.
Another variable eliminating possibility results from the
combinatorial structure of the problem: On single-class tracks,
taking the first car into the train is equivalent to taking the
track itself for the train. Thus wg,l = Sg for single-classtracks, so we can delete one of the variables.

Coefficient reduction
In an LP-relaxation-based branch-and-bound process, every
LP solution with non-integer values for the integer variables leads to the generation of subproblems (the branchand-bound tree).
Often coefficients in the constraint matrix can be modified (without changing the optimal MIP solution) so that

K.-P. Bernatzki et al.: Optimal scrap combination for steel production

256

already the LP solution becomes integer in some components. Let us focus on the following example: A multi-classtrack contains twelve cars, each holding 50 t of scrap (thatis 600 t altogether). We then have the inequality

specification of branching direction (up: variable fixed to1, down: variable fixed to 0). For the variables mentioned
above we figured out that branching down first yields muchbetter solution performances.

K} 2 } 2 xg,p,k _< 6 0 % .
p

k=lSince only eight cars can be selected, the sum neverexceeds 400, and the constraint can be replaced by
K

}2 }2
p

-< 4o%,

k=l

which is still correct for all solutions with an integer value
for sg, but makes some non-integer solutions infeasible.
In order to use this technique on our model, we needbetter bounds for the scrap sums. These can be found byconsidering that

6 Computational results
HKM have supplied us with several production test files.
Table 1 shows relevant data on the solution process for 17
representative real-life instances. The columns contain thefollowing data: number of constraints, variables, and nonzeroes, LP relaxation value, MIP optimal value, and MIP
solution time.
Table 1. Model data for the HKM instances

~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

- only scrap from eight cars can be taken,- some scrap combinations are not allowed because of theirtramp elements (this is in particular useful for tracks containing the cheap scrap with high relative tramp element
amounts).

Cutting planes
Sometimes, non-integer solutions can be eliminated by adding
constraints (which are not violated by any integer solution)arising from the combinatorial structure of the problem. Such
constraints are called cutting planes (see [8] for an introduction, a survey written in German can be found in [5]).
We give an example for cutting planes in the scrap optimizafion model: /,From the fifth cars of all single-classtracks, only one can be taken into a train (otherwise, there
would be more than eight cars). Still, there is the non-integer
solution of taking 8/15 of each of the first five cars on three
single-class tracks. The non-integer solution can be excluded
by adding} 2 wg,5 < 1,gCG ~where G / denotes the set of single-class tracks. A similar
cutting plane can be found for the third cars on single-classtracks.
We add a couple of useful cutting planes to our model.
A detailed description can be found in [6].

Priority orders
One of the most efficient methods for improving solution
performance besides polyhedral improvements is to assign
a branching priority for variables (see [1]). Variables withhigher priorities will be selected and branched upon in the
branch-and-bound tree before variables with lower priorities.
We put high priorities on the variables wg,i which indicate
if the train includes some cars of the track g. The priority
orders implemented in the CPLEX package also permit theting techm'ques

IT

~

.
229
310
306
308
343
319
342
318
343
393
310
343
343
418
389
322
534

# ~ 0 1 ~
481
725
746
715
741
677
758
685
782
911
731
742
742
959
982
796
1299

4074
6300
6017
5914
6781
6284
6925
6696
6215
7210
6346
6331
6606
9206
8068
6518
10880

111258
69412
97415
94675
76667
92648
91805
96508
99781
92962
92173
88265
98912
90723
97886
98806
71510

-

Sol. j111707
69969
97500
94980
77801
94790
92844
97612
100578
93778
92977
88863
99433
92597
98340
99336
75280

-

Time
0.84 s137.14 s
42.98 s16.97 s1.28 s
26.54 s1.22 s6,85 s
8.63 s12.47 s6,81 s1,28 s8,33 s
20.77 s2,20 s973.10 s
12468.31 s

With accelerating techniquesfTest II #C J #V. I #r j LP Sol. I MIP SoL

Time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

0.9I s10.00 s18.94 s3.56 s2.39 s5.25 s1.12 s3.31 s
4.41 s7.12 s5.49 s1.68 s6.21 s8.87 s1.01 s
16.28 s11.30 s

262
377
323
316
389
335
364
414
417
437
406
432
427
472
475
403
689

440
640
624
592
624
568
648
664
751
824
720
729
712
880
944
784
1280

3782
5687
5013
4879
5785
5289
5927
6670
6079
6568
6389
6351
6482
7809
7889
6524
10937

111258
69755
97415
94675
76667
92749
91830
96576
99781
92962
92448
88614
99025
91358
98139
99335
71954

111707
69969
97500
94980
77801
94790
92844
97612
100578
93778
92977
88863
99433
92597
98340
99336
75280

As one can see, the use of MIP acceleration techniques isessential for a fast calculation as requested by HKM (remember the demanded time limit of 20 s) and yield a speedup offactor 1000 for instance number 17.
Table 2 shows a cost comparison of the HKM heuristic (column "HKM") and our MIP model ("MIP") for the
instances. The solutions generated from our model promise
scrap combinations of significiantly reduced cost than those257

K.-P. Bernatzki et al.: Optimal scrap combination for steel production
Table 2. Cost comparison

Additional features

Test

HKM

Solution costs
MIP
Test

1
2
3
4
5
6
7
8
9

115700
76398
99902
99267
86510
98100
95312
102909106698111707
69969
97500
94980
77801
94790
92844
97612
100578

II

I0
11
12
13
14
15
16
17

HKM

MIP

99142
93778
100292
92977
97055
88863
100190
99433
94258
92597
1 0 3 0 8 8 98340
1 0 1 9 5 7 99336
81054
75280

from the present HKM heuristic discussed earlier. The figures in Table 2 do not represent a particular monetary unit
but point at the relative cost savings from 0.8% to 10.1%
with an average improvement of approximately 5%.

7 Limitations and extensions
As stated in the model introduction, we have done some
simplifications on the real-world situation. The most obvious one is the calculation of a single train only. If all necessary data is available for an enlarged time horizon, thesimultaneous computation may yield another cost reduction.

Multi train models
The easiest way of simultaneous treatment of t trains is obtained by fixing the number of processes for each train. In
this case, one can easily add another index for the train number to the z-, w- and s-variables. Additional constraints areneeded: For example, a car can only be integrated into one
train.
It is even more desirable to let the model determine an
assignment for processes to trains. This can also be handled
by using more variables (see [6]).
The great advantage of a multi train model is the consideration of the global planning situation. The single trainmodel is "greedy": It will always search for the cheapest
solution for one train without regarding that a slighty more
expensive solution will lead to a large cost saving for the
next train.
One main reason (besides increased solution times) for
disregarding multi train models in practice is the highly unpredictable planning situation in the steelworks. Because of
the complex structure of steel production, there are often disturbances which lead to massive changes in the production
schedule and completely destroy the quality of a solution
corresponding to a long planning period.
The "single train" model presented in this paper obeys
the on-line characteristic of the present situtation, because
the dispatcher can initiate the computation just before ordering a train from the scrap yard. Changes in the production
schedule afterwards cannot be taken into account by manual
orders either.

Some additional features can easily be added to the MIP
model. Different cooling effects can be taken into accountby introducing particular coefficients in the cooling effectconstraints. Transport costs for using cars and tracks canalso be considered. Other linear constraints such as scrap
volume can be taken into account.
Another idea is the extension of the optimization to otherproblems related to the scrap problem. This may involve themovements of cranes that take the scrap from the cars to thetransport containers [2] or even the action of assembling thetrain itself on the scrap yard.

Using the model for simulations
Moreover, the MIP model will be useful as a simulation
tool. Simply by changing coefficients one may examine theeffects of small changes in prices, scrap classes, tramp element restrictions . . . .
Another idea is to change the restrictions for the maximum track number. It is possible that essentially better solutions are generated if four or more tracks can be used for
one train, even at higher transport costs.

8 From theory to practice
H K M intend the developed software to be installed in theirown computer system. The main part of the present HKM
scrap information system runs on a process computer underan operating system called MAX32. For reasons of availability of the CPLEX solver, our software OSCAR will be
implemented on a separate UNIX system. The process computer must send the data of the scrap yard and of the processes to the UNIX machine, which, in turn, provides the
optimization results for further use in the scrap information
system on the process computer. Since the size of the data isquite small no loss of performance is expected with respect
to communication delays between the two machines.
It is worth mentioning that not only technical and implementational issues are of interest when regarding the personnel' s acceptance of new technologies. As we know fromexperience, "black box" methods, such as the use of a mixed
integer program, are likely to be disregarded when they are
not properly introduced to the operating personnel. Nonobvious changes in the structure of solutions have to be carefully explained and made comprehensible. It is even more
important to see that a mathematician's idealistic view ofthe world has to be complemented with practitioner's experience. In every day operation, data often are just an estimate
and consequently not always that complete and consistent
as we assumed in this paper. By establishing a certain error tolerance one has to ensure that our program always
delivers a solution even if mathematically no feasible one
exists. Closely related is the fact that small changes in the
input data may often lead to completely different, and thus
unstable and confusing solutions. Consequently, the conflict
between optimality and robustness of solutions should rather
be decided in favour of reliability, and implemented in the258
system accordingly. Besides that, the computer results haveto be regarded as a proposal only, so that the planner may
resort to alternative dispatching at any time. This is not only
important for psychological reasons, but also imperative insituations that require immediate or exceptional decisions, as
they sometimes arise in a real time setting. Moreover, it isadvisable to maintain some degree of freedom in the choiceof certain parameters, in our case the maximal number ofcars per train, prices for scrap, or relative amounts of tramp
elements, just to mention a few. This flexibility, often referred to as "what-if analysis", enables dispatchers as wellas H K M ' s management to simulate altered operations, thus
possibly identifying further economization potential.
Clearly, the implementation of reliability and stability
will reduce the savings of about five per cent, calculated forour pure model. Nevertheless, the mathematical optimization methods will lead to remarkable savings with feasible
solutions, an aspect which is ignored by the current strategy.

K.-P. Bernatzki et al.: Optimal scrap combinationfor steel production

References
1. CPLEX Optimization(1996) Using the CPLEX CallableLibrary
2. Heinrichs U, Moll C (1997) On the schedulingof one-dimensionaltransport systems. Technical Report No. 97-277, Center for Parallel
Computing, Universityof Cologne
3. Hoffman KL, Padberg M (1991) LP-based combinatorialproblem
solving. Annals of Operations Research 4:145-194
4. JohnsonEL, KostrevaMM, Suhl UH (1985) Solving0-1 integerprogramming problems arising from large scale planning models. Operations Research 33:803-819
5. Juenger M, Reinelt G (1992) Schnittebenenverfahrenin der kombintorischen Optimierung,Mitt Ges Angew Math Mech 15(2): 120-134
6. Lindner T (1997) KostenoptimaleSchrottzusammenstellungbei den
Hiittenwerken Krupp Mannesmann. Master's Thesis. TU Braunschweig
7. MehlhornK, N~iherS, Uhrig C (1997) The LEDA User Manual
8. NemhauserGL, Wolsey LA (1988) Integer and CombinatorialOptimization. Wiley, New York9. SavelsberghMWP (1994) Preprocessing and probing techniques formixed integer programmingproblems. ORSA J Comput 6 (4): 445454