minlp stefen presentation
TRANSCRIPT
-
8/13/2019 Minlp Stefen presentation
1/13
Optimization of a Nonlinear
Workload Balancing Problem
Stefan Emet
Department of Mathematics and Statistics
University of Turku
Finland
Euro 2012 Vilna 8-11.7
-
8/13/2019 Minlp Stefen presentation
2/13
Outline of the talk
Introduction
Some notes on Mathematical ProgrammingMINLP methods and solversSolution principlesSome advantages and disadvantages
MINLP model for the PCB-problemObjective - Maximizing profit under cyclic operation
Some example problemsSolution results
SummaryConclusions and some comments on future research issues
Euro 2012 Vilna 8-11.7
-
8/13/2019 Minlp Stefen presentation
3/13
Optimization problems are usually classified as follows;
Variables Functions
continuous:
masses,volumes, flowes
prices, costs etc.
discrete:
binary {0, 1}
integer {-2,-1,0,1,2}
discrete values{0.2, 0.4, 0.6}
linear non-linear
non-convex
quasi-convex
pseudo-convex
convex
Classification of optimization problems...
Euro 2012 Vilna 8-11.7
-
8/13/2019 Minlp Stefen presentation
4/13
variables
continuous integer mixed
linear
nonlinear
LP ILP MILP
NLP INLP MINLP
On the classification...
Euro 2012 Vilna 8-11.7
-
8/13/2019 Minlp Stefen presentation
5/13
MINLP-methods..
Branch and Bound MethodsDakin R. J. (1965). Computer Journal, 8, 250-255.
Gupta O. K. and Ravindran A. (1985).Management Science, 31, 1533-1546.
Leyffer S. (2001). Computational Optimization and Applications,18, 295-309.
Cutting Plane MethodsWesterlund T. and Pettersson F. (1995). An Extended Cutting Plane Method for Solving Convex MINLPProblems. Computers Chem. Engng. Sup., 19, 131-136.
Westerlund T., Skrifvars H., Harjunkoski I. and Porn R. (1998). An Extended Cutting Plane Method for
Solving a Class of Non-Convex MINLP Problems. Computers Chem. Engng., 22, 357-365.Westerlund T. and Prn R. (2002). Solving Pseudo-Convex Mixed Integer Optimization Problems byCutting Plane Techniques. Optimization and Engineering, 3,253-280.
Decomposition MethodsGeneralized Benders Decomposition
Geoffrion A. M. (1972).Journal of Optimization Theory and Appl., 10, 237-260.
Outer Approximation
Duran M. A. and Grossmann I. E. (1986).Mathematical Programming, 36, 307-339.
Viswanathan J. and Grossmann I. E. (1990). Computers Chem. Engng, 14, 769-782.
Generalized Outer Approximation
Yuan X., Piboulenau L. and Domenech S. (1989). Chem. Eng. Process, 25, 99-116.
Linear Outer Approximation
Fletcher R. and Leyffer S. (1994).Mathematical Programming, 66, 327-349.
Euro 2012 Vilna 8-11.7
-
8/13/2019 Minlp Stefen presentation
6/13
NLP-subproblems:
+ relative fast convergengeif each node can be solvedfast.
- dependent of the NLPs
MINLP-methods (solvers)...
Branch&Bound
minlpbb, GAMS/SBB
Outer Approximation
DICOPT
ECP
Alpha-ECP
MILP
MILP
NLP
NLPNLP
NLP NLP
NLP
MILP and NLP-subproblems:
+ good approach if the NLPscan be solved fast, and the
problem is convex.
- non-convexities impliessevere troubles
MILP-subproblems:
+ good approach if the
nonlinear functions arecomplex, and e.g. if gradientsare approximated
- might converge slowly ifoptimum is an interior point offeasible domain.
Euro 2012 Vilna 8-11.7
-
8/13/2019 Minlp Stefen presentation
7/13
Workload balancing problem...
Decision variables:
yikm=1, if component i is in machine k feeder m.
zikm= # of comp. i that is assembled from machine k and feeder m.
Feeders:
Euro 2012 Vilna 8-11.7
Placement-head
PCB
-
8/13/2019 Minlp Stefen presentation
8/13
Production balancing problem...
Production lines:
Euro 2012 Vilna 8-11.7
Line 1:
Line 2:
Line n:
-
8/13/2019 Minlp Stefen presentation
9/13
Objective (one production line)..
where is the assembly time of the slowestmachine:
KkzttsM
m
I
i
ikmik ,...,1,..1 1
K
k
kkYc
1max
Euro 2012 Vilna 8-11.7
Optimize the profits during a period :
-
8/13/2019 Minlp Stefen presentation
10/13
constraints...
(slot capacity)km
M
m
ikmik Sys 1
i
K
k
M
m
ikm dz 1 1
(component to place)
(all components set)
0
ikmiikm ydz
Euro 2012 Vilna 8-11.7
-
8/13/2019 Minlp Stefen presentation
11/13
PCB example problems...
Problem characteristics:
Machines 3 3 3 3 6 6 6 6
Components 10 20 40 100 100 140 160 180
Tot. # comp. 404 808 1616 4040 4040 5656 6464 7272
Variables
Binary 90 180 360 900 1800 2520 2880 3240
Integer 90 180 360 900 1800 2520 2880 3240
Constraints
Linear 172 332 652 1612 3424 4784 5464 6144
cpu [sec] 0.11 0.03 3.33 2.72 5.47 6.44 11.47 121.7
Euro 2012 Vilna 8-11.7
-
8/13/2019 Minlp Stefen presentation
12/13
Objective (multiline system)...
where is the assembly time of the slowestmachine:
I
i
ililLl
tz
1,,1
maxmin
Euro 2012 Vilna 8-11.7
Decision variables:
zil = # of products i that are assembled on line l
til = production time of product i on line
-
8/13/2019 Minlp Stefen presentation
13/13
Summary...
Though the results are encouraging there are issues to be tackled and/or
improved in a future research (in order to enable the solving of larger problemsin a finite time);
- refinement of the models
- implementation of convexification strategies
Some references
Emet S. et al. (2010). Workload balancing in printed circuit board assembly line.Int. Journal ofAdv Manufacturing Technology, 50, 1175-1182.
Porn R. et al. (2008). Global Solution of Optimization Problems with Signomial Parts.DiscreteOptimization, 5, 108-120.
Emet S. (2004).A Comparative Study of Solving Some Nonconvex MINLP Problems, Ph.D. Thesis,bo Akademi University.
Euro 2012 Vilna 8-11.7