=Paper=
{{Paper
|id=Vol-2098/paper1
|storemode=property
|title=Design of Complex Products with Regard to
Coloristics Based on Discrete Optimization
Problems
|pdfUrl=https://ceur-ws.org/Vol-2098/paper1.pdf
|volume=Vol-2098
|authors=Alexander Adelshin,Alexandra Artemova,Irina Kan,Zhulduz Suleimenova
}}
==Design of Complex Products with Regard to
Coloristics Based on Discrete Optimization
Problems==
https://ceur-ws.org/Vol-2098/paper1.pdf
Design of Complex Products with Regard to
Coloristics Based on Discrete Optimization
Problems ?
Alexander Adelshin1 , Alexandra Artemova2 , Irina Kan3 , and Zhulduz
Suleimenova4
1
Sobolev Institute of Mathematics, Omsk Branch, Omsk, Russia
adelshin@mail.ru
2
Omsk State Technical University, Omsk, Russia
alexartemova@gmail.com
3
Multidisciplinary Academy of Continuing Education, Omsk, Russia
irina.e.kan@gmail.com
4
Dostoevsky Omsk State University, Omsk, Russia
suleimenova.zhulduz@mail.ru
Abstract. In this work, development and study of models of discrete
optimization with logical, resource and other constraints to solve the
problems of design of complex products are continued. Special attention
is paid to the questions of selection of coloristic solutions in the process
of complex products design. It allows improving visual variety for con-
sumers without significant production costs. A mathematical model for
the distribution of colors to the details of complex products based on
the theory of color and the satisfiability problem is proposed. The re-
sults of computational experiments which reflect the prospects of further
development of the considered approach are presented.
Keywords: Discrete optimization · Mathematical models · Logical con-
strains · Complex products · Outline design · Coloristics
1 Introduction
In many decision-making problems, related to design, planning and management,
logical, resource and other constraints are used. Logical and resource constraints
can lead to the partial maximum satisfiability problem. This problem is a gen-
eralization of the well known satisfiability problem (SAT), that is one of the
central problems in the complexity theory. It is known that these problems are
?
This research was supported by the Russian Foundation for Basic Research, grant
16-01-00740.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: S. Belim et al. (eds.): OPTA-SCL 2018, Omsk, Russia, published at http://ceur-ws.org
Discrete Optimization Models for Complex Products Design Problems 7
NP-hard. The considered problems with the specified constraints can be used to
solve a variety of applied problems in many fields. For example, studying and
solution of the problem of outline design of clothes that are formed of a set of
components [3, 4, 6, 12], design of some technical devices, formulations of rubbers
for special purposes [2], the problem of the formation of production groups with
regard to interpersonal relations [11], the problem of logical cryptanalysis [14]
and others.
Currently, design of complex products has received much attention due to the
relevance of this direction. The majority of the problems are solved on the base
of different computer systems, for example [15]. However, in most cases these
systems do not make much use of the capabilities of the mathematical apparatus.
To solve these problems, it is rational to use in particular models and methods
of discrete optimization, as well as the development of special algorithms.
In the paper, the development of the described in [3, 4, 10, 12] approach and
study of corresponding mathematical models are being continued. The possibil-
ities of the use of the mentioned approach to automation of outline design of
complex objects, on the example of some assortment groups of the consumer
goods industry, are studied. These groups are distinguished by a great variety
and filling. Much attention is paid to the questions of the design of complex
products with due regard to coloristic solutions which allow broading the va-
riety of the produced products. During manual design, an expert must search
through and compare a large number of variants of color combinations for com-
ponents and elements. This way, in some cases, not all prospective and interesting
variants can be considered, and selected ones are not always optimal. The use
of mathematical apparatus and partial automation of the creative process can
give the specialist opportunities to meet various demands (economical, resource
conditions, the theory of coloristics, fashion trends, etc.) in the optimum way.
Therefore, the development of the research in this direction is actual and greatly
requested.
2 Problems Formulation and Mathematical Models
We begin with introducing logical variables x1 , . . . , xn that can take the values
true or false. Consider the 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.
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.
In addition, the practical importance is the problem where a variable assign-
ment is required to satisfy all ”hard” clauses and to maximize the total weight
of ”soft” clauses in a boolean formula (a partial MAX-SAT).
8 A. Adelshin et al.
There are models of integer linear programming based on the SAT and the
MAX SAT problem. On the basis of these models and the method of regular
partition, theoretical research of the problems with logical constraints was con-
ducted [1, 8, 9]. Design and analysis of algorithms of the search of exact and
approximate solutions were carried out. The results are used in various applica-
tions.
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 constraints. In addition, the partition of elements into the groups of com-
ponents is taken into account. It can adequately describe the problem situation
and can be used for the development of algorithms solving the problem [10, 12].
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 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;
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 I00 ⊆ I0 must be satisfied;
di – the weight of formula Ci that defines the significance of satisfying this
formula, i ∈ I0 \I00 ;
C̃αr – the logical formula corresponding to the r-th logical constraint and
bind variables from group α, r ∈ Iα . Equations with numbers from Iα0 ⊆ Iα
must be satisfied;
dαr – the weight of formula C̃αr that defines the significance of satisfying this
formula, r ∈ Iα \Iα0 ;
The problem is to find the values of the logical variables which satisfy logical
formulae Ci with numbers i ∈ I00 and logical formulae C̃αr , r ∈ Iα0 , α ∈ G.
The total number of the satisfied formulae Ci , i ∈ I0 \I00 , and formulae C̃αr ,
r ∈ Iα \Iα0 , α ∈ G is maximized.
Let us assume that the boolean variable yjα takes 1 if a corresponding element
is included in the product (xα j = true) 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:
X X X
f (z) = di zi + dα α
r zr → max (1)
i∈I0 \I00 0
α∈G r∈Iα \Iα
Discrete Optimization Models for Complex Products Design Problems 9
X X X
yjα − yjα ≤ |Ci− | − 1, i ∈ I00 ; (2)
α∈G − +
j∈Cαi j∈Cαi
X X X
yjα − yjα + zi ≤ |Ci− |, i ∈ I0 \I00 ; (3)
α∈G − +
j∈Cαi j∈Cαi
X X
−
yjα − yjα ≤ |C̃αr | − 1, r ∈ Iα0 , α ∈ G; (4)
− +
j∈C̃αr j∈C̃αr
X X
−
yjα − yjα + zrα ≤ |C̃αr |, r ∈ Iα \Iα0 , α ∈ G; (5)
− +
j∈C̃αr j∈C̃αr
0 ≤ yjα ≤ 1, yjα ∈ Z, j ∈ Jα ; (6)
0 ≤ zi ≤ 1, zi ∈ Z, i ∈ I0 \I00 ; (7)
0 ≤ zrα ≤ 1, zrα ∈ Z, r ∈ Iα \Iα0 , α ∈ G. (8)
Here Ci− and Ci+ (Cαi − +
and Cαi respectively) are the indexes sets of the neg-
ative and positive literals in clause Ci (Cαi ). Note that if zi (zrα ) is equal to
one in a feasible solution of the problem, then clause Ci (C̃αr ) is satisfied. The
optimal value of the objective function is the total weight of satisfied clauses. In
the objective function (1), the sum of weights of the ”soft” logical constraints
is maximized by the relating variables belonging to different groups of com-
ponents, and variables of individual groups. Inequalities (2) correspond to the
”hard” logical constraints binding the variables among the groups. Inequalities
(3) correspond to the ”soft” constraints binding the variables among the groups.
Constraints (4) and (5) are similar to constraints (2) and (3) but bind variables
within one group,(6) – (8) are the conditions on the boolean variables.
A feasible solution of problem (1) – (8) determines a variant of a product
satisfying the above-mentioned conditions. Note that the designer is able to
correct the previously 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 [4, 12]. 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 cre-
ation of outfits [4], i.e., the sets of clothes that consist of items which belong
to two or more various assortment groups interconnected by the unity of style,
shape, and the proportional ratio of elements, coherence of articulations, a com-
bination of trimmings and materials, color scheme, etc.
10 A. Adelshin et al.
3 On Finding Coloristic Solutions
Coloristic theory plays an important role in the process of design of a visual
variety of garments [7, 13]. To find the optimal color decision on the basis of
several criteria, it is possible to construct and use various restrictions, including
logical ones. As a result, we obtain a technical outline with a selection of color-
grades of materials for its production, which satisfy fashion trends, the theory
of colors combination and the requests of the designer.
The construction of mathematical models for the problem of finding color so-
lutions is based on the recommendations of the theory of costume design, taking
into account preferred color combinations. The selection of harmonious color-
grades, that give the impression of color entirety and the relationship between
colors of details, is important.
We describe the scheme for finding solutions to the problem of selection of
color-grades for sewn products. In the first stage, an optimal solution is found on
the basis of the initial mathematical model (without taking color into account).
Next, a model of integer linear programming is constructed on the basis of the
maximum satisfiability problem. The purpose is to determine the set of colors
(palettes) used for colouring technical outlines. The designer can choose a color
solution for single or serial production, as well as specify a certain color range,
which can also be applied for outfits. In the last stage, a transition to the distri-
bution of selected colors among the details of a garment is made. It takes into
account the dimensions of the specific elements to obtain a harmonious com-
bination of proportions, according to the principle of the golden ratio [7]. The
corresponding system of inequalities is constructed based on the ratio of areas.
Also it is possible to arrange the priority of the use of available remainders of
fabrics of specific colors.
To research the problem of finding the optimum coloristic solution from the
point of view of several criteria, we use the twelve-part color wheel, the fragment
of which is presented in Figure 1. The color wheel is an important foundation
for any aesthetic theory of color, since it gives the system of color arrangement
and allows us to understand clearly the schemes of harmonious combinations.
The considered scheme of division of a color circle allows classifying colors
into groups and harmonious combinations formed [7, 13]:
1) Related colors;
2) Relatively-contrasting colors;
3) Contrast colors.
We consider combinations of related-contrast colors. The main combinations
of the colors (see Figure 1) are the pairs of complementary colors (diametrically
opposed colors), all combinations of three and four colors in the twelve-colored
wheel that are connected to each other through equilateral or isosceles triangles,
squares and rectangles.
We now turn to the construction of mathematical models for the problem
of finding color solutions for the obtained outlines, based on the problem of
aumomation of outline design described, for example, in [12]. We construct a
new mathematical model. We introduce the following notations:
Discrete Optimization Models for Complex Products Design Problems 11
Fig. 1. Fragment of the scheme of harmonious color combinations according to Jo-
hannes
J – the set of color numbers, J = {1, ..., n};
vj – the color with number j ∈ J;
xj – a boolean variable that takes the value of true if vj is a part of the
palette and false otherwise;
sj – the weight of the color according to vj , j ∈ J;
p1 , p2 – the lower and upper bounds for the total number of colors included
in the product;
I – the set of logical formula numbers used in the model;
Ci – the logical formula corresponding to the i-th constraint, which is the
disjunction of variables and/or their negations;
The task is to find the values of the logical variables that limit the total
number of colors included in the product, and formulas Ci , i ∈ I are satisfied,
and the weight of the colors included in the gamut will be maximum.
Similar to the previous model we denote by y1 , ..., yn boolean variables, that
yj corresponds to literal xj , and (1 − yj ) corresponds to literal x̄j , j = {1, ..., n}.
The problem of integer linear programming for the case under consideration is
as follows:
X
g(y) = sj yj → max (9)
j∈J
X X
yj − yj ≤ 1 − |Ci− |, i ∈ I, (10)
j∈Ci− j∈Ci+
X
p1 ≤ yj ≤ p2 , (11)
j∈J
0 ≤ yj ≤ 1, yj ∈ Z, j ∈ J, (12)
0 ≤ zi ≤ 1, zi ∈ Z, i ∈ I. (13)
12 A. Adelshin et al.
All the conditions of a harmonious combination of colors (10) considered
in the problem are constraints of a hard type. Condition (11) determines the
possible number of colors in the found gamma.
In Figure 1 the vertices of the graph correspond to the colors of the circle, and
arc (x1 , x7 ) and subgraphs (x1 , x5 , x9 ), (x1 , x6 , x8 ), (x1 , x3 , x7 , x9 ), (x1 , x4 , x7 , x10 )
correspond to the logical constraints that describe harmonious combinations of
colors. The part of the system of logical constraints, for example, for color x1 ,
can be presented the following way:
1) If ”yellow” is selected, ”purple” must be added:
x1 → x7 .
2) If ”yellow” is selected, ”blue” or ”red” must be added:
x1 → (x5 ∨ x9 ).
3) If ”yellow” is selected, ”blue-violet” or ”violet-red” must be added:
x1 → (x8 ∨ x8 ).
4) If ”yellow” is selected, ”green”, ”purple” or ”orange” must be added:
x1 → (x3 ∨ x7 ∨ x9 ).
5) If ”yellow” is selected, ”blue-green”, ”purple” or ”red-orange” must be
added:
x1 → (x4 ∨ x7 ∨ x10 ).
6) If ”yellow” is selected, ”orange-yellow” or ”yellow-green” must be added:
x1 → (x2 ∨ x12 ).
Similarly, restrictions for all the remaining schemes and colors of the circle
are made. As the result of solving these problems, the user will receive a set of
color scales that satisfy the set conditions.
After that, the transition to the distribution of the selected colors among
details of a garment is carried out. It takes into account their area. The corre-
sponding mathematical model is as follows:
To describe the model of the problem, we introduce the following notation
similar to the previous model:
J – the set of numbers of components of the product;
P – the set of numbers of colors;
vjp – the component with number j of color p, j, j ∈ J, p ∈ P ;
spj – the weight of component vjp (the square);
Discrete Optimization Models for Complex Products Design Problems 13
Ap – the volume of the resource p (the square of material of color p), p ∈ P ;
Let p = 1 is the main color, which is determined by the designer.
X
h(y) = s1j yj1 → max (14)
j∈J
X X X
s1j yj1 ≤ 2 spj yjp ; (15)
j∈J j∈J p∈P \{1}
X X
yj − yj ≤ 1 − |Ci− |, i ∈ I, p ∈ P ; (16)
j∈Ci− j∈Ci+
X p p
sj yj ≤ Ap , p ∈ P ; (17)
j∈J
X
yjp = 1, j ∈ J; (18)
p∈P
0 ≤ yjp ≤ 1, yjp ∈ Z, j ∈ J, p ∈ P. (19)
4 On Development of Algorithms for Searching Exact
and Approximate Solutions
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 developed.
For the analysis and solution of the problems of ILP, the regular partition
method was previously proposed, which was successfully used for various prob-
lems of discrete optimization [8, 9]. The L-partition is the most studied among
the partitions. On the basis of this approach, algorithms for solving the satisfia-
bility and maximum satisfiability problems were proposed. In this paper, to solve
problem (1)-(8) we develop an algorithm based on the search for the L-classes,
which makes it possible to find a series of products based on a set of optimal
solutions or close to optimal ones. Consider the scheme of this algorithm, based
on the combination of the algorithm for the L-class enumeration and the package
of applied programs GAMS.
The algorithm for constructing a series of complex products (the problem
determined by conditions (1)-(8)):
Step 0. We solve the problem of satisfiability (2), (4) for ”hard” constraints
with the help of the algorithm for the L-class enumeration of LCE. If the formula
is feasible, we get a feasible solution y and go to step 1. Otherwise the algorithm
completes the work, the formula is unsatisfiability.
Step 1. We substitute the found admissible solution into constraints (3), (5).
We formulate the maximum satisfiability problem. If zi = 1, we exclude the
corresponding restriction Ci , i ∈ I\I 0 , from the formula. We solve this problem
using the package GAMS. If the executing set y ∗ is found, it and the value of
14 A. Adelshin et al.
the objective function are fixed. Go to step 2. Otherwise, immediately move on
to the next step.
Step 2. We use the algorithm for of the L-class enumeration to find the follow-
ing admissible solution in the order of lexicographic descending. The following
cases are possible:
a) The requested solution is found. Go back to step 1.
b) There are no admissible solutions or there are no solutions at all. All the
received sets y ∗ are collected, if any, and go to step 3.
Step 3. If there is no admissible solution y ∗ that satisfy constraints (3),
(5), then it is unsolvable. Otherwise, we obtain a set of solutions of the original
problem. The algorithm completes the work in two cases: if one or more solutions
to the problem are obtained, or the solution to this problem cannot be found. In
the future, when constructing a series of products, the designer can use different
criteria for selecting the solutions obtained. For example, choose variants for
which the values of the objective function (1) are maximal, or deviate from
the optimum by no more than a certain predetermined value. In the case of
an approximate solution of the problem, the maximum permissible deviation
from the optimal solution (by the value of the objective function) is taken into
account.
The proposed algorithm is implemented in Visual Studio C++ environment.
With the purpose of approbation experimental studies on the class of problems
of designing series of products of the dress-blouse assortment were carried out.
The task with real initial data was taken. Its solutions resulted in series of sewn
products of the dress-bloise assortment [3].
5 Computational Experiments
The computational experiments were divided into the following stages:
1) Finding variants of outlines (optimal solutions of problem (1) - (8)) without
taking coloristics into account;
2) Selecting the dominant color (by varying the weights), searching for opti-
mal color combinations using model (9)-(13);
3) For the variants found, model (14) - (19) is used to find the proportional
ratio of color spots for one product.
At all stages, the algorithm developed by the authors for finding exact and
approximate solutions was also used. For the experiments, the task with real
initial data for the design of women’s casual dresses was taken. It contained 30
variables, 55 ”hard” and 6 ”soft” constraints. For the experiments, the weights of
the elements and the value of the designer’s constraint were varied. The weights
of the corresponding variables were changed to select the dominant color. In the
third stage, variants of the sets of the colors were obtained for the outlines, some
of which are shown in Figure 2.
As it can be seen in Figure 2, in case of applying various color solutions to
the products created on the basis of one kernel, specialists can significantly in-
crease visual diversity of finished products at minimal costs. The results of the
Discrete Optimization Models for Complex Products Design Problems 15
Fig. 2. Fragment of computational experiments
experiments confirmed the prospects of applying the developed approach for ob-
taining a series of various solutions including taking coloristics into account. The
authors plan to continue developing this theme in the direction of considering
lightness, saturation, temperature, chromatic colors, as well as the description
of new combinations schemes, including achromatic colors.
6 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, including consumer goods industry, are continued. The special attention
is paid to the creation of complex products on the base of the theory of coloristics.
Corresponding mathematical models for automation of outline design of complex
products are offered.
The developed algorithm for searching exact and approximate solutions has
been proposed. The computational experiments with real input data have been
carried out and show the prospects of further development of the appoach.
References
1. Adelshin, A.V.: Investigation of maximum and minimum satisfiability problems
using L-partition. Automation and Remote Control 65(3), 388–395 (2004)
2. Adelshin, A.V., Zhovner E.N.: Application of the SAT problems of logical formu-
las for the chemical composition of rubber compounds design. Herald of Omsk
University 2, 14–18 (2011), (in Russian)
3. Adelshin, A.V., Artemova, A.V., Kan, I.E., Suleimenova, Z. B.: Development of
mathematical models and algorithms for solutions of some problems of optimum
design. In: Proceedings of XIII International Asian school-seminar “Problems of
complex systems’ optimization”. pp. 5–10 (2017), (in Russian)
16 A. Adelshin et al.
4. Artemova, A.V., Kan, I.E.: Application of methods of discrete optimization for the
design of some classes of complex products in terms of colour. In: Proceedings of
X Asian school-seminar “Problems of complex systems’ optimization”. pp. 65–68
(2014), (in Russian)
5. Gu, J., Purdom, P., Franco, J., Wah, B.: Algorithms for the Satisfiability (SAT)
Problem: A Survey. DIMACS Series in Discrete Mathematics and Theoretical Com-
puter Science. 131 p. (1996)
6. Guseletova, O.N., Kolokolov, A.A.: Discrete optimization with logical constraints
for design of complex products. Automation and Remote Control 69(10), 1808–
1813 (2008)
7. Johannes, I.: The Art of Color (translation from German). 96 p. (2001), (in Rus-
sian)
8. Kolokolov, A.A., Adelshin, A.V., Yagofarova, D.I.: Analysis and solving SAT and
MAX-SAT problems using an L-partition approach. Journal of Mathematical Mod-
eling and Algorithms 12(2), 201–212 (2013)
9. Kolokolov, A.A., Adelshin, A.V., Yagofarova, D.I.: Study of discrete optimization
problems with logical constraints based on regular partitions. Applied Discrete
Mathematics 1(19), 99–109 (2013), (in Russian)
10. Kolokolov, A.A., Yarosh, A.V.: Clothes design using some discrete optimization
models. Omsk Scientific Gazette 20, 91–94 (2002), (in Russian)
11. Kolokolov, A.A., Serysheva, Y.S., Shulepova, L.D.: Decision of tasks of small groups
forming with regard for interpersonal relations. In: Proceedings of the XV Baikal
international school-seminar “Optimization Methods and their applications”. vol.
5, pp. 61–66 (2011), (in Russian)
12. Kolokolov, A., Artemova, A., Adelshin, A., Kan, I.: Discrete optimization models
for solving complex products design problems. In: Proceedings of International
conference on discrete optimization and operations research (DOOR-2016). pp.
49–56. Vladivostok, Russia (2016)
13. Parmon, F.M.: Composition of Costume: College Textbook. 318 p. (1997), (in
Russian)
14. Posypkin, M.A., Zaikin, O.S., Bespalov, D.V., Semenov, A.A.: Decision of the
problem of cryptanalysis of sequence cipher in distributed area networks. In: Pro-
ceedings of ISA. vol. 46, pp. 119–137 (2009), (in Russian)
15. Sano, T., Yamamoto, H.: Computer aided design system for Japanese kimono. In:
Proceedings of the 18th IEEE. vol. 1, pp. 326–331 (2001)