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 consumers without signi cant production costs. A mathematical model for the distribution of colors to the details of complex products based on the theory of color and the satis ability problem is proposed. The results of computational experiments which re ect the prospects of further development of the considered approach are presented.
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 satis ability problem. This problem is a generalization of the well known satis ability 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 NP-hard. The considered problems with the speci ed constraints can be used to solve a variety of applied problems in many elds. 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 di erent 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 possibilities 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 lling. Much attention is paid to the questions of the design of complex products with due regard to coloristic solutions which allow broading the variety of the produced products. During manual design, an expert must search through and compare a large number of variants of color combinations for components 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
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 xj (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 nding an assignment to the variables that maximizes the weight of the satis ed clauses.
In addition, 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).
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 conducted [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 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 constraints. 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 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 = f1; : : : ; ng; G { the set of groups of components and characteristics;
{ the number of a group of the components and characteristics, 2 G; J { the numbers of elements in group ; vj { the component with number j from group ; xj { 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 = f1; : : : ; mg;
I0 { the set of the logical formulae that bind variables from di erent groups; Ci { the logical formula corresponding to the i-th logical constraint, i 2 I0, which is a disjunction of variables xj and/or their negations. It should be noted that the formulae with numbers from I00 I0 must be satis ed;
di { the weight of formula Ci that de nes the signi cance of satisfying this formula, i 2 I0nI00;
C~ r { the logical formula corresponding to the r-th logical constraint and bind variables from group ; r 2 I . Equations with numbers from I0 I must be satis ed;
dr { the weight of formula C~ r that de nes the signi cance of satisfying this formula, r 2 I nI0 ;
The problem is to nd the values of the logical variables which satisfy logical formulae Ci with numbers i 2 I00 and logical formulae C~ r , r 2 I0 ; 2 G. The total number of the satis ed formulae Ci, i 2 I0nI00, and formulae C~ r, r 2 I nI0 ; 2 G is maximized.
Let us assume that the boolean variable yj takes 1 if a corresponding element is included in the product (xj = true) and it takes 0 otherwise, j 2 J; 2 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: f (z) =
X
X
dr zr ! max
2G r2I nI0
(
X yj j2C i
X yj j2C+i X yj
X yj jCi j
1; i 2 I00; + zi
jCi j; i 2 I0nI00; jC~ rj
1; r 2 I0 ; jC~ rj; r 2 I nI0 ;
Here Ci and Ci+ (C i and C+i respectively) are the indexes sets of the
negative 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 satis ed. The
optimal value of the objective function is the total weight of satis ed clauses. In
the objective function (
A feasible solution of problem (
One of the e ective 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 de ne a xed 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 out ts [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 combination of trimmings and materials, color scheme, etc.
Coloristic theory plays an important role in the process of design of a visual variety of garments [7, 13]. To nd 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 colorgrades 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 nding color solutions is based on the recommendations of the theory of costume design, taking into account preferred color combinations. The selection of harmonious colorgrades, that give the impression of color entirety and the relationship between colors of details, is important.
We describe the scheme for nding solutions to the problem of selection of color-grades for sewn products. In the rst 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 satis ability 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 out ts. In the last stage, a transition to the distribution of selected colors among the details of a garment is made. It takes into account the dimensions of the speci c elements to obtain a harmonious combination 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 speci c colors.
To research the problem of nding 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 nding 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:
J { the set of color numbers, J = f1; :::; ng; vj { the color with number j 2 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 2 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 nd the values of the logical variables that limit the total number of colors included in the product, and formulas Ci; i 2 I are satis ed, 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 xj , j = f1; :::; ng. The problem of integer linear programming for the case under consideration is as follows:
X yj j2Ci g(y) =
X sj yj ! max j2J X yj j2Ci+
All the conditions of a harmonious combination of colors (
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: x1 ! (x5 _ x9): x1 ! (x8 _ x8): x1 ! (x3 _ x7 _ x9): x1 ! (x4 _ x7 _ x10):
x1 ! (x2 _ x12): 2) If "yellow" is selected, "blue" or "red" must be added: 3) If "yellow" is selected, "blue-violet" or "violet-red" must be added: 4) If "yellow" is selected, "green", "purple" or "orange" must be added: 5) If "yellow" is selected, "blue-green", "purple" or "red-orange" must be added: 6) If "yellow" is selected, "orange-yellow" or "yellow-green" must be added: 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 corresponding 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 2 J; p 2 P ;
sjp { the weight of component vjp (the square);
Ap { the volume of the resource p (the square of material of color p), p 2 P ;
Let p = 1 is the main color, which is determined by the designer.
(
X yj j2Ci+
X sj yj
1 1 j2J h(y) =
X sj yj ! max
1 1 j2J Currently, some special algorithms to nd 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
problems 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 satis
ability and maximum satis ability problems were proposed. In this paper, to solve
problem (
The algorithm for constructing a series of complex products (the problem
determined by conditions (
Step 0. We solve the problem of satis ability (
Step 1. We substitute the found admissible solution into constraints (
Step 2. We use the algorithm for of the L-class enumeration to nd the following 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 (
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
The computational experiments were divided into the following stages:
1) Finding variants of outlines (optimal solutions of problem (
2) Selecting the dominant color (by varying the weights), searching for
optimal color combinations using model (
3) For the variants found, model (
At all stages, the algorithm developed by the authors for nding 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 signi cantly increase visual diversity of nished products at minimal costs. The results of the experiments con rmed the prospects of applying the developed approach for obtaining 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
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 o ered.
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.