The development and research of discrete optimization models with logical, resource and other constraints to solve complex products design problems 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 re ect the prospects of the approach are presented.
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 satis ability problem, which is a
generalization of the well known satis ability 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 speci ed constraints can be used to solve many applied problems in
various elds. 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 [
Currently, design of complex products has received much attention due to the
relevance of this direction. Many design problems are solved with the help of different
computer systems, for example [
In [1{5, 10{12, 16{20] and other papers, mathematical models are applied that are
generalizations of the maximum satis ability problem and include two types of
constraints: "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 [
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 xj (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 xj ; j = 1; : : : ; n. Satis ability of the formula is equivalent to solvability of the following system: ∑ yj j2Ci+ ∑ yj j2Ci 1 where Ci and Ci+ are the index sets of the negative and positive literals in clause Ci, respectively.
If zi is equal to one in a feasible solution of problem (4){(8), then clause Ci is satis ed. The optimal value of the objective function is the total weight of satis ed 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).
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.
Here we provide a formulation of the MAX-SAT problem as an integer linear programming (ILP) problem: yj ; zi
1; j = 1; : : : ; n; i = 1; : : : ; m; yj ; zi 2 Z; j = 1; : : : ; n; i = 1; : : : ; m:
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 [
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
subject to:
∑ yj
j2Ci+
∑ yj
j2Ci
0
∑ yj
j2Ci
∑ yj + zi
j2Ci+
y0 =
m
∑ cizi ! max
i=1
1
the development of algorithms solving the problem [
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 the 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;
L { the set of numbers of indicators that characterize the degree of the expediency of inclusion of components and characteristics in the product;
slj { the weight of component or characteristic vj according to the l-indicator, l 2 L; j 2 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 = f1; : : : ; mg; 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 2 I0, which is a disjunction of variables xj and/or their negations. It should be noted that the formulae with numbers from I0′ I0 must be satis ed;
di { the weight of formula Ci that de nes the signi cance of satisfying this formula, i 2 I0nI0′;
C~ r { the logical formula corresponding to the r-th logical constraint and bind variables from group ; r 2 I . Equations with numbers from I′ 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 nI′ ;
K { the set of the used resources; akj { the volume of the k-th resource that is necessary to produce the j-th component of the product in group , k 2 K; j 2 J ; bk { the available volume of the k-th resource, k 2 K.
The problem is to nd the values of the logical variables which satisfy the logical formulae Ci with numbers i 2 I0′ and the logical formulae C~ r , r 2 I′ ; 2 G. The resource constraints and the constraint for the total weight of the components included in the product must be satis ed and the total number of the satis ed formulae Ci, i 2 I0nI0′, and the formulae C~ r, r 2 I nI′ ; 2 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 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: subject to: f (z) =
∑ i2I0nI0′ dizi + ∑ ∑
dr zr ! max 2G r2I nI′ (15) ∑ ( ∑ yj 2G
j2C i ∑ yj j2C~ r ∑ yj j2C~ r ∑ j2C~+r ∑ ( ∑ yj 2G j2C i ∑ yj j2C+i
) ∑ yj
) jCi j
1; i 2 I0′; j2C+i ∑ yj j2C~+r yj + zr ∑ ∑ (16) (17) (18) (19) (20) (21) (22) (23) (24) (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 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 [
pl; l 2 L; akj yj
bk; k 2 K; 1; yj 2 Z; j 2 J ; 1; zi 2 Z; i 2 I0nI0′; 1; r 2 I nI′ ; 2 G: art, design and technological compatibility. This method allows to form clothes and produce them at the same time in one production ow 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 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 [
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 signi cance degree of certain "soft" logical constraints as well. Various silhouette shapes of products were examined. We also xed the minimum number of elements that were included in the outline. The calculations con rmed 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 nd exact and approximate solutions of the
investigated problems to create series of products based on one "kernel" are being
developed. 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
analysis and solving integer programming problems [
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
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 series and out ts 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.