Discrete Optimization Models for Solving Complex Products Design Problems Alexander Kolokolov1 , Alexandra Artemova2 , Alexander Adelshin1 ⋆ and Irina Kan3 ⋆⋆ 1 Sobolev Institute of Mathematics, Omsk Branch Pevtsova str. 13, 644043, Omsk, Russia 2 Omsk State Technical University pr. Mira 11, 644050, Omsk, Russia 3 Omsk State Institute of Service Pevtsova str. 13, 644043, Omsk, Russia kolo@ofim.oscsbras.ru, alexxartemova@gmail.com adelshin@ofim.oscsbras.ru, irina.e.kan@gmail.com Abstract. The development and research of discrete optimization models with logical, resource and other constraints to solve complex products design prob- lems are continued in the article. These models are based on the SAT problem and its generalizations. Particular attention is paid to the questions of design of series of products using special sets of components (”kernels”) that have been suggested by the authors and allow to expand the variety of output products in various production branches. The results of computational experiments that reflect the prospects of the approach are presented. Keywords: discrete optimization, integer programming, satisfiability problem, logical constraints, complex products, computer-aided design, consumer goods industry. Introduction In many decision-making problems related to design, planning and management logical, resource and other constraints are used. Logical constraints are often described in the terms of mathematical logic and lead to the maximum satisfiability problem, which is a generalization of the well known satisfiability problem and one of the central problems in the complexity theory. It is known that these problems are NP-hard. The considered problems with the specified constraints can be used to solve many applied problems in various fields. For example, in [1–9] the problem of design of clothes that are formed of a set of components have been studied and solved. In [10] formulations of rubbers for ⋆ This research was supported by the Russian Foundation for Basic Research, grant 16-01- 00740. ⋆⋆ This research was supported by the Foundation for Assistance to Small Innovative Enter- prises in Science and Technology, grant 7789 2/2015 Copyright ⃝ c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Kononov et al. (eds.): DOOR 2016, Vladivostok, Russia, published at http://ceur-ws.org 50 A. Kolokolov, A. Artemova, A. Adelshin, I. Kan special purposes are developed, while [11] is devoted to the problem of the formation of production groups with regard to interpersonal relations. In [12] the problem of logical cryptanalysis is solved. In addition, a large number of applications of the satisfiability problem are given in the review article [13]. Currently, design of complex products has received much attention due to the rel- evance of this direction. Many design problems are solved with the help of different computer systems, for example [14, 15], which are used by an expert for a thorough search and comparison of a large number of combinations of components and elements. This way, in some cases, may not be considered sufficiently interesting and promising variants of solutions, and selected ones are not always optimal. In this regard, it is rational to use the mathematical apparatus, in particular, models and methods of dis- crete optimization, as well as the development of a software package on this basis [2, 4, 5, 8, 9, 16, 17]. In [1–5, 10–12, 16–20] and other papers, mathematical models are applied that are generalizations of the maximum satisfiability problem and include two types of con- straints: ”hard” (that are binding) and ”soft” (that can be violated under certain conditions). The development of the above-mentioned approach and the investigation of the relevant mathematical models are continued in the presented paper. A particular attention is paid to the questions of design of series of products based on the use of the offered in [7] special sets of components (”kernels”) that allow one to expand the variety of output products. There are being studied the possibilities of the use of the afore-mentioned approach to automate outline complex products design (on the exam- ple of some assortment groups characterized by a wide variety of components and filling groups). The structure of the software package under development is described [5, 9]. The results of computational experiments that reflect the prospects of application of the specified structures are also presented. 1 Problems formulation and mathematical models We begin with introducing logical variables x1 , . . . , xn that can take the values true or false. Consider a propositional formula F = C1 ∧ . . . ∧ Cm where each clause Ci is a disjunction of literals, and each literal is either a variable xj (that is, a positive literal) or its negation x̄j (that is, a negative literal). In the SAT problem, a truth assignment for variables is sought that makes the formula true. Denote by y1 , . . . , yn the binary variables such that yj corresponds to xj and 1 − yj corresponds to x̄j , j = 1, . . . , n. Satisfiability of the formula is equivalent to solvability of the following system: ∑ ∑ yj − yj ≥ 1 − |Ci− |, i = 1, . . . , m; (1) j∈Ci+ j∈Ci− 0 ≤ yj ≤ 1, j = 1, . . . , n; (2) yj ∈ Z, j = 1, . . . , n, (3) where Ci− and Ci+ are the index sets of the negative and positive literals in clause Ci , respectively. Discrete Optimization Models for Complex Products Design Problems 51 Suppose that every clause Ci has a nonnegative weight ci . The MAX-SAT is the problem of finding an assignment to the variables that maximizes the weight of the satisfied clauses. Here we provide a formulation of the MAX-SAT problem as an integer linear pro- gramming (ILP) problem: ∑ m y0 = ci zi → max (4) i=1 subject to: (5) ∑ ∑ yj − yj + zi ≤ |Ci− |, i = 1, . . . , m; (6) j∈Ci− j∈Ci+ 0 ≤ yj , zi ≤ 1, j = 1, . . . , n, i = 1, . . . , m; (7) yj , zi ∈ Z, j = 1, . . . , n, i = 1, . . . , m. (8) If zi is equal to one in a feasible solution of problem (4)–(8), then clause Ci is satisfied. The optimal value of the objective function is the total weight of satisfied clauses. In addition, of the practical importance is the problem where a variable assignment is required to satisfy all ”hard” clauses and to maximize the total weight of ”soft” clauses in a boolean formula (a partial MAX-SAT). ∑ m y0 = ci zi → max (9) i=1 subject to: (10) ∑ ∑ yj − yj ≥ 1 − |Ci− |, i = 1, . . . , m; (11) j∈Ci+ j∈Ci− ∑ ∑ yj − yj + zi ≤ |Ci− |, i = 1, . . . , m; (12) j∈Ci− j∈Ci+ 0 ≤ yj , zi ≤ 1, j = 1, . . . , n, i = 1, . . . , m; (13) yj , zi ∈ Z, j = 1, . . . , n, i = 1, . . . , m. (14) On the basis of these models of ILP and the method of regular partition, theoretical research of the problems with logical constraints was conducted. Design and analysis of algorithms of the search of exact and approximate solutions were carried out [18]. The results are used in various applications. Let us consider the setting of the problem of complex products outline design and the relevant mathematical model with the use of the logical, resource and other con- straints. In addition, the partition of elements into the groups of components is taken into account. It can adequately describe the problem situation and can be used for 52 A. Kolokolov, A. Artemova, A. Adelshin, I. Kan the development of algorithms solving the problem [1, 4, 9, 16, 20]. To formulate the problem, we introduce the following notation: J – the set of numbers of components of the product, J = {1, . . . , n}; G – the set of groups of components and characteristics; α – the number of a group of the components and the characteristics, α ∈ G; Jα – the numbers of elements in group α; vjα – the component with number j from group α; xα α j – the logical variable that takes the value true if vj is included in the product and false otherwise; L – the set of numbers of indicators that characterize the degree of the expediency of inclusion of components and characteristics in the product; sα α lj – the weight of component or characteristic vj according to the l-indicator, l ∈ L, j ∈ Jα ; pl – the lower bound for the total weight of the components included in the product according to the l-indicator; I – the set of numbers of the logical formulae used in the problem, I = {1, . . . , m}; I0 – the set of the logical formulae that bind variables from different groups; Ci – the logical formula corresponding to the i-th logical constraint, i ∈ I0 , which is a disjunction of variables xα j and/or their negations. It should be noted that the formulae with numbers from I0′ ⊆ I0 must be satisfied; di – the weight of formula Ci that defines the significance of satisfying this formula, i ∈ I0 \I0′ ; C̃αr – the logical formula corresponding to the r-th logical constraint and bind variables from group α, r ∈ Iα . Equations with numbers from Iα′ ⊆ Iα must be satisfied; dαr – the weight of formula C̃αr that defines the significance of satisfying this formula, r ∈ Iα \Iα′ ; K – the set of the used resources; aαkj – the volume of the k-th resource that is necessary to produce the j-th compo- nent of the product in group α , k ∈ K, j ∈ Jα ; bk – the available volume of the k-th resource, k ∈ K. The problem is to find the values of the logical variables which satisfy the logical formulae Ci with numbers i ∈ I0′ and the logical formulae C̃αr , r ∈ Iα′ , α ∈ G. The resource constraints and the constraint for the total weight of the components included in the product must be satisfied and the total number of the satisfied formulae Ci , i ∈ I0 \I0′ , and the formulae C̃αr , r ∈ Iα \Iα′ , α ∈ G is maximized. Let us assume that the boolean variable yjα takes 1 if a corresponding element is included in the product and it takes 0 otherwise, j ∈ J, α ∈ G. By the analogy of the ILP model for the partial MAX-SAT problem it is possible to build a model of the considered design problem: ∑ ∑ ∑ r zr → max dα α f (z) = di zi + (15) i∈I0 \I0′ ′ α∈G r∈Iα \Iα subject to: Discrete Optimization Models for Complex Products Design Problems 53 (16) ∑( ∑ ∑ ) yjα − yjα ≤ |Ci− | − 1, i ∈ I0′ ; (17) α∈G − + j∈Cαi j∈Cαi ∑( ∑ ∑ ) yjα − yjα + zi ≤ |Ci− |, i ∈ I0 \I0′ ; (18) α∈G − + j∈Cαi j∈Cαi ∑ ∑ − yjα − yjα ≤ |C̃αr | − 1, r ∈ Iα′ , α ∈ G; (19) − + j∈C̃αr j∈C̃αr ∑ ∑ − yjα − yjα + zrα ≤ |C̃αr |, r ∈ Iα \Iα′ , α ∈ G; (20) − + j∈C̃αr j∈C̃αr ∑ ∑ lj yj ≥ pl , l ∈ L; sα α (21) α∈G j∈Jα ∑ ∑ kj yj ≤ bk , k ∈ K; aα α (22) α∈G j∈Jα 0 ≤ yjα ≤ 1, yjα ∈ Z, j ∈ Jα ; (23) 0 ≤ zi ≤ 1, zi ∈ Z, i ∈ I0 \I0′ ; (24) 0 ≤ zrα ≤ 1, r ∈ Iα \Iα′ , α ∈ G. (25) In the objective function (15), the sum of weights of the ”soft” logical constraints is maximized by the relating variables belonging to different groups of components, and variables of individual groups. Inequalities (17) correspond to the ”hard” logical constraints binding the variables among the groups. Inequalities (18) correspond to the ”soft” constraints binding the variables among the groups. Constraints (19) and (20) are similar to constraints (17) and (18) but bind variables within one group. The designers’ preferences for selecting components and their integration into the product are given by system (21). Inequalities (22) are the constraints on the used resources (cost, material consumption, etc.), (23) – (25) are the conditions on the boolean variables. A feasible solution of problem (15) – (25) determines a variant of a product satisfy- ing the above-mentioned conditions. Note that the designer is able to correct the previ- ously formulated constraints. There may be several optimal solutions of this problem, so the specialist can choose some of them, taking into account his or her preferences. One of the effective ways to improve the competitiveness of production is to design not individual products but several models that are connected by a common group of components (”kernel” of series), with the possibility of varying and interchanging other components and elements that is based on the use of models and methods of discrete optimization [5, 7]. Let us consider thoroughly the concept of the ”kernel” of the series. To do this, we divide all the groups of product components into two classes. The first is a group of product components that form the shapes of the product. The second class is a group of details that are designed to create a visual variety of outlines of products. The ”kernels” are generated by certain combinations of components of the first class, interconnected by the unity of constructive solutions. The elements of the second class must be consistent with the ”kernel”, taking into consideration their 54 A. Kolokolov, A. Artemova, A. Adelshin, I. Kan art, design and technological compatibility. This method allows to form clothes and produce them at the same time in one production flow without additional time and resource waste during the process of clothes production. Previously, some ”kernels” to design series of models of the dress-blouse assortment of women’s clothes have been built by the authors. To create them, a number of ”hard” logical constraints that define a fixed set of elements and form the ”kernel” of the series were distinguished. Other ”hard” and ”soft” logical constraints create a variety of models. The corresponding computational experiments have been carried out. Another perspective direction of the development of the approach is the creation of outfits [5, 7, 9], i.e., the sets of clothes that consist of two or more various assort- ment groups interconnected by the unity of style, shape, and the proportional ratio of elements, coherence of articulations, a combination of trimmings and materials, color scheme, etc. 2 On the algorithms and software package development In order to solve relevant design problems earlier, the authors used a variety of software packages, in particular, GAMS. In addition, a variant of a program complex for an automation design of a series and singular items of clothes outline was created. Thus the problem of women’s coats, jackets, products of the dress-blouse assortment group design and also of some technical devices design was solved [2, 4–9, 16, 17, 19, 20]. About 150 variables and more than 100 constraints were used by the example of women’s clothes design based on mathematical model (13)–(22). During the experiments, we varied input data, such as the weights of elements and the significance degree of certain ”soft” logical constraints as well. Various silhouette shapes of products were examined. We also fixed the minimum number of elements that were included in the outline. The calculations confirmed the practical value of the approach. It helps get a wide variety of variants of outlines rapidly, which is useful for the development of models of clothes of different assortment groups that are run into the technological process. Currently, some special algorithms to find exact and approximate solutions of the investigated problems to create series of products based on one ”kernel” are being de- veloped. The algorithms are based on the L-class enumeration that was developed for the MAX-SAT problem in the context of the regular partition method for the anal- ysis and solving integer programming problems [18]. In the case of an approximate solution, the maximum allowed deviation from the optimal solution (according to the objective function value) is taken into account. In addition, the software package is being modernized [5, 9]. The complex will allow the specialist to enter and adjust the source data to create technical sketches, to use mathematical models and algorithms to search for optimal solutions, and realize the interaction with the knowledge bases. The latter include the following information: typical measures and their graphics, compo- nents and characteristics of garments, ready-made technical and artistic sketches, and also logical, resource and other constraints that are necessary to construct mathemat- ical models and apply the algorithms of discrete optimization. The software package is to provide the ability of obtaining and modifying the above-mentioned constraints, Discrete Optimization Models for Complex Products Design Problems 55 the visualization of the project and intermediate results, to prepare reports and print them, to use different color options. In addition to the forward-engineering of clothing, such a software package can provide the analysis of the obtained solutions concidering the values of a number of indicators to assess the quality of the complete outlines, as well as to compare several variants to choose the best of them. 3 Conclusion In the work, the development and research of the integer linear programming models based on the SAT and the MAX-SAT problems for the complex products design, in- cluding consumer goods industry, are continued. The special attention is paid to the creation of series and outfits of complex products using special structures (”kernels”) illustrated by the example of some assortment groups of complex products. The modernization of the software package for the automation of clothes design to extend its functionality is in progress. The computational experiments with real input data are being carried out. References 1. Kolokolov, A. A. Clothes design using some discrete optimization models / A. A. Kolokolov, A. V. Yarosh // Omsk Scientific Gazette, 2002. – Issue 20. – pp. 91 – 94. (in Russian) 2. Guseletova, O. N. Discrete optimization with logical constraints for design of complex products / O. N. Guseletova, A. A. Kolokolov // Automation and Remote Control, 2008. – Vol. 69. – Issue 10. – pp. 1808 – 1813. (DOI: 10.1134/S0005117908100147) 3. Kolokolov, A. A. Development and analysis of models for discrete optimization for a single class of complex products design / A. A. Kolokolov, T. M. Orlova // Omsk Scientific Gazette, 2012. – No. 2(110). – pp. 22 – 24. (in Russian) 4. Artemova, A. V. Solving optimization problems in the development of computer technol- ogy : studies guide / A. V. Artemova, A. A. Kolokolov, V. I. Potapov. – Omsk: OmSTU Press, 2012. – 88 p. (in Russian) 5. Artemova, A. V. Application of methods of discrete optimization for the design of some classes of complex products in terms of colour / A. V. Artemova, I. E. Kan // Proceedings of the X-th Asian school-seminar ”Problems of complex systems optimization”. – Almaty: NC NTI, 2014. – pp. 65 – 68. (in Russian) 6. Kan, I. E. About one approach for the automation of the clothes design process using discrete optimization / I. E. Kan, A. V. Artemova // Russia-Korea Conference on Science and Technology: Abstracts. – Novosibirsk: NSTU Press, 2013. – pp. 22 – 25. 7. Yarosh, A. V. Solution of problems of series and sets of clothes formation based on discrete optimization / A. V. Yarosh, L. V. Larkina // Application of optimization methods: Proceedings of the XIV Baikal international school-seminar ”Optimization methods and their applications”: Irkutsk, ESI SB RAS, 2008. – Vol. 4 – pp. 230 – 237. (in Russian) 8. Kolokolov, A. A. Computer-Aided Design of Some Assortment Groups of Complex Prod- ucts Using Discrete Optimization / A. A. Kolokolov, A. V. Artemova, I. E. Kan // Dy- namics of Systems, Mechanisms and Machines (Dynamics), 2014. – pp. 1 – 5. ( DOI: 10.1109/Dynamics.2014.7005667) 56 A. Kolokolov, A. Artemova, A. Adelshin, I. Kan 9. Artemova, A. V. On solving some problems of automation of complex products design in consumer goods industry / A. V. Artemova, I. E. Kan // Mathematical programming and its applications: Abstracts of Russian conference Yekaterinburg: UrB of RAS , 2015. – pp. 69. (in Russian) 10. Adelshin, A. V. Application of the SAT problems of logical formulas for the chemical composition of rubber compounds design / A. V. Adelshin, E. N. Zhovner // Herald of Omsk University, 2011. – No. 2. – pp. 14 – 18. (in Russian) 11. Kolokolov, A. A. Decision of tasks of small groups forming with regard for interpersonal relations / A. A. Kolokolov, Y. S. Serysheva, L. D. Shulepova // Proceedings of the XV-th Baikal international school-seminar ”Optimization Methods and their applications”, 2011. – Vol. 5. – pp. 61 – 66. (in Russian) 12. Posypkin, M. A. Decision of the problem of cryptanalysis of sequence cipher in distributed area networks / M. A. Posypkin, O. S. Zaikin, D. V. Bespalov, A. A. Semenov // Pro- ceedings of ISA, 2009. – Vol. 46. – pp. 119 – 137. (in Russian) 13. Gu J. Algorithms for the Satisfiability (SAT) Problem: A Survey / J. Gu, P. Purdom, J. Franco, B. Wah // DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1996. – 131 p. 14. Sano, T. Computer aided design system for Japanese kimono / T. Sano, H. Yamamoto // Instrumentation and Measurement Technology Conference. IMTC 2001. Proceedings of the 18th IEEE, 2001. – Vol.1. – pp. 326 – 331. (DOI: 10.1109/IMTC.2001.928834) 15. Suresh, M. N. Development of total material design system of woven fabrics foe apparel use / M. N. Suresh, T. Matsuto // International Journal of Clothing Science and Technology. – No. 12 (6). – pp. 47 – 49. 16. Kolokolov, A. A. Mathematical models and software complex for outline clothes design / A. A. Kolokolov, Z. E. Nagornaya, O. N. Guseletova, A. V. Yarosch // Journal of Applied mathematics and information technologies: Collection of scientific and method. works. – Omsk: OmSTU Press, 2005. – pp. 80 – 98. (in Russian) 17. Kolokolov, A. A. Computer-aided design systems in service : study guide. Part 1 / A. A. Kolokolov, Z. E. Nagornaya, A. V. Yarosh. – Omsk: OSIS, 2006. – 113 p. (in Russian) 18. Kolokolov, A. A. Analysis and solving SAT and MAX-SAT problems using an L-partition approach / A. A. Kolokolov, A. V. Adelshin, D. I. Yagofarova // Journal of Mathematical Modeling and Algorithms, Spinger, 2013. – Vol. 12. – No. 2. – pp. 201 – 212. 19. Kolokolov, A. A. On solving some complex design problems using discrete optimization models / A. A. Kolokolov, A. V. Yarosh // Operation Research 2003, Annual International Conference of the German Operation Research Society (GOR). Heidelberg, Germany : University of Heidelberg, 2003. – pp. 136. 20. Kolokolov, A. A. Computer aided design of complex products using discrete optimization and information technology / A. A. Kolokolov, A. V. Yarosh // Omsk Scientific Gazette, 2010. – No. 2(90). – pp. 234 – 238. (in Russian)