=Paper=
{{Paper
|id=Vol-1623/paperco9
|storemode=property
|title=Discrete Optimization Models for Solving Complex Products Design Problems
|pdfUrl=https://ceur-ws.org/Vol-1623/paperco9.pdf
|volume=Vol-1623
|authors=Alexander Kolokolov, Alexandra Artemova, Alexander Adelshin, Irina Kan
|dblpUrl=https://dblp.org/rec/conf/door/KolokolovAAK16
}}
==Discrete Optimization Models for Solving Complex Products Design Problems==
https://ceur-ws.org/Vol-1623/paperco9.pdf
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)