=Paper=
{{Paper
|id=Vol-1453/10_MongePitiotAldanondoVareilles_TowardsABenchmarkForConfiguration_Confws-15_p61
|storemode=property
|title=Towards a benchmark for configuration and planning optimization problems
|pdfUrl=https://ceur-ws.org/Vol-1453/10_MongePitiotAldanondoVareilles_TowardsABenchmarkForConfiguration_Confws-15_p61.pdf
|volume=Vol-1453
|dblpUrl=https://dblp.org/rec/conf/confws/GarcesPAV15
}}
==Towards a benchmark for configuration and planning optimization problems==
https://ceur-ws.org/Vol-1453/10_MongePitiotAldanondoVareilles_TowardsABenchmarkForConfiguration_Confws-15_p61.pdf
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