Towards a benchmark for configuration and planning optimization problems  Luis Garcés Monge1, Paul Pitiot1,2, Michel Aldanondo1, Elise Vareilles1 1 University Toulouse – Mines Albi, France 2 3IL-CCI Rodez, France Abstract. Computer science community is always interested various industrial cases: automotive [Amilhastre et al., in « benchmarks », e.g. standard problems, by which per- 2002], [Kaiser et al., 2003], [Sinz et al., 2003], power sup- formance of optimization approaches can be measured and ply [Jensen, 2005], train design [Han and Lee, 2011], etc. A characterized. This article aims at present our research per- data-base of industrials cases was started on [Subbarayan, spectives to achieve a benchmark for concurrent configura- 2006] but it is not any more maintained. tion and planning optimization problems. A benchmark is a set of reference models that represents a particular kind of problem. Product configuration and project planning are Our previous research projects [Pitiot et al., 2013] aim at classic problems abundantly handled in the literature. Their producing decision aiding tools for a specific problem sub- coupling in an integrated model is a more and more handled ject to a growing interest in mass customization communi- complex problem; but there is a lack of benchmark in spite ty: the coupling between product and project environments. of the need expressed by the community during last configu- Numerous authors [Baxter, D. et al., 2007] [Zhang et al. ration workshops [config, 2013/2014]]. Two approaches 2013] [Hong et al., 2010] or [Li et al., 2006], [Huang and may be combined to obtain a benchmark: (i) generalization of existing real applications (for example, automotive, tele- Gu, 2006] showed the interest to take into account simulta- communication or computer industry), (ii) or using a struc- neously the product and project dimensions in a decision tural analysis of theoretical model of the problem. In this aiding tool. This concurrent process has two main interests: article, we propose a meta-model of concurrent configura- i) Allowing to model, and thus to take into account, interac- tion and planning problem using these two approaches. It tions between product and project (for example, a specific shall allow us to supply a representative and complete product configuration forbids using certain resources for benchmark, in order to accurately estimate the contribution project tasks), ii) Avoid the traditional sequence: configure of existing optimization methods. product then plan its production which is the source of multiple iterations when selected product can’t be obtained 1 Introduction in satisfying conditions (mainly in terms of cost and cycle time). Benchmarking of optimization approaches is crucial to In spite of the growing interest of the community and in- assess performance quantitatively and to understand their dustrialists, there is no standard (benchmark) for this con- weaknesses and strengths. There are numerous academic current problem. benchmarks associate with various classes of optimization problem (linear / nonlinear problems, constrained problems, In this article, we propose a meta-model of the whole prob- integer or mixed integer programming, etc.). Studies, reports lem (configuration, planning and coupling) which will be and websites of [Shcherbina, 2009] [Domes et al., 2014] used for a theoretical investigation. We also propose to [Mittelmann , 2009] [Gilbert and Jonsson, 2009] are particu- generate representative instances of the problem. By repre- larly accomplished examples of existing optimization sentative, we mean both: benchmark with a multitude of articles and algorithms - Representative of the diversity that could be obtained by benchmarked on great variety of test functions (see for ex- theoretical investigation of the meta-model ample [Shcherbina et al., 2003], [Pál et al., 2012] or [Auger - Representative of the diversity of industrial existing and Ros, 2009]). cases (models and decision aiding process); especially for the configuration part due to its diversity. More than an academic tool, a benchmark should also be representative of real-world problems. For a specific do- Therefore, the paper is organized as follow. The next sec- main, a benchmark represents a reference which should be tion details the problem and its combinatorial aspect. The used by company’s decision-makers to select an approach or third section proposes first elements relevant to a meta- an algorithm. But it is not always easy for them to know of model of the benchmark tool. Some elements associated which theoretical cases cover their practical cases. Bench- mark on configuration field could illustrate this aspect with with cases diversity are discussed. 61 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors Proceedings of the 17th International Configuration Workshop September 10-11, 2015, Vienna, Austria 2 Addressed problem uct or project environment). We assume that those decision variables are all discrete variables, so that an instantiation of For our benchmark, the addressed problem is limited to the all these decisions variables corresponds to a particular coupling between product configuration and project plan- product / project. Indeed in reality and regardless of the ning. We will describe both environments and the coupling environment, decisions correspond to choices between vari- of them in next sub-sections. ous combinations. In product environment, decisions corre- spond to architectural choices between various combina- 2.1 Concurrent configuration and planning tions of sub-systems, or to a choice among various variants for every sub-system. In project environment, decisions Product configuration problem is a multi-domain, multidis- correspond to resources choices between various variants. ciplinary, multiobjective problem [Viswanathan and Linsey, Combinatorial constrained optimization problems consist in 2014], [Tumer and Lewis, 2014]. That generates a wide a search of a combination of all decision variables that re- diversity of possible models to represent. We will try to spects constraints of the problem [Mezura-Montes and define a classification of existing product models and mod- Coello Coello, 2011]. Instantiation of every decision varia- elize it in the proposed meta-model. Planning problems are ble in CSP model corresponds to a specific product/project generally more framed (e.g. temporal precedence, resources which could be analyzed and scored according user’s multi- consumption, cycle time or delay, etc.). To generate various ple preferences or objectives (cost, delay, etc.). As those problem instances we can act on the shape of the project objectives could be antagonist, algorithm has to find in a graph and on the dispersal of the values assigned for the short time a set of approximately efficient solutions that will resources of tasks (cost, cycle time, etc.). Thus, we need to allow the decision maker to choose a good compromise define in our meta-model of the product / project a kind of solution. Using Pareto dominance concept, the optimal set generic model for each part and for the coupling. The aim of of solutions searched is called the optimal Pareto front. the next step of our study will be to analyze industrial cases This allows us to define a multiobjective combinatorial and to define this generic model. constrained optimization problem: a search between various combinations to find a selection of solutions which are the Many authors, since [Mittal and Frayman, 1989], [Soininen closest possible of the optimal Pareto front. et al., 1998], [Aldanondo et al., 2008] or [Hofstedt and Schneeweiss, 2011] have defined configuration as the task of deriving the definition of a specific or customized prod- 3 Meta-model description uct (through a set of properties, sub-assemblies or bill of materials, etc…) from a generic product or a product family, This part aims at present the first elements relevant to a while taking into account specific customer requirements. meta-model of a concurrent configuration and planning Some authors, like [Schierholt 2001], [Bartak et al., 2010] problem which will be used to generate data on benchmark. or [Zhang et al. 2013] have shown that the same kind of reasoning process can be considered for production process 3.1 Constrained optimization problem planning. They therefore consider that deriving a specific production plan (operations, resources to be used, etc...) The constrained optimization problem (O-CSP) is defined by the quadruplet where V is the set of deci- from some kind of generic process plan while respecting sion variables, D the set of domains linked to the variables product characteristics and customer requirements, can of V, C the set of constraints on variables of V and f the define production planning. More and more studies tackle multi-valued fitness function. The set V gathers: the product the coupling of both environment [Baxter, D. et al., 2007] variables and the process variables (we assume that duration [Zhang et al. 2013] [Hong et al., 2010] or [Li et al., process variables are deduced from product and resource). 2006], [Huang and Gu, 2006]. Many configuration and In our meta-model, we define two kind of variable: descrip- planning studies (see for example [Junker, 2006] or [La- tion variables and decision variables. The first ones could be borie, 2003]) have shown that each problem could be suc- discrete or continuous and allow description of the problem cessfully considered as a constraint satisfaction problem in each environment. On other hand, the decision variables (CSP). CSP’s are also widely used by industrials [Kaiser et are all discrete, that thus define the combinatorial optimiza- al., 2000]. Considering that using a CSP representation, we tion problem to solve. Those variables, linked by various could both represent constrained and unconstrained prob- constraints, describe product and project. In product side, lems, we will use it to represent each environment and the we consider that a generic product can be described by a set of properties or a set of components or a mix of both as coupling. proposed in [Aldanondo et al., 2008]. Product description variables can be associated with product properties or com- 2.2 Combinatorial optimization problem ponent type. The definition domains of these variables are either symbols (for example: type of finish…) or discrete In previous concurrent model, some variables represent numbers (for example: flight range…). The configuration decisions of the user (customer or decision-maker on prod- constraints that link these variables show the allowed com- Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 62 Proceedings of the 17th International Configuration Workshop September 10-11, 2015, Vienna, Austria binations of variable values. On figure 1, we represent vari- a subset of continuous or discrete variables connected by ous groups of variables. It illustrates both the fact that a constraints. To generate various models, we can act on the system is composed of multiple sub-systems, and also that number of variables, on theirs domains or on their relations the system and its components are analyzed according to (constraints). Every variable possesses a domain gathering several points of view from various disciplines. Finally, the set of the values or the possible intervals for this varia- each description variable can have an influence on the prod- ble. Combinatorial problems stem from cartesian product of uct cost and can be therefore associated with a cost variable every domain of decision variables. A first variation would defined on a real domain. be obviously the number of variables and the average num- ber of states by variable. For a given complexity, we could also evaluate impact of a few number of variables with large domains or the opposite. We can also generate diversity by acting on constraints: constraints density, number and kind of constraints. These variations will allow generating models more or less diffi- cult to solve, especially because they define the ratio be- tween feasible and unfeasible solutions and thus the difficul- ty of the search. Finally, we can act on distribution of the values affected to each state for each variable involved in evaluation of objec- tives. For example, it concerns acting on the costs and the performances of components or on the costs and durations of project tasks. This will allow us to act on the density of Figure 1 – Meta-model of the Constrained optimization problem solutions in the search space. On project side, we consider that a generic production pro- 3.3 Problem specific analysis cess can be described with a set of planning operations (supplying, manufacturing, assembling…) linked with ante- 3.3.1 Product environment riority constraints. Each operation is defined with: Product environment is a multi-domain, multidisciplinary • Three operation temporal variables: possible starting and thus multiobjective context. In meta-model, product time, possible finish time, possible duration, defined on a configuration model corresponds to a description of relation real domain, between architectural or components choices represented by • Two operation resource variables: required resource, decision variables. Each domain or discipline describes its defined on a symbolic domain, quantity of resource, defined own point of view of the product and its decomposition on integer domain. using constraints. Their analysis could take into account Planning constraints link temporal variables in order to some context description variables. The result is a frag- represent temporal precedence. Resources description varia- mented model stemming from the aggregation of these bles can influence the production process cost and thus are analyses all connected with the decision variables. linked to cost variable. For the objective aspect, every configuration model takes The coupling materializes by some coupling constraints that into account cost dimension. Other objective could also link at least one variable of the configuration model with at appear like technical performance, environmental impact, least one variable of the planning model. In terms of objec- etc. For cost aspect, we expect that at least a cost variable is tive variable, the global cost can be defined as the sum of all linked (directly or not) to each component choice. product cost and operation cost variables. The global cycle time corresponds with the earliest possible finishing time of Concerning the distribution of values that allows to calcu- the last operation of the production process. The definition late objective satisfaction, we assume that the model has to of these coupling constraints completes the model and al- be balanced in order: (i) to be an interesting optimization lows the representation in figure 1 of the global constraint problem to solve and (ii) to be representative of real prob- model associating configuration and planning. lems. For the optimization aspect, if an option is systemati- 3.2 Structural analysis cally better than others, the optimization problem will not be very hard to solve. Furthermore, it corresponds to a better To be able to generate various problems, we analyze the description of the reality where that kind of option will not meta-model structure, e.g. relations between variables. It is be conserved in the catalog. necessary to describe the types of relations ("pattern") exist- ing between variables in every environment (product / pro- Relations between variables and distribution of values are ject / coupling). Each of these environments corresponds to generally consistent at elemental level, e.g. considering and 63 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors Proceedings of the 17th International Configuration Workshop September 10-11, 2015, Vienna, Austria analyzing only few variables using a specific point of view. Indeed in realty, option choices are generally coherent; in On this side, decision variable are the resource choices the sense that existence of each option is justified by differ- (make, buy or make by subcontract decision). In this same ences with other options and those differences generally way as in product side, the different options for each re- correspond to an application of some basic relations or be- source choice are going to differ with regard to the objec- haviors. We identify four kind of basic behavior between tives. For example considering cost and duration objective, two variables: a cost and duration could be assigned to each resource - Positively correlated: the increase of the one leads choice, then total cost is obtained by a summation and pro- to the increase of other one. For example, perform- ject cycle time by a constraint propagation on temporal ing components will be more expansive. constraints. - Negatively correlated: the increase of the one leads As in product side, values distribution between various to the decrease of other one. For example, compo- resource choices has to be balanced and consistent in order nents with low environmental impact will be more to represent real problems. We must unsure there is no use- expansive. less or dominant option and value distributions must repre- - Aggregation: values of a variable are summation of sent accumulation of some basic behavior. Here for exam- values of some others variable. For example, global ple, we expect that there is a positive correlation between product cost is summation of every component cost and quantity/quality of resources or a negative correla- costs. tion between duration and quantity/quality of resources. - Compatibility/incompatibility of some combina- Except these particular aspects, project environment can tions of values: some values of different variables contain other description variables and other objectives will be incompatible. connected with decision variables. Effects of a positive or a negative correlation aren’t neces- sarily linear but this study will be limited to linear interac- 4 Conclusion tions. Figure 2 shows possible linear correlations between two variables. Of course, extension dealing with three, four The goal of this paper was to present our research perspec- or five variables will be considerate as for example flight tives for a benchmark on concurrent configuration and plan- range, flying speed, seat capacity and cost. ning. This problem is more and more studied. Although there are a lot of cases of Knowledge-based configuration systems applied on the industrial practice and project plan- ning, there is a real lack of real-word inspired benchmark. In this study, we propose the first elements of a meta-model that can represent this diversity and that will allow to gener- ate various test models for our benchmark goal. References [Auger and Ros, 2009] Anne Auger and Raymond Ros. Figure 2 – Negative (a) and positive (b) correlations with three Benchmarking the pure random search on the BBOB- possible case: (1) reducer, (2) linear, (3) amplifier. 2009 testbed. In Franz Rothlauf, editor, GECCO, pp. 2479–2484. ACM, (2009) It is the accumulation of a large number of simple and [Aldanondo et al., 2008] M. Aldanondo, E. Vareilles. Con- sometimes conflicting elementary behaviors that gives its figuration for mass customization: how to extend prod- complexity to the problem. Furthermore, real problems also uct configuration towards requirements and process con- show some additional singularities on elementary level (for figuration, Journal of Intelligent Manufacturing, vol. 19 example, a high performing solution for a component) or at n° 5, pp. 521-535A (2008) system level (for example, the choice of a standard configu- ration, e.g. a selection of standard components, could lead to [Amilhastre et al, 2002] J. Amilhastre, H. Fargier, P. Mar- an important discount). quis, Consistency restoration and explanations in dynam- ic csps - application to configuration, in: Artificial Intel- 3.3.2 Project environment ligence vol.135, pp. 199-234, (2002) On project side, meta-model is more framed on its diversity: [Bartak et al., 2010] R. Barták, M. Salido, F. Rossi. Con- - project is a set of task to achieve, straint satisfaction techniques in planning and schedul- - tasks are linked by chronological and precedence ing, in: Journal of Intelligent Manufacturing, vol. 21, constraints, n°1, pp. 5-15 (2010) - tasks are described by some temporal description [Baxter, D., 2007] Baxter, D. An engineering design variable (duration, beginning, end) and some vari- knowledge reuse methodology using process modelling. ables that represent resource choices. Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors 64 Proceedings of the 17th International Configuration Workshop September 10-11, 2015, Vienna, Austria Research in Engineering Design, 18 (1) pp. 37-48, [Mittal and Frayman, 1989] S. Mittal, F. Frayman. Towards (2007) a generic model of configuration tasks, proc of IJCAI, p. [Domes et al., 2014] F. Domes, M. Fuchs, H. Schichl and 1395-1401(1989) A. Neumaier. The Optimization Test Environment, Op- [Mittelmann , 2009] H. Mittelmann, Benchmarks, timization and Engineering, vol. 15, pp. 443–468, (2014) http://plato.asu.edu/sub/benchm.html, 2009. [Gilbert and Jonsson, 2009] J.C. Gilbert and X. Jonsson. [Pàl et al., 2012] László Pál, Tibor Csendes, Mihály Csaba LIBOPT - An environment for testing solvers on hetero- Markót, and Arnold Neumaier Black Box Optimization geneous collections of problems - The manual, version Benchmarking of the GLOBAL Method, , Evolutionary 2.1. Technical Report RT-331, INRIA, (2009) Computation, Vol. 20, No. 4 , pp. 609-639, (2012) [config, 2013/2014] workshops on configuration : 2013 : [Pitiot et al., 2013] P. Pitiot, M. Aldanondo, E. Vareilles, P. http://ws-config-2013.mines-albi.fr/, 2014 : Gaborit, M. Djefel, S. Carbonnel, Concurrent product http://confws.ist.tugraz.at/ConfigurationWorkshop2014/ configuration and process planning, towards an approach [Han and Lee, 2011] S.Han , J. Lee. Knowledge-based combining interactivity and optimality, in: I.J. of Pro- configuration design of a train bogie. Journal of Mechan- duction Research Vol. 51 n°2, 2013 , pp. 524-541. ical Science and Technology. Volume 24, Issue 12, pp [Schierholt 2001] K. Schierholt. Process configuration: 2503-2510, (2011) combining the principles of product configuration and [Hofstedt and Schneeweiss, 2011]. P. Hofstedt, D. Schnee- process planning AI EDAM / Volume 15 / Issue 05 / no- weiss. FdConfig: A Constraint-Based Interactive Product vembre 2001 , pp 411-424 Configurator. 19th International Conference on Applica- [Shcherbina, 2009] O. Shcherbina, COCONUT benchmark, tions of Declarative Programming and Knowledge Man- http://www.mat.univie.ac.at/~neum/glopt/coconut/Bench agement, (2011) mark/Benchmark.html, 2009. [Huang and Gu, 2006] Huang, H.-Z. and Gu, Y.-K., Devel- [Shcherbina et al., 2003] O. Shcherbina, A. Neumaier, Dja- opment mode based on integration of product models mila Sam-Haroud, Xuan-Ha Vu and Tuan-Viet Nguyen, and process models. Concurrent Engineering: Research Benchmarking global optimization and constraint satis- and Applications. 14, 1. 27-34, (2006) faction codes, pp.211--222 in: Ch. Bliek, Ch. Jermann [Hong et al., 2010] G. Hong, D. Xue, Y. Tu,, Rapid identifi- and A. Neumaier (eds.), Global Optimization and Con- cation of the optimal product configuration and its pa- straint Satisfaction, Springer, Berlin 2003. rameters based on customer-centric product modeling [Sinz et al., 2003] Sinz, C., Kaiser, A., Küchlin, W.: Formal for one-of-a-kind production, in: Computers in Industry methods for the validation of automotive product con- Vol.61 n°3, pp. 270–279, (2010) figuration data. Artificial Intelligence for Engineering [Jensen, 2005] Jensen, R., Lars, S.: Power Supply Restora- Design, Analysis and Manufacturing 17, 2003, pp.75-97. tion, Master's thesis, IT University of Copenhagen, [Soininen et al., 1998] T. Soininen, J. Tiihonen, T. Männis- (2005) tö, and R. Sulonen, Towards a General Ontology of Con- [Junker, 2006] U. Junker. Handbook of Constraint Pro- figuration., in: Artificial Intelligence for Engineering gramming, Elsevier, chap. 24, Configuration, pp. 835- Design, Analysis and Manufacturing vol 12 n°4, 1998, 875 (2006) pp. 357–372. [Kaiser et al., 2003] A. Kaiser, K. Wolfgang, S. Carsten. [Subbarayan, 2006] Formal methods for the validation of automotive product http://www.itu.dk/research/cla/externals/clib/, 2006. configuration data. Artificial Intelligence for Engineer- [Tumer and Lewis, 2014] I. Tumer and K. Lewis. Design of ing Design, Analysis and Manufacturing, 17(2), April complex engineered systems. Artificial Intelligence for Special Issue on configuration. (2003) Engineering Design, Analysis and Manufacturing, 28, pp [Laborie, 2003] P. Laborie. Algorithms for propagating 307-309. 2014. resource constraints in AI planning and scheduling: Ex- [Viswanathan and Linsey, 2014] Vimal Viswanathan and isting approaches and new results, in: Artificial Intelli- Julie Linsey, Spanning the complexity chasm: A re- gence vol 143, 2003, pp 151-188. search approach to move from simple to complex engi- [Li et al., 2006] L. Li, L. Chen, Z. Huang, Y. Zhong, Prod- neering systems. AI EDAM 28(4): pp. 369-384, 2014. uct configuration optimization using a multiobjective [Kaiser et al., 2000] A. Kaiser, K. Wolfgang, S. Carsten. GA, in: I.J. of Adv. Manufacturing Technology vol. 30, Proving consistency assertions for automotive product 2006, pp. 20-29. data management. J. Automated Reasoning, 24(1- [Mezura-Montes and Coello Coello 2011] E. Mezura- 2):145-163, February 2000. Montes, C. Coello Coello, Constraint-Handling in Na- [Zhang et al., 2013] L. Zhang, E. Vareilles, M. Aldanondo. ture-Inspired Numerical Optimization: Past, Present and Generic bill of functions, materials, and operations for Future, in: Swarm and Evolutionary Computation, Vol. 1 SAP2 configuration, in: I.J. of Production Research Vol. n°4, 2011, pp. 173-194 51 n°2, pp. 465-478, (2013). 65 Juha Tiihonen, Andreas Falkner and Tomas Axling, Editors Proceedings of the 17th International Configuration Workshop September 10-11, 2015, Vienna, Austria