Modelling and Types of Specifications

Abstract

This chapter studies the main part of a mathematical programming model, the constraints. We integrate the concept of constraints on the concept of specification, giving a classification of specifications in two levels, first depending of the type of statement and second depending on the semantic. A complete scheme for the modelling of compound propositions is proposed. Important aspects as the identification of implicit specifications in a system and its relation with the elements also are defined in the chapter.

6.1 Introduction

The specifications of an optimization problem include all the constraints existing within it. The constraints have been catalogued generally according to their meaning, as Williams (2013) have already pointed out, although proposing a classification of constraints seems to be a rather complex task. The only classification that I consider 100% valid would be the one that refers to the sign of the constraints. There are constraints of three signs: ≤, ≥, and =. However, with this classification, we would not pay attention to the meaning of the specification. And on the other hand, not all specifications correspond to a single constraint. There are specifications, as we will see, that are modelled using more than one constraint.

Therefore, in this methodology, we will propose a classification in two levels. The upper level is determined by the way in which the specification is stated, whereby we would have two types of specifications:

• A. Specification stated as a simple proposition

• B. Specification stated as a compound proposition

In Sect. 5.3, dedicated to logical calculations, we state the concept of proposition and its typologies. It is important to bear in mind that a proposition in mathematical programming is defined as a mathematical semantic content that, when applied to a solution, can be assigned a truth value (true or false).

Remember also that there are two kinds of propositions:

• Simple: also called atomic, they express a statement that cannot be divided into other propositions because they do not employ any logical operator.

• Compound: propositions composed of logical operators and one or more simple propositions. In the previous chapter, several examples of the formulation of compound propositions were already shown. In this chapter we will study its modelling.

Specifications Stated as Simple Propositions

The specifications that are formulated as simple propositions give rise to most of the constraints of optimization problems. Simple propositions can also be classified, here with greater difficulty and not exclusively, depending on the meaning or objective of the constraints or the intervening variables. In this methodology, we will define the following types of specifications stated as simple propositions:

• Quantitative specification of selection

A specification based on the variables involved. Whenever logical activities are presented on sets of individual elements or binary logical calculations, it is necessary to analyze the existence of this type of specification, since in many cases they are not explicitly described in the description of the system because they are understood.

They can be of three types:

• Upper bound

• Lower bound

• Equality

Capacity specifications

Based on the semantics of element data, it is a specification catalogued by some authors. It is based on availability data of elements that have a resource character in the system. The two most common formats in which it is presented in a system are:

• Specification focused on the consumption of capacity: The capacity of the resource can be partially consumed.

• Specification focused on the contribution of capacity: The capacity of the resource is used to satisfy a fixed demand for capacity. In this case, the capacity is used in its entirety.

Supply of a demand

Based also on data semantics, it is the opposite of the capacity specification. It occurs when an element has an attribute that represents a quantity demanded that is necessary to cover or supply.

• Bound imposition specifications

These are the most easily recognizable specifications in a system. It would be a typology regarding the way of stating the specification. There are two types:

• Imposition of maximums: these impose upper bounds on variables or functions of variables. Within these we could also include the specifications of capacity consumption.

• Imposition of minimums: these impose lower bounds on variables or functions of variables.

Allocation or balance specifications

These impose values on variables or functions of measurable variables. They also impose a balance between the inputs and outputs of a measurable element, collective or individual. Included in this typology are constraints on the distribution of stocks or those that impose equality between variable functions.

It is inevitable that sometimes certain specifications will be considered as belonging to more than one typology.

Specifications Stated as Compound Propositions

The specifications enunciated as compound propositions have already appeared in the chapter dedicated to the logical calculations of a system. They are specifications that are based on a logical language, using logical operators or a connective to define the specification. They are also usually easily identifiable in the system description. As we already mentioned, the modelling of logical propositions could involve the definition of logical calculations. In this chapter, we will see the modelling of any type of compound proposition.

The formulation of logic-based propositions has been studied mainly by Mitra et al. (1994), Williams (1995), and Williams (2009) proposing constraints using binary decision variables, particular propositions as disjunctive constraints but there is not a general method for formulating any compound propositions with any connective.

In this book we will see a general scheme for modelling compound propositions where the basic rules are based on the modelling of propositions already described by those authors.

The structure of this chapter is as follows: first (Sect. 6.2) we will analyze the elements on which the specifications fall. In Sects. 6.3 to 6.7, we will present the modelling of each type of simple specification (A.1 to A.5). Section 6.8 will deal with the modelling of compound propositions. Section 6.9 is devoted to objective functions, since objective functions can be considered as one more specification of the system. In Sect. 6.10, we will analyze the identification of specifications in the description of a system.

6.2 Elements on Which the Specification Falls on

When it comes to modelling a specification, the first task is to identify to which elements the specification is directed. If it is an individual specification, it will be directed to a particular element within a set, to an element that is not part of any set or to the system itself. If the specification is directed to a set of elements, the construction of the specification uses terms such as “Every” or “A” as an indeterminate article, without referring to one in particular but to any. This means that the specification will have to be mounted for each element of the set. We can even express a specification using the term “all.” In this case the norm must also be mounted for each element individually if they are defined individually.

Illustration 6.1

In a system for assigning jobs to machines, with those elements defined as unitary, the specification that assigns each job to a machine could be defined as:

• Each job must be assigned to a machine.

• A job will be assigned to a machine.

• All jobs must be assigned to a machine.

It could also be that the specification does not apply to all elements of the set but only to those that meet a condition subject to the values of their data or their indices. This will be expressed using the mathematical symbol “such that” (/):

• ∀i/C_i>10: … . (C_i is an attribute of the elements of the index set i)

• ∀i,j/i>j: … .

• ∀i/i≥3: … .

We should never express variables in the clause such that. As its value is not determined, we will not know whether or not the specification is applied:

• ∀i/x_i>10: … . Error!

Whenever we try to define variables in the clause “such that,” we must define a conditional logical proposition “IF…THEN…” that uses these variables as an input condition of the conditional. The logical propositions will be studied in Sect. 6.8. Let’s look at a simple example:

• ∀i/x_i > 10 : α_i + β_i ≤ 1 ⇒  ∀ i : IF x_i > 10 THEN α_i + β_i ≤ 1

It may also be common for specifications to be defined by the combination of several sets of elements. Again, the determination of the elements depends on the way in which they are alluded to in the statement of the specification, if in a determined way on some elements or in an indeterminate way, which is why all the combinations that define the specification should be considered. Let us look at an example:

Illustration 6.2: Distribution of Ham

A ham distribution company has designed a set of 20 delivery routes for distribution. The company has a portfolio of 350 clients. Each delivery route goes through a series of known customers. The company has ten vehicles for the distribution stage. Each vehicle has a given capacity or number of Iberian hams that it can transport.

The demand for ham that must be supplied to each customer is known. Each vehicle that delivers ham must choose a single route, since more than one would take too long.

Two vehicles cannot choose the same route.

If a vehicle delivers more than 50 Iberian hams to a customer, it should not deliver ham to any other customer.

We know the delivery cost of each route.

• Table of Elements (Table 6.1)

Table 6.1 Table of elements of Illustration 6.2

In the Customer_Route attribute, the customers by which each route passes are annotated. It is therefore shared between routes and customers.

• Decision Activities

  • Action: Deliver [Iberian hams to customers with vehicles]

  • Decision variables:

  • x_kj = Number of Iberian hams delivered with vehicle k to customer j.

  • k = 1…10, j = 1…350

• Action: Choose [Routes for vehicles]

• Decision variables:

• α_ik =1 if I choose Route i for Vehicle k; 0 otherwise. k = 1…10, i = 1…20

Let us analyze two of the specifications of the system:

• Specification 1: Two vehicles cannot choose the same route

The first question would be: which two vehicles? They are not determined, so we should consider the combination of every two vehicles from the ten vehicles. Obviously, since vehicles are individuals, this value (two vehicles) cannot represent a numeral of a collective element.

The second question would be: which route? And again, the answer is indeterminate, so we should consider them all.

Therefore, the specification is presented for each pair of vehicles and each route. For vehicles, we can define a second subscript k'. The specification is defined by a logical statement:

$$ \mathrm{Logical}\ \mathrm{proposition}:\forall k,{k}^{\prime },i:\mathrm{NOT}\ \left({\alpha}_{ik}=1\ \mathrm{AND}\kern0.5em {\alpha}_{i{k}^{\prime }}=1\right) $$

(6.1)

This specification could also be written as follows: The number of vehicles that can choose each route must be at most 1:

$$ \forall i:\sum \limits_{k=1}^{10}{\alpha}_{ik}\le 1 $$

(6.2)

Specification 2: If a vehicle delivers more than 50 hams to a customer, it should not deliver ham to any other customer:

• “a vehicle”: indeterminate, any vehicle

• “a customer”: indeterminate, any customer

“any other customer”: the rest of customers is also indeterminate, any customer.

$$ \mathrm{Logical}\ \mathrm{proposition}:\forall j,{j}^{\prime }/{j}^{\prime }<>j,k:\mathrm{IF}\;{x}_{kj}>50\ \mathrm{THEN}\;{x}_{k{j}^{\prime }}=0 $$

(6.3)

The specification could also have been defined with the following equivalent statement: If a vehicle delivers more than 50 Iberian hams to a customer, the sum of Iberian hams to the rest of customers will be zero:

$$ \mathrm{Logical}\ \mathrm{proposition}:\forall j,k:\mathrm{IF}\;{x}_{kj}>50\ \mathrm{THEN}\sum \limits_{j^{\prime}\ne j}{x}_{k{j}^{\prime }}=0 $$

(6.4)

Both in (6.2) and in (6.4) the number of specifications is reduced, which a priori may contribute to improving the resolution times of the model.

6.3 Quantitative Specifications of Selection

Specifications are very common in modelling. They are relevant when we work with variables of logical decision and can also be enunciated with respect to a set of binary logical calculations.

This specification expresses a quantitative condition with respect to the set of binary variables. It is to establish the amount of choices that are going to be given or that can be given as a maximum or minimum.

• Format: Sum of Selection options SIGN Value

• General Expression:

• α₁ + α₂ + … + α_n ≈ Value

• Regarding the SIGN (≈):

• ${\displaystyle \begin{array}{l}\kern2.5em =\mathrm{Exact}\ \mathrm{imposition}\ \mathrm{or}\ \mathrm{imposition}\ \mathrm{of}\ \mathrm{equality}\\ {}\kern2.5em \le\ \mathrm{Imposition}\ \mathrm{of}\ \mathrm{upper}\ \mathrm{bound}\\ {}\kern2.5em \ge \mathrm{Imposition}\ \mathrm{of}\ \mathrm{lower}\ \mathrm{bound}\\ {} Value=\mathrm{Quantification}\ \mathrm{of}\ \mathrm{the}\ \mathrm{selection}\end{array}}$

The sum of binary variables expresses the set (or sets) of elements that are selection options. The most frequent case of this type of specification occurs between more than one set of individual elements, normally of unitary nature, which are combined in the events of the decision activity, although it is also possible to find it in a single set of elements.

As we will see in Sect. 6.10, this type of specification may not appear explicitly in the description of the system, so we will always have to do an analysis exercise of the quantitative selection rules when we have systems with logical activities.

Let us consider some examples of the specification in different scenarios:

Illustration 6.3: Case of a Set of Unitary Elements

Let us suppose there is a series of activities that make reference to the use of a unitary set of machines:

• Elements: Machines i = 1…n Unitary

• Decision activities:

• Use (Machines i = 1…n) ⇒ α_i = 1 if I use machine i; 0 otherwise

Quantitative specifications of selection: In this system, specifications such as the following could be considered:

• You must use (select) at least one machine: $\sum \limits_{i=1}^n{\alpha}_i\ge 1$

• You must use three machines: $\sum \limits_{i=1}^n{\alpha}_i=3$

Illustration 6.4: Case of Two Sets of Elements

Let us suppose there is a series of operators that must be assigned to a series of machines:

• Elements: Machines i=1…n Unitary; Operators j=1…m Unitary

• Decision activities:

• Assign (Operators to Machines) → α_ij=1 if I assign operator j to machine i; 0 otherwise.

• Quantitative specifications of selection:

• Maximum two operators per machine: This specification falls on each machine of the system:

• $\forall i:\sum \limits_{j=1}^m{\alpha}_{ij}\le 2$

• An operator must be assigned only one machine: The specification refers to any operator, since it refers indeterminately to an operator. On the other hand, with machines it refers to the quantity of a machine.

• $\forall j:\sum \limits_{i=1}^n{\alpha}_{ij}=1$

If we assume a power attribute (P) for the machines, we could find a specification that does not consider, as a selection option, all the elements of the set of machines:

A machine with power greater than 10000w will be assigned to operator 3:

• $j=3:\sum \limits_{i/P>10000}{\alpha}_{ij}=1$

Illustration 6.5: Case of a Set with Choices About the Set Itself

Let us suppose there is a series of elements that must be assigned among them. Each element must be associated with another element of the same set:

• Elements: Elements i=1…n Unitary;

• Decision activity:

Assign [Elements to Elements] → α_ij=1 if I assign element i to element j; 0 otherwise.

• Quantitative specifications of selection:

  • Each element is associated with a different element of itself.

    $\forall i:\sum \limits_{j/j\ne i}{\alpha}_{ij}=1$

  • Since i and j are indices of the same set and is a bi-univocal correspondence, the association of i with j is the same as that of j with i, therefore: ∀i, j : α_ij = α_ji

Illustration 6.6: Case of Two Sets That Share the Selection

Let us suppose that we have divided elements of the same functionality in the system into two sets due to data, but both share the same logical decision activity on which a quantitative selection rule is applied.

• Elements:

• Individuals i=1…n Unitary;

• Groups_Type1 j=1…m₁ Unitary;

• Groups_Type2 k=1…m₂ Unitary;

• Decision activity:

• Assign [Individuals to Groups_Type1 and Groups_Type2] →

• →Events: Individuals to Groups_Type1; Individuals to Groups_Type2 →

• → α_ij=1 if I assign Individual i to Group_Type1 j; 0 otherwise.

• → β_ik=1 if I assign Individual i to Group_Type2 k; 0 otherwise.

• Quantitative specifications of selection:

• One individual in a group at most:

• $\forall i:\sum \limits_{j=1}^{m_1}{\alpha}_{ij}+\sum \limits_{k=1}^{m_2}{\beta}_{ik}\le 1$

6.4 Capacity Specifications

Capacity specifications are ones that appear in systems where there are elements acting as resources. For this, they must have an attribute of capacity or availability, either intrinsic to the element or shared with a measurable element, collective or individual. They usually appear in different ways that are synthesized in the following general format:

• Format: Capacity Consumption or Demand for Capacity ≤ Capacity Contribution

• Expression: Both the consumption or demand for capacity and the contribution of capacity can be fixed and/or variable. Capacity contribution and consumption must be expressed in the same unit of measure. In the same specification we can have both a fixed and a variable consumption or contribution at the same time.

Capacity consumption or demand		Capacity contribution
Variable	Fixed	Variable	Fixed

Variable Capacity Consumption

This corresponds to the classic consumption format in a capacity specification.

$$ \mathrm{General}\ \mathrm{expression}\ \mathrm{of}\ \mathrm{consumption}:{c}_1{x}_1+{c}_2{x}_2+\dots +{c}_n{x}_n $$

(6.5)

The capacity consumption is made up of a series of variables represented as x₁, x_{2, …}, x_n. Each activity performs a consumption that is given by the expression c_ix_i where c_i is the unit consumption of activity x_i (the amount of capacity consumed by each unit of value that variable x_i takes).

Fixed Capacity Consumption or Demand

This corresponds to an attribute of the element that demands that capacity. It appears in systems where a set of elements provide capacity of a measurable element that has a stock that corresponds to the fixed capacity demand. Decisions focus on the capacity contribution, not on the amount that is consumed or demanded, which is fixed.

Fixed Capacity Contribution

An element provides a given capacity, collected as an attribute. Decisions are focused on how much of that existing capacity is consumed. The specification falls on the proprietary element of that fixed capacity.

Variable Capacity Contribution

This usually appears in specifications where a fixed capacity is demanded. The general expression corresponds to an expression similar to (6.5):

General expression of contribution: a₁y₁ + a₂y₂ + … + a_my_m

The variables y_j, j = 1…m, represent activities that provide capacity, with a_j being the unit contribution.

There is a set of elements that provide capacity to an element that demands capacity. Decisions are focused on the contribution of capacity, not on the quantity that is consumed or demanded, which is constant. The system does not collect the amount of capacity consumed on each element that contributes capacity, but it collects the amount of capacity contributed.

This case is very similar to the next type of specification, the specification of demand contribution. In any case, they are treated here independently because semantically they are different. In the specification of demand contribution, a quantity of a measurable element is demanded since it is not possessed, and some elements can contribute to it. Here, we already have a quantity of a measurable element and capacity for this is requested. Basically, it is a semantic differentiation.

The most common formats of capacity specifications are collected in Table 6.2.

Table 6.2 Most common formats in a capacity specification (Table 6.2)

Let us analyze each case.

6.4.1 Case 1: Variable Capacity Consumption and Fixed Contribution

The relationship is established between the capacity consumption of an element and the fixed amount of capacity that the element has in the system.

• Format: Consumption ≤ Capacity

• General Expression: ${\mathit{\mathsf{c}}}_{\mathsf{1}}{\mathit{\mathsf{x}}}_{\mathsf{1}}+{\mathit{\mathsf{c}}}_{\mathsf{2}}{\mathit{\mathsf{x}}}_{\mathsf{2}}+\dots +{\mathit{\mathsf{c}}}_{\mathit{\mathsf{n}}}{\mathit{\mathsf{x}}}_{\mathit{\mathsf{n}}}\le \mathit{\mathsf{K}}$

This type of specification is usually not presented explicitly in the system description, as we will see in Sect. 6.10, but the modeller must detect them from the data of the table of elements.

Illustration 6.7: Production of Butter

We have already analyzed this problem amply. The specifications that are presented are only of capacity.

• Table of Elements (Table 6.3)

Table 6.3 Table of elements

• Decision Activities

  • Action: Produce Butters

  • Decision variables: x_j = Amount of butter type j produced; j = 1,2;

• Capacity Specifications

The Whipping Machine (i = 1) has a usage time of T₁ = 6 hours which is measurable.

Variables x₁ and x₂ consume TM₁₁=3 min. and TM₁₂= 3 min.

Expressing the specification in minutes: 3x₁ + 3x₂ ≤ 360

$$ \mathrm{Parametric}:\sum \limits_{j=1}^2{\mathrm{TM}}_{1j}{x}_j\le {T}_1 $$

(6.6)

• The Pasteurization Machine (i = 2) also has a T₂ usage time:

$$ \sum \limits_{j=1}^2{\mathrm{TM}}_{2j}{x}_j\le {T}_2 $$

(6.7)

And the parameterized expression that collects (6.6) and (6.7) would be:

• $\forall i:\kern0.5em \sum \limits_{j=1}^2{\mathrm{TM}}_{ij}{x}_j\le {T}_i$

Although in this type of specification it is usually more common for consumption to be carried out by measurable activities, logical activities can also participate as consumption, as in the following illustration.

Illustration 6.8: Management of a Warehouse

Management of a warehouse in which it is necessary to place a set of Pieces (i = 1..n) in a set of Shelves (j = 1 … m). Each piece has a weight and a volume. Each shelf has a load capacity and a volume.

Capacity specifications:

Do not load a shelf with more weight than it can support.

Do not load a shelf with a total volume higher than its own.

• Table of Elements (Table 6.4)

Table 6.4 Table of elements of illustration 6.8

• Decision Activities

  • Action: Assign Pieces to Shelves

  • Decision variables: α_ij = 1 if I assign piece i to shelves j; 0 otherwise.

• Capacity Specifications

Do not load shelves with more weight than it can support: specification applied to each of the shelves

• $\forall j:\kern0.5em \sum \limits_{i=1}^n{p}_i{\alpha}_{ij}\le {\mathrm{PE}}_j$

Do not load a shelf with a total volume higher than its own: also applied to each of the shelves:

• $\forall j:\kern0.5em \sum \limits_{i=1}^n{v}_i{\alpha}_{ij}\le {\mathrm{VE}}_j$

6.4.2 Case 2: Variable Consumption with Fixed and Variable Capacity Contribution

Although it is less common, we can also find activities to increase capacity in addition to consumption. Let us take a look at the following illustration.

Illustration 6.9: Production of Pills

600 Kg of a certain drug is available to make large and small pills. We also have the possibility of buying more drugs at a price of $0.05/gram.

The big pills require 40 g and the small ones 30 g.

Each large pill provides a profit of $2 and a small one of $1.

The manufacturing capacity is 2000 pills.

• Table of Elements (Table 6.5)

Table 6.5 Table of elements of Illustration 6.9

• Decision Activities

• Action: Produce [pills]

• Decision variables: x_i = Number of pills produced of type i

• Action: Buy [drug]

• Decision variables: z = Amount of drug bought

• Capacity Specifications

(Case 2) Drug capacity: relapses on the drug. There is a capacity contribution collected in the variable z.

• $\sum \limits_{i=1}^n{c}_i{x}_i\le E+z$

(Case 1) Manufacturing capacity: applied in the system.

• $\sum \limits_{i=1}^n{x}_i\le K$

6.4.3 Case 3: Fixed Capacity Demand and Variable Capacity Contribution

There are systems where elements with capacity data and therefore acting as a resource do not individually define a capacity consumption specification. The reason is that the problem can be modelled without there being activities that measure (discretely or continuously) the consumption of that resource. The capacity attribute is not measured because it is assumed that it has either not been used or used in its entirety. The system has an element that demands a capacity, and it is necessary that other elements provide that capacity. Sometimes this specification occurs because there is a capacity attribute that is assigned to each item of a collective element. Since the instances are not treated individually but collectively, the capacity attribute cannot be used for a capacity consumption specification, since this would be applied individually on each item. The capacity attribute is used as contribution. There are also cases where the capacity attribute is held by an individual element that acts as unitary.

The format of the specification would be:

• Format: Fixed capacity demand ≤ variable capacity contribution

Let us first look at an example that illustrates the case of capacity data imputable to each item of a collective element (illustration 6.10), and a second illustration where the capacity attribute is possessed by individual elements. In this second illustration we will propose the two possible versions: measuring capacity through consumption and not measuring the capacity of each individual element, by using it logically in a capacity contribution specification (illustration 6.11).

Illustration 6.10: Celebration Hall

There is a celebration hall where a wedding will take place. The hall has tables of two sizes. There are tables of 8 seats and tables of 12 seats, 14 and 11 of them, respectively.

150 guests attend the wedding. The company must decide which tables to use so that the guests can sit down, minimizing the number of tables used.

• Table of Elements (Table 6.6)

Table 6.6 Table of elements of Illustration 6.10

Since each type of table is formed by an identical set of items and the text does not refer individually to them, the tables are configured as collective. The same happens with the guests. We make explicit the seats as element although there are no decisions about the seats but so there is a demand for seats for the guests.

Regarding the tables, there are two sets of data on capacity: availability of tables and the number of seats. The availability is applied to the element globally or collectively, while the number of seats is capacity attribute regarding each item of the collective element, so that attribute will not be associated with a specification of capacity consumption.

• Decision Activities

The system imposes the action of using tables as a decision activity. We do not need to decide where to locate the guests; we simply select tables and establish the specification of placing 150 guests, based on a certain value action corresponding to a specification of capacity demand.

• Action: Use tables

• Decision activities: x_i = Number of tables i used

• Specifications

To seat the 150 guests: We can understand the specification as the guests demanding a capacity of 150 seats. The tables act as a resource for these places. Each type of table contributes a certain number of places:

• Fixed capacity demand ≤ Variable capacity contribution

  • 150 ≤ 8x₁ + 12x₂

The capacities of the tables are being used as a contribution. The capacity refers to each item of the table.

Table availability: This attribute does give rise to a capacity consumption specification for each type of table

• ∀i : x_i ≤ N_i

• Objective Criterion

  • Min x₁ + x₂

Illustration 6.11: Containers

There is a set of n containers each with a capacity of volume and a cost. There is a liquid product with an amount of C. The objective consists in the selection of containers at a minimum cost so that we can store the quantity C of the product.

Version 1: By Capacity Consumption

In this first version, we analyze the system as a system to store liquid in containers. Therefore, the capacity data will be measured in the specifications. The liquid is a measurable element by its own continuous quantity used partially.

• Table of Elements (Table 6.7)

Table 6.7 Table of elements of Illustration 6.11 – Version 1

• Decision Activities

• Action: Store liquid product in containers

• Decision variables: x_i = amount of liquid product introduced in container i

We measure the liquid because it is the direct object of the action, “store liquid.”

• Specifications

Capacity consumption: In this scenario a capacity consumption specification is to be proposed for each container, to ensure that the quantity introduced does not exceed the capacity of the container:

$$ \forall i:{x}_i\le {K}_i $$

(6.8)

Balance specification: Although we have not yet seen the balance specifications, in the system, a balance specification is generated with the liquid availability data. The amount of liquid distributed by all the containers corresponds to the quantity Q.

$$ \sum \limits_{i=1}^n{x}_i=Q $$

(6.9)

• Objective Criterion

Since we minimize the cost of the used or selected containers, it is necessary to calculate that qualifier for the containers, which becomes a logical calculation on the containers (if you store in a container, it is because you have selected it). If we had considered it as a decision activity, that is, on the one hand store and on the other select, the implicit relationship between the two activities cannot be ignored as a specification: If I store then I select.

• Binary logical calculation: Selected container

• Applied to: Containers i=1…n

• Definition of logical variable: α_i = 1 if I select container i; 0 otherwise

• Logical proposition: $\forall i:{\mathit{\mathsf{\alpha}}}_i=1\kern0.75em \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ {x}_i>0$⇒ Ref. S_V (The selection of a container has a cost so it is useless to select containers if you do not put anything in them [Sect. 5.3.3])

$$ \Rightarrow \forall i:\mathrm{IF}\kern1em {x}_i>0\kern1em \mathrm{THEN}\kern1em {\alpha}_i=1 $$

(6.10)

In spite of not having presented the modelling of logical propositions yet, we are going to write the constraints that are generated from modelling (6.10), since it will be necessary for the simplification process between versions. The constraints generated are:

$$ \forall i:\kern1em {x}_i\le {K}_i{\alpha}_i $$

(6.11)

where K_i acts as the upper bound of what can be stored in each container.

The objective function would be:

$$ \operatorname{Min}\kern1em \sum \limits_{i=1}^n{c}_i{\alpha}_i $$

(6.12)

Version 2: By capacity contribution

In this second version, we will not introduce liquid into the containers, and therefore we will not measure at the specifications the capacity of the containers. The only thing we are going to do as a decision activity is select containers, making sure that the liquid fits. The liquid becomes unitary because we stop making a partial use of its quantity in the decision activities.

• Table of Elements (Table 6.8)

Table 6.8 Table of elements of Illustration 6.11 – Version 2

• Decision Activities

• Action: Select [Containers]

• Decision variables: α_i = 1 if I select container i; 0 otherwise.

• Specifications

• 1. Capacity contribution: The liquid element demands a capacity for its quantity. Each container i has a capacity contribution of value K_i.

$$ Q\le \sum \limits_{i=1}^n{K}_i{\alpha}_i $$

(6.13)

• Objective Criterion

Minimize costs:

$$ \operatorname{Min}\kern1em \sum \limits_{i=1}^n{c}_i{\alpha}_i $$

(6.14)

Relation Between Versions

Objective functions (6.12) and (6.14) are identical. Version 1 is equivalent to version 2 but logically larger. If we perform two simple operations, we can get to version 2 from version 1:

On the one hand, we have in Version 1:

• Modelling of the logical proposition (6.11): ∀i : x_i ≤ K_iα_i

• Capacity specification (6.8): ∀i : x_i ≤ K_i

It is only necessary to use (6.11). If I select the container (α_i=1) I cannot store more than its capacity, and if I do not select the container (α_i=0), then x_i ≤ 0 ⇒x_i = 0.

On the other hand, if we add the n constraints of (6.11), we obtain:

$$ \sum \limits_{i=1}^n{x}_i\le \sum \limits_{i=1}^n{K}_i{\alpha}_i $$

(6.15)

Substituting (6.9) with (6.15):

• $\sum \limits_{i=1}^n{x}_i=Q\le \sum \limits_{i=1}^n{K}_i{\alpha}_i$

This corresponds with (6.13), the only constraint that the first version had. In this way, it is guaranteed that at least quantity Q can be stored, and the use of decision variable x_i is not necessary.

6.5 Supply of a Demand

This is a specification which is analogous to the capacity contribution specification. It expresses a relationship between the supply of a measurable element, collective or individual, and the demand requested of that measurable element.

• Format: Measurable element supply ≥ (=) Measurable element demand

• General Expression:

• The supply is considered variable in the specification. Demand is considered both fixed and variable, although the most common case is fixed.

• ${\displaystyle \begin{array}{l}{a}_1{x}_1+{a}_2{x}_2+\dots +{a}_n{x}_n\ge D+{d}_1{y}_1+{d}_2{y}_2+\dots +{d}_m{y}_m\kern1em or\kern1em \\ {}{a}_1{x}_1+{a}_2{x}_2+\dots +{a}_n{x}_n=D+{d}_1{y}_1+{d}_2{y}_2+\dots +{d}_m{y}_m\end{array}}$

The supply is made up of a series of variables represented as x₁, x₂,…x_n

Each activity makes a contribution determined by the value of the expression: a_ix_i where a_i is the unit contribution of the variable x_i (the amount supplied by each unit of the value that takes the variable x_i).

The quantity demanded is defined as D. The variables y_j represent activities that may exist in the system to increase demand (d_j would be the unit increase in demand for each activity y_j). The supply and the demand must be expressed in the same unit of measure.

Regarding the sign of the constraint, we can find cases where only ≥ is admissible, others where only = is admissible, and others where both signs are valid. The validity is governed by the following rules:

• The expression with sign ≥ is correct when the supply involves a cost in the system or there are unit contributions other than 1.

• The expression with = is correct as long as the unit contributions are all equal to 1.

If the unit contributions are different from 1, imposing equality could make the problem inadmissible because we would not obtain values of x_i that give equality, or we would exclude solutions that could be better for the objective function. Let us analyze this validity with an illustration:

Illustration 6.12: Buying from Providers

There is a simplified system of buying a product from two providers. It is necessary to buy 1000 units of the product. The purchase cost is €3 for both providers. (We can ignore other system features).

• Table of Elements (Table 6.9)

Table 6.9 Table of elements of Illustration 6.12

• Decision Activities

• Action: Buy product from providers

• Decision variables: x_i = Product units bought from provider i

• Demand Supply Specification

There is a fixed demand D = 1000 units of the product for which we have the variable x_i as input. The unit contribution is 1. For each unit of product purchased, a unit of demand is provided.

In this case, the two signs would be valid:

• x₁ + x₂ ≥ 1000 Buying has a cost.

• x₁ + x₂ = 1000 Unitary contributions are 1.

Now we can modify the statement and incorporate the following information:

• “Provider 2 does not serve single units but serves lots of 8 units at a price of $22.”

This modifies the table of elements and the decision activity as follows:

• Table of Elements (Table 6.10)

Table 6.10 Table of elements of Illustration 6.12 modified

• Decision Activities

• Action: Buy product from provider 1 and lots from provider 2

• Events: Product ⇒ provider 1; Lot ⇒ provider 2

• Decision variables:

• x = Product units bought from provider 1

• y = Lots bought from provider 2

• Demand Supply Specification

The two decision variables, x and y, act as input, but in this case, the unit contribution of the variable y is 8 (8 units of product are contributed for each lot).

x + 8y ≥ 1000: Correct expression. Buying has a cost and the contributions are not all the units.

x + 8y = 1000: Incorrect expression. Solutions are excluded.

Obviously, if the system explicitly specifies that we must provide exactly the amount of demand, then we are obliged to use the equality sign.

6.6 Bound Imposition Specifications

Bound imposition specifications are usually the simplest to identify and model in a system. They establish lower or upper bounds for measurable activities or for variable functions (calculations). There are two types:

• Upper bound: Imposition of maximum value

• Lower bound: Imposition of minimum value

Both the capacity specifications and the demand contribution with sign ≥ can be understood as a particular case of bound specification. However, we have taken them out of this category because of the meaning they express. Bound specifications do not have to represent a concept of capacity consumption or demand supply but are impositions without defined semantics and of an explicit nature (they must be explicitly defined in the statement).

Illustration 6.13

For a system that generates the following decision variables:

• x _i = Number of product units purchased from provider Pi; i = 1 … n

The following bound specifications are defined:

• 1. Do not buy more than 50 units from provider 1: x₂ ≤ 50.

• 2. Buy at least 10 units from provider 2: x₁ ≥ 10.

• 3. Buy more than 20 units from provider 3: x₁ > 20⇒x₁ ≥ 21.

Illustration 6.14

System: A set of operators (O1, On) that work in the production of a set of substances (S1, Sm). The system measures the amount of substance produced by each operator. The number of kilos produced by operator 1 must be at least 1 kilo more than the kilos of operator 2.

• Table of Elements (Table 6.11)

Table 6.11 Elements of Illustration 6.14

• Decision Activities

• Action: Produce substances using operators

• Decision variables: x_ij = Kilos of Substance j produced by operator i

• Specifications

• Imposition: The number of kilos produced by operator 1 must be at least 1 kilo more than the kilos of operator 2:

Number of kilos produced by operator 1: Not included in the decision variables since it is an auxiliary calculation (y₁):

• ${y}_1=\sum \limits_{j=1}^m{x}_{1j}$

Number of kilos produced by operator 2:

• ${y}_2=\sum \limits_{j=1}^m{x}_{2j}$

Bound specification: a lower limit is imposed on the kilos produced by the operator 1.

• y₁ ≥ y₂ + 1

6.7 Allocation, Balance, or Equilibrium Specifications

Allocation, balance, or equilibrium specifications are all of the specifications that define:

• An exact assignment to or imposition of a value on an integer or continuous variable or on variables functions.

• Balance or equilibrium between variables or functions of variables. This includes auxiliary calculations.

Their controversy is that they can cause equivalences between auxiliary calculation and decision activity.

Illustration 6.15

For a system that generates the following decision variables:

• x _i = Number of product units purchased from provider Pi; i = 1 … n

• A. Buy 10 units from provider 1:

  x₁ = 10

• B. The sum of quantities purchased from provider 1 and 2 must be 50:

  x₁ + x₂ = 50

• C. Buy a total of 500 units:

  $\sum \limits_{i=1}^n{x}_i=500$

• D. Buy the same from provider 1 as from 3:

  x₁ = x₃

As we have said, this type of specification makes certain decision variables cease to exist because they are given a certain value (Case A) or because they become auxiliary calculations (cases B, C, D). However, if we differentiate the description of elements and activities from the specifications, we can consider them as decision variables. In any case, the system does not vary, but its structure can simply be represented in several ways.

This type of specification has greater relevance when a relationship of flow balance is expressed. This happens when a directed graph G (N, A) formed by nodes (N) and arcs (A) is established as a scenario, where a concept that corresponds to a measurable element of the system flows through the graph.

The adjective of directed graphs (Bang-Jensen and Gutin, 2000) is important since the systems that are represented as non-directed graphs (formed by nodes and edges) have a completely different meaning. An undirected graph always has a meaning of relationship or association between elements that are presented as nodes. These relationships are represented by its edges. Both nodes and edges can have associated data (Fig. 6.1).

Fig. 6.1

Directed and undirected graphs

A directed graph instead has a different meaning. The nodes are elements of the system, and the arcs are connections between nodes to enable the circulation of an added concept, the flow, in most cases. There are some scenarios where the direction has some meaning of relationship between the nodes, as dependency or offspring meanings. When there is flow, the flow is an element of the problem whose activity is to circulate through the arcs of the graph. This flow must be injected into the graph by the nodes and must also be extracted from the graph through the nodes.

The constraints of flow balance mean that the flow to arrive at a node must be equal to the flow that leaves it.

In Chap. 3 (Tables 3.46, 3.47, and 3.48), we saw three ways of representing the table of elements of a directed graph. We use Table 3.47, incorporating the flow concept (Table 6.12):

Table 6.12 Table of elements of a system with a directed graph

As a directed graph, the data of injection or flow input and demand or flow output that each node can possess have been incorporated. A node will inject flow, demand flow, or do neither of these. On the other hand, we can also find systems where injecting or demanding flow is not an attribute but a decision activity. In that case, those data would disappear.

In the system, the sum of the flow injected must always be equal to the sum of the flow demanded.

In Node Data and Arc Data, all those specific data of the system associated with nodes and arcs would be represented, respectively.

Regarding the decision activities, each system will have specific activities, but there is always the flow circulation activity in common:

• Action: Circulate [flow through the arcs]

• Participating elements: Flow C/I_M; Arcs k = 1…m;

• Quantification: Continuous

• Events: Flow ⇒ k=1…m

• Decision variables: x_k = Flow that circulates through the arc k.

In general, the constraint of equilibrium or flow balance is expressed as follows:

• Format: At each node of the graph: Sum of the Input Flow = Sum of the Output Flow

• General expression:

• $\forall i:\sum \limits_{k/{\mathrm{ND}}_{ik}=1}{x}_k+{I}_i=\sum \limits_{k/{\mathrm{NO}}_{ik}=1}{x}_k+{D}_i$

The flow x_k of all the incoming arcs in i (k/ND_ik = 1) plus the flow I_i that injects the node is recorded as input flow.

In output flow, the flow x_k of all the outgoing arcs of i (k/NO_ik = 1) plus the D_i flow demanded by the node is recorded.

We are going to differentiate two types of scenarios in which these restrictions are presented, and therefore we require the use of directed graphs:

• Explicit Case: the system itself is a directed graph on which an optimization problem is raised (shortest path, maximum flow, minimum cost flow, etc.).

• Implicit Case: this is the most interesting case. The system is not described as a graph. However, part of its activity can be represented by a directed graph. The condition for this is that there must be a measurable element, individual or collective, subject to activities in which unitary elements also participate. This acquires a greater meaning if a set of time periods participates in the system as elements. The complexity in the implicit case lies in the creation of the graph, although we will give a series of guidelines for its construction in Sect. 6.7.2.

6.7.1 Explicit Case

Within the problems associated with directed graphs, we can see one of the most known and applied, which is the shortest path problem. Let us look at an illustration of it:

Illustration 6.16: Shortest Path Problem (Dijkstra 1959)

There is a graph G (N, A) where each arc has a cost, obtaining the shortest path from a source node to a destination node. We model the problem for the graph of the figure, using Node 1 as the source node and Node 9 as destination.

Fig. 1 Directed graph G(N,A)

Nodes and arcs have been labelled with a number.

• Table of Elements

The problem uses a flow unit that will flow from node 1 to node 9. Therefore, node 1 injects a flow unit that requires node 9. Although we inject an integer amount of flow, it is not necessary to consider the flow as collective (discrete measurable), since in operative research it is demonstrated that by considering it as a continuous measurable, due to the property of unimodularity of its coefficients matrix, variables will always be integers in the optimal solution (Table 6.13).

Table 6.13 Table of elements of illustration 6.16

• Decision Activities

  • Action: Circulate flow through the arcs

  • Decision variables: x_k = Flow that circulates through the arc k.

• Specifications

Flow balance:

• $\forall i:\sum \limits_{k/{\mathrm{ND}}_{ik}=1}{x}_k+{I}_i=\sum \limits_{k/{\mathrm{NO}}_{ik}=1}{x}_k+{D}_i$

• Objective Function

• $\operatorname{Min}\kern0.5em \sum \limits_{k=1}^{12}{c}_k{x}_k$

The shortest path problem does not need any additional specification. The specification of flow balance not only guarantees the conservation of the flow but also its continuity; therefore, the set of arcs of the solution guarantees a path.

On the other hand, there are some problems associated with undirected graphs that have been modelled, transforming the graph into directed and introducing a flow concept in it. Examples include the Minimum spanning tree problem, MST (Graham and Hell 1985), or the Steiner problem (Hwang et al. 1992), as well as variants thereof. Let us consider the case of the MST problem.

Illustration 6.17: MST Problem

There is an undirected graph G (N, A), where each edge has a cost. We try to obtain the minimum cost spanning tree, that is, obtain a subgraph of G that connects all the nodes at a minimum cost.

To model this problem with the use of a directed graph, we proceed as follows:

Each edge is transformed into two arcs:

n−1 flow units are included in the problem (n = number of nodes) that will send (inject) a node, labelled as root node, to the rest of nodes of the graph. Therefore, node i will have an injection I_i = n−1, with D_i = 0, and the n−1 remaining nodes I_i = 0 and D_i = 1.

In the objective function, we consider the cost of the arcs through which the flow has circulated, so that the cost is incurred if the flow has circulated, regardless of the amount of flow that has circulated. The cost of each arc is the cost of the associated edge.

• Table of Elements (Table 6.14)

Table 6.14 Table of elements of Illustration 6.17

It is not necessary to use a binary attribute that identifies the root node, since it can be identified by the injection of n−1 flow units.

• Decision Activities

  • Action: Circulate flow through the arcs.

  • Decision variables: x_k = Flow that circulates through the arc k. k = 1…2m.

• Specifications

Flow balance:

• $\forall i:\sum \limits_{k/{\mathrm{ND}}_{ik}=1}{x}_k+{I}_i=\sum \limits_{k/{\mathrm{NO}}_{ik}=1}{x}_k+{D}_i$

• Objective Criterion

For the objective function, it is necessary to define a logical calculation on each arc to know whether or not the flow has circulated:

• Binary logical calculation: Circulate flow through an arc.

• Applied to: Arcs k=1…2m.

• Definition of logical variable:

• ∀k: 𝛼_k = 1 if the flow circulates through arc k; 0 otherwise.

• Logical proposition: ∀k : α_k = 1 IF AND ONLY IF x_k > 0 ⇒ Ref. S_V ⇒ ∀k : IF x_k > 0 THEN α_k = 1 .

• The expression of costs would be as follows:

• $\operatorname{Min}\kern0.5em \sum \limits_{k=1}^{2m}{c}_k{\alpha}_k$

6.7.2 Implicit Case

The implicit case is an optional support tool for the identification of equilibrium specifications between variables of the system. It occurs in systems where a measurable element is subjected to activities in which other no measurable individual elements participate. These activities suppose injections or demands of the measurable element and even the transfer of quantities between individual elements. This becomes even more relevant if the time element participates in the system, that is, if there is a set of periods in which the activities occur. The activities contribute, demand, or simply move units of the element over time.

In a graph, only the movement of a measurable element can be represented. If there is more than one measurable element in a system, a graph must be made for each of them.

If there are no periods of time, there is only one implicit period in which the activities take place, as already mentioned in Chap. 3. However, what does need to happen to represent the problem as a graph is that other individual elements must participate in the measurement activities.

As we have said, it is not mandatory to design a directed graph to model these systems, but it is convenient. The graph will contain the activities of the system with respect to that measurable element and the relationships between them.

The construction procedure of the graph is the following:

Nodes

We will use a node for each individual element that intervenes in the flow of units of the measurable element in each period of time, except for the time element. By default, we can use all individual elements as nodes in each period of time and afterwards eliminate those that are not connected in the final graph. There are systems where an element only participates in a certain period, and therefore its use does not make sense in other periods.

The nodes can inject or demand flow. If they are known values, they correspond to data of those elements. The sum of the flow injected must always be equal to the demanded flow. It is also possible that the node injects or demands flow, but the amount is not determined. In this case, injecting or demanding flow corresponds to decision activities or calculations. By annotating this in the graph, we will represent the injection with a negative superscript (−) and the demand with a positive superscript (+).

Arcs

In the arc activities, simple calculations and data of the measurable element are represented.

We must analyze:

• The movements of units between elements.

• The elements that maintain units over time: since the nodes cannot store units, in order to respect the principle of flow balance, the units not subject to any activity in a node must also circulate over time to the node that represents the same element in the next period. With this we achieve a circulation between nodes that is equivalent to the storage of units of the measurable element over time in that element.

Finally, once the graph has been designed, it will be necessary to explore which arcs and which auxiliary calculations define decision activities.

The design of the graph does not have to adapt to a single configuration. Depending on the interpretation of the activities over time, different designs can be generated.

From the constructed graph, a flow balance constraint is proposed on each node. This type of graph can always be refined and simplified, since nodes that have an input arc and an output arc can be discarded for the balance.

This type of graph has always been used in some optimization problems, to turn them into problems associated with directed graphs. A clear example is the transport problem, which has been modelled as a minimum cost flow problem:

Illustration 6.18: Transportation Problem (Öztürk et al. 2015)

A company has m warehouses where its products are located. Each warehouse i (i = 1…m) has a stock of Ki units. There is a set of n customers (j = 1…n) with a demand Dj of product units. The company has to supply the product demand of the customers from the warehouses. The cost of sending a product from each warehouse i (i = 1…m) to each customer j is estimated in c _ij .

• Table of Elements (Table 6.15)

Table 6.15 Elements of Illustration 6.18

We are facing a system that does not have periods of time. The measurable element is the product. We designed a graph (Fig. 6.2) with the m warehouses and the n customers:

Fig. 6.2

Implicit directed graph of Illustration 6.18

The graph will collect the admissible movements of the product units (flow), which is produced from each warehouse to each customer. Nodes associated with warehouses inject an undetermined amount of flow (y_i for warehouse i). The nodes associated with customers demand a certain amount of flow, their product demand D_j. The arcs between each warehouse and each customer include the problem decision activities (x_ij = product units that are sent from warehouse i to customer j).

The equations of flow balance generated by the graph are:

$\forall i:\kern1em {y}_i=\sum \limits_{j=1}^m{x}_{ij}$ The flow injection could be defined as an auxiliary calculation.

$\forall j:\kern1em \sum \limits_{i=1}^n{x}_{ij}={D}_j$ This corresponds with a specification of demand supply (unit contributions allow the use of the equality sign).

To finish formulating the transport problem, we would have to incorporate the capacity consumption specification at each warehouse:

• $\forall i:\kern1em \sum \limits_{j=1}^m{x}_{ij}\le {K}_i$

Objective Function

Minimize associated costs. Each decision variable has a unit cost:

• $\operatorname{Min}\kern1em \sum \limits_{i=1}^n\sum \limits_{j=1}^m{c}_{ij}{x}_{ij}$

Let us now take a look at an illustration of the implicit case in a system that considers more than a period of time. Production planning problems are included in this type of case:

Illustration 6.19: Production Planning of a Product (Larrañeta et al. 1995)

System for the production planning of a factory that produces a product for which there is a market demand for the next three months of 30, 12, and 26 units. A warehouse is available to store the manufactured units. Initially, there is a stock in the warehouse of five units.

The system must determine the quantities produced in each period as well as the quantities stored (Fig. 6.3).

• Table of Elements (Table 6.16)

Fig. 6.3

Implicit directed graph of Illustration 6.19

Table 6.16 Elements of Illustration 6.19

The three individual elements participate in the three periods.

Since the warehouse can keep units from one period to the next, we join those nodes with arcs. Labelling flow movements (Fig. 6.4):

Fig. 6.4

Labelled graph of Illustration 6.19

The nodes with an entry or injection and an exit or demand can simplify the labelling, as it is evident that for each node factory and each node market, it is fulfilled by flow balance (Fig. 6.5):

• ${\displaystyle \begin{array}{cc}{F}_i={x}_i& i=1,2,3\\ {}{E}_i={D}_i& i=1,2,3\end{array}}$

Fig. 6.5

Simplified labelled graph of Illustration 6.19

Therefore, we generate only the equations in the warehouse nodes:

• Warehouse t=1: x₁ + SI = D₁ + I₁

• Warehouse t=2: x₂ + I₁ = D₂ + I₂

• Warehouse t=3: x₃ + I₂ = D₃

• Generically: ∀t : I_t − 1 + x_t = D_t + I_t (I₀ = SI)

The flow balance equations define in themselves both the demand supply specification of the market element in each period and the auxiliary calculation of the quantity stored in each period (the action of storing is not really a decision activity but an auxiliary calculation):

Picking up the excess of units of what stays in the warehouse:

• I₁ = (SI + x₁) − D₁

• ${\displaystyle \begin{array}{l}t=2:\kern1em {I}_1+{x}_2\ge {D}_2\\ {}\kern3.5em {I}_2=\left({I}_1+{x}_2\right)-{D}_2\\ {}t=3:\kern1em {I}_2+{x}_3\ge {D}_3\\ {}\kern3.5em {I}_3=\left({I}_2+{x}_3\right)-{D}_3\end{array}}$

∀t : I_t − 1 + x_t ≥ D_t ⇒∀t : I_t − 1 + x_t − I_t = D_t

Finally, to reinforce the graph design, let us consider an example with more content:

Illustration 6.20: Food Service (Illustration 3.9.2)

A food service business has contracted three banquets for the next 3 days, requiring 150 clean tablecloths for the first banquet, 100 for the second, 140 for the third, and 130 for the fourth. Currently, it has 200 tablecloths in the storeroom, all of them clean, and they can buy what you need on the market every day at a cost of 12 m.u/tablecloth.

After the banquets, the tablecloths can go to the laundry basket or be sent to the laundry to be washed. The laundry offers the following washing services:

• Fast: Clean tablecloths for the next day, at a cost of 6 m.u/tablecloth.

• Slow: Clean tablecloths in 2 days, at a cost of 4 m.u/tablecloth.

Table of Elements (Table 6.17)

Table 6.17 Elements of Illustration 6.20

Next, we present a graph design. In the graph, we have excluded the possibility of washing slowly from the second and three periods and washing quickly from the fourth one.

On the other hand, since the injected units must be extracted from the graph, the warehouse and the laundry basket are taken as nodes that demand flow units in the last period of undetermined value.

For the flow balance we can exclude the market because it has a flow injection and a single exit arc. Similarly, the nodes that represent the fast wash and slow wash element have a single input and output and it is not necessary to propose the balance equation.

The labelling of arcs has been as follows:

• x_t: Quantity of tablecloths purchased on day t

• I_t: Quantity of tablecloths in store (clean tablecloths)

• E_t: Quantity of tablecloths brought to the banquet i = t (E_t = D_t)

• L_t: Quantity of tablecloths sent to be washed on day t

• C_t: Quantity of tablecloths taken to laundry basket on day t

• CI_t: Quantity of tablecloths in basket

• LR_t: Quantity of tablecloths washed quickly on day t

• LL_t: Quantity of tablecloths washed slowly on day t (Fig. 6.6)

Fig. 6.6

Implicit directed graph of Illustration 6.20

It would have been possible to use two elements to represent the tablecloth element: clean tablecloth and dirty tablecloth. This configuration would also have been correct in the system, but it was not necessary to make the distinction since in the decision activities the concepts are not intermingled (only clean tablecloths are bought, only dirty tablecloths are washed, etc.). The system can work with a single concept.

However, if we had made the distinction in the table of elements, we should have designed two graphs, one for each measurable element. The flow of each graph should be related later. The design would be as follows:

• Clean tablecloths (Fig. 6.7).

Fig. 6.7

Implicit directed graph for clean tablecloths

• Dirty tablecloths ( Fig. 6.8 ).

Fig. 6.8

Implicit directed graph for dirty tablecloths

The tablecloth demand D_t becomes a demand for flow in the graph of clean tablecloths and injection of flow in the graph of dirty tablecloths. With the tablecloths to be washed (LR and LL), the opposite happens.

6.8 Modelling of Propositional Logic Specifications

At the beginning of the chapter, we assigned specifications to the nature of propositions, which may be simple or compound. The simple propositions are all the typologies that we have just studied. Compound propositions are those propositions that use logical operators or connectives (If … then; If and only if; Not; Or; And; Either … or) to relate simple propositions. In this section, we focus on the modelling of compound propositions. Compound propositions are a key aspect in the formulation of optimization problems of a certain depth.

Since compound propositions are the basis of propositional logic, we shall consider the propositional logic specification as that which is formulated as a compound proposition. When using operators, we are always representing a compound proposition.

We already saw in Chap. 5 that logical calculations were defined by compound propositions, and therefore these propositions can be considered as a propositional logic specification.

Let us look at some examples of specifications and logical calculations that give rise to compound propositions:

Illustration 6.21

For a product purchasing system with five suppliers, the following decision variables are generated:

xi = units of the product purchased from the supplier i. i = 1 … 5.

Specifications that we could define:

• Logical proposition 1. – We cannot buy units from supplier 1 and supplier 2:

  “NOT (x₁>0 AND x₂>0)”

• Logical proposition 2. – If you buy more than 10 units from supplier 1 you cannot buy more than 5 units from supplier 3:

  “IF x₁>10 THEN x₃≤5”

• Logical proposition 3. – You must buy 25 units from only one of the suppliers:

  “EITHER x₁=25 OR x₂=25 OR x₃=25 OR x₄=25 OR x₅=25”

• Logical proposition 4. – If you buy more than 10 units from supplier 4 or supplier 5, you must buy 15 units from supplier 1:

  “IF x₄>10 OR x₅>10 THEN x₁=15”

• Logical proposition 5. – If the system needs a logical calculation to know from which suppliers we have purchased units:

  • Binary logical calculation: Supplier provides units

  • Applied to: Each supplier i=1…5

  • Variables: α_i = 1 if we buy units from supplier i; 0 otherwise. i=1…5

  • Logical proposition: ∀i : α_i = 1 IF AND ONLY IF x_i > 0

The difficulty of modelling logical propositions lies not so much in obtaining the constraints that define it, which as we will see in the following sections is based on the application of some rules but on correctly stating the proposition.

We have already defined the concepts related to the propositional logic in Chap. 5, when we present the logical calculations. Now we present some of these concepts with the aim of structuring their modelling. For modelling, we propose a general scheme where some rules are based on the modelling of propositions already described by authors. We emphasize as a reference the modelling of propositions described by Williams (2013).

6.8.1 Simple Propositions and Logical Operators

Atomic or simple propositions are those that are defined without the use of any logical operator. The format in a lineal formulation would be:

Left part	Sign	Right part
X (Lineal function)	< ; ≤ ; = ; ≥ ; >; ≠	Independent term (Numeric value)

In mathematical programming, we will distinguish three types of simple propositions:

• Binary simple proposition: The lineal function from the left part only takes binary values (1; 0).

• Integer simple proposition: The lineal function from the left part only takes integer values.

• Continuous simple proposition: The lineal function from the left part takes continuous values.

This distinction is necessary for the modelling of compound propositions.

In mathematical programming, any valid or admissible solution must satisfy a truth result (T). Therefore, any restriction such as those defined in Sections 6.3, 6.4, 6.5, 6.6 and 6.7 would correspond to a simple proposition, with an admissible solution of the problem being one that satisfies a truth result when applied to the simple proposition. When faced with composite propositions, where we use logical operators, the allowable solutions must satisfy the truth results of the operator's truth table. Let us see the truth tables of each operator:

• ϕ y ψ are shown as logical propositions (Table 6.18).

Table 6.18 Truth tables of logical operators

Already in Chap. 5 devoted to logical calculations, we presented equivalences between some operators. Table 6.19 collects those equivalences in addition to another with the operator Exclusive disjunction (⊕). The operator Biconditional (↔) as well as the operator Exclusive disjunction could be ignored thanks to these equivalences. However, for convenience, we will take a look at the modelling of those operators as well. From Table 6.19, we will label with references all the transformations or formulations that can be used in the modelling of propositions, in order to be able to reference the origin of the transformation in the text.

Table 6.19 Equivalences between operators

6.8.2 Reduction of Signs

For integer or continuous simple propositions, the group of signs is convenient to reduce it to the set (≤; =; ≥), except for those to which the negation operator applies. In that case, for simplicity, reduction is not necessary.

Calling X the linear function of the proposition and V the independent term or numerical value of the right part of the simple proposition, the transformation of integer/continuous propositions is the following:

ξ is a small enough value to avoid in continuous propositions that the value less than V that the linear function could take is greater than (V – ξ), in the case of X < V. The same applies for X > V.

We do not consider the case of binary atomic propositions in the reduction of signs, since the forms in which they can be presented are reduced to:

• α as a binary linear function: α = 1; α = 0;

For convenience in modelling, in the case α = 0, we can change the value to 1 using the following equivalence:

• α = 0 ⇒ 1 – α = 1; (1 – α) is still a binary expression. [Reference f₇]

6.8.3 Modelling Operators Individually

First, we are going to analyze the modelling of connectives or logical operators individually, that is, we only consider compound propositions that do not have more than one different operator.

To express the constraints resulting from modelling operators, we will distinguish between the type of value of the linear function (binary, integer, or continuous) and the sign (≤; =; ≥) for the case of integer or continuous simple propositions.

We will denote with the variables X or Y the function of the left part of an integer or continuous simple proposition. The binary propositions will be expressed with a Greek letter (α, β, ω, δ, etc.).

In the modelling of operators, the integer or continuous simple propositions will only be differentiated in the increment or decrement parameters of the independent term V, as in the case of the reduction of signs (Table 6.20). Therefore, to simplify the notation, we are going to call the increment parameter R^I and the decrement parameter R^D. They will be defined as (Table 6.21):

Table 6.20 Reduction of signs in simple propositions

Table 6.21 Increment and decrement parameters

ξ it will be a small enough value.

In the development of the modelling of some compound propositions, the definition of binary logical calculations is necessary, as we expressed in Section 5.2.3 of the previous chapter. These logical calculations serve to collect the result of simple propositions that are within the compound proposition. They will be collected in binary variables denoted by ω or by δ¹, δ², δ³, and δ⁴, when necessary. With these calculations we are going to ignore this semantic and mathematical definition. The proposition that defines them mathematically is integrated within the formulation of the operator.

On the other hand, for any integer or continuous atomic proposition, it will be necessary to obtain an upper bound and a lower bound of the linear function. The upper bound is a value that is never surmountable by the function. Equivalently, the lower bound is a value that can never be exceeded inferiorly by the linear function. Any value of dimension will be valid in the modelling, although adjusting the upper bound to the maximum of the linear function and the lower one to the minimum reduces the space of solutions and usually offers better behavior in the resolution. If X is our integer or continuous function, we will denote its dimensions with the following parameters:

• Upper bound of X: UB_X

• Lower bound of X: LB_X

6.8.3.1 Negation Operator (NOT; ¬)

Negation operator modelling does not require any complex modelling exercise; it is just based on representing the opposite proposition. We show the case of whole or continuous propositions; for binary propositions, the application of the connective negation is something evident (Table 6.22).

Table 6.22 Negation operator modelling

6.8.3.2 Conditional Operator (IF … THEN … ; →)

The modelling of the conditional operator will be separated into two tables. In Table 6.24, we will present the modelling of the connective when the proposition of input of the condition is binary. In Table 6.25, we will deal with the modelling options when the input and output propositions are integer or continuous.

The nomenclature used in both Tables 6.24 and 6.25 is shown in Table 6.23.

Table 6.23 Nomenclature

Table 6.24 Conditional operator modelling with binary input proposition

Table 6.25 Conditional operator modelling with integer/continuous input proposition

Whenever possible, we should avoid the signs of equality in simple propositions. If the independent term corresponds to a lower bound of X, we can replace it with the sign ≤ ([Reference f_LB]). Similarly, if it corresponds to an upper bound, we can work with the sign ≥ ([Reference f_UB]).

Any combination of types of propositions not contemplated in the two previous tables can easily be deduced with the use of the equivalences Ref. f₃ and Ref. f₇.

The tables could have been further reduced, since we can change the sign ≥ to the sign ≤ simply by multiplying the proposition by −1. Even equality corresponds to two propositions of sign ≥ and ≤ with the connective AND, but I prefer this representation to facilitate the obtaining of the mathematical formulation without having to change the propositions too much.

Let us take a look at some illustrations:

Illustration 6.22

We have x₁, x₂, x₃ integer variables ≥ 0.

We also have α₁ and α₂ binary variables.

• IF α₁=1 THEN x₁+x₂ ≤ 10 ⇒ Ref. f₁₄ [α = α₁; X = x₁+x₂; V=10] ⇒

• ⇒ ${x}_1+{x}_2\le 10+\left({UB}_{x_1+{x}_2}-10\right)\left(1-{\alpha}_1\right)$

• IF α₁ = 0 THEN α₂ = 0 ⇒ Ref. f₇ ⇒ IF 1−α₁ = 1 THEN 1−α₂ =1

• ⇒ Ref. f₁₃ ⇒ 1 − α₁ ≤ 1 − α₂

• IF α₂ = 0 THEN x₁ > 10 ⇒ Ref. f₅ ⇒ IF α₂ = 0 THEN x₁ ≥ 10 ⇒ Ref. f₇ ⇒

• ⇒ IF 1−α₂ = 1 THEN x₁ ≥ 11 ⇒ Ref. f₁₅ ⇒ ${x}_1\ge 11{\alpha}_2+{LB}_{x_1}\left(1-{\alpha}_2\right)$⇒[${LB}_{x_1}=0$]

• ⇒x₁ ≥ 11α₂

• IF x₁ > 5 THEN x₂ ≤ 3 ⇒ Ref. f₅ ⇒ IF x₁ ≥ 6 THEN x₂ ≤ 3 ⇒ Ref. f₁₈ ; f₂₀ ⇒

• ⇒ ${\displaystyle \begin{array}{l}{x}_1\ge 6\omega +{LB}_{x_1}\left(1-\omega \right)\\ {}{x}_1\le 5\left(1-\omega \right)+{UB}_{x_1}\omega \\ {}{x}_2\le 3+\left({UB}_{x_2}-3\right)\left(1-\omega \right)\end{array}}$ ⇒ [${LB}_{x_1}=0$] ⇒ ${\displaystyle \begin{array}{l}{x}_1\ge 6\omega \\ {}{x}_1\le 5\left(1-\omega \right)+{UB}_{x_1}\omega \\ {}{x}_2\le 3+\left({UB}_{x_2}-3\right)\left(1-\omega \right)\end{array}}$

• IF x₁ + x₃ ≥ 10 THEN α₁ =1 ⇒ Ref. f₃

• ⇒ IF NOT (α₁ =1) THEN NOT (x₁ +x₃≥ 10) ⇒

• ⇒ IF α₁ = 0 THEN NOT (x₁+ x₃ ≥ 10) ⇒ Ref. f₁₁ ⇒ IF α₁ = 0 THEN x₁+ x₃ ≤ 9 ⇒ Ref. f₇ ⇒ IF 1−α₁ = 1 THEN x₁+x₃ ≤ 9 ⇒ Ref. f₁₄ ⇒

• ⇒${x}_1+{x}_3\le 9+\left({UB}_{x_1+{x}_3}-9\right)\left(1-\left(1-{\alpha}_1\right)\right)$ ⇒ ${x}_1+{x}_3\le 9+\left({UB}_{x_1+{x}_3}-9\right){\alpha}_1$

• IF x1−x2 = 5 THEN x3 ≥ 1 ⇒ Ref. f19; f21 ⇒

• $\Rightarrow \kern0.5em {\displaystyle \begin{array}{l}{x}_1-{x}_2\le 5+\left({UB}_{x_1-{x}_2}-5\right)\left(1-\omega \right)\\ {}{x}_1-{x}_2\ge 5\omega +{LB}_{x_1-{x}_2}\left(1-\omega \right)\\ {}{x}_1-{x}_2\le 4{\delta}_1+{UB}_{x_1-{x}_2}\omega +{UB}_{x_1-{x}_2}{\delta}_2\\ {}{x}_1-{x}_2\ge 6{\delta}_2+{LB}_{x_1-{x}_2}\omega +{LB}_{x_1-{x}_2}{\delta}_1\\ {}{\delta}_1+{\delta}_2=1-\omega \\ {}{x}_3\ge 1\omega +{LB}_{x_3}\left(1-\omega \right)\end{array}}$

6.8.3.3 Biconditional Operator (IF AND ONLY IF; ↔)

Following the same format as for the conditional, the modelling tables are the following (Tables 6.26 and 6.27):

Table 6.26 Biconditional connective modelling with binary propositions

Table 6.27 Biconditional connective modelling with integer/continuous propositions

6.8.3.4 Disjunction Operator (OR; ˅)

If there are two or more atomic propositions joined with the operator OR:

ϕ_i, i=1,2,…, n: ϕ₁ OR ϕ₂ OR … OR ϕ_n

Modelling follows two steps:

• 1. We define a logical calculation (ω_i) for each atomic proposition ϕ_i that is integer or continuous (not binary), to know when the proposition is fulfilled. However, it is not necessary to control the two output values of the calculation, which would have been formulated as ϕ_i ↔ ω_i =1. To simplify the modelling, we just need to pick up the value of ω_i when the proposition is not fulfilled:

  ∀i/ϕ_i ∈ Z ∨ ϕ_i ∈ ℜ : IF NOT (ϕ_i)THEN ω_i = 0

By equivalence f₃, we can also define it as:

∀i/ϕ_i ∈ Z ∨ ϕ_i ∈ ℜ : IF ω_i = 1 THEN ϕ_i [Reference f₃₃]

• 2. A quantitative selection specification is incorporated for the defined ω_i and the binary propositions (i/ϕ_i ϵ{0,1}: α_i =1*):

• $\sum \limits_{i/{\phi}_i\in \Re \vee {\phi}_i\in \mathrm{Z}}{\omega}_i+\sum \limits_{i/{\phi}_i\in \left\{0,1\right\}}{\alpha}_i\ge 1$ [Reference f₃₄]

where it is required that at least one proposition be fulfilled.

*: If the binary proposition were defined with value 0, by equivalence f₇, we transform it into value 1.

Illustration 6.23

We have x₁, x₂ continuous variables ≥ 0.

We also have α₁ and α₂ binary variables.

Proposition: x₁ ≤ 10  ∨ x₂ ≥ 4 ∨ α₁ = 1 ∨ α₂ = 0 ⇒ Ref. f₁₄ ⇒

⇒x₁ ≤ 10  ∨ x₂ ≥ 4 ∨ α₁ = 1 ∨ (1 − α₂) = 1

Model:

• 1. Logical calculations [Ref. f₃₃]:

• IF ω₁ = 1 THEN x₁≤ 10 ⇒ Ref. f₁₄ ⇒${x}_1\le 10+\left({\mathrm{UB}}_{x_1}-10\right)\left(1-{\omega}_1\right)$

• IF ω₂ = 1 THEN x₂ ≥ 4 ⇒ Ref. f₁₅ ⇒${x}_2\le 4{\omega}_2+{\mathrm{LB}}_{x_2}\left(1-{\omega}_2\right)$⇒ ${\mathrm{LB}}_{x_2}=0$

• ⇒x₂ ≤ 4ω₂

• 2. Quantitative selection specification [Ref. f₃₄]:

• ω₁ + ω₂ + α₁ + (1 − α₂) ≥ 1

6.8.3.5 Conjunction Operator (AND; ˄)

When we have a compound proposition where only the disjunction operator appears, it is not necessary to perform any modelling processes. Each atomic proposition corresponds to a restriction in the model.

Instead, the conjunction operator within compound proposals with more operators needs a modelling process, which we will see in Sect. 6.8.4.

6.8.3.6 Exclusive Disjunction Operator (EITHER … OR…;⊕)

If there are two or more atomic propositions joined with the operator ⊕ :

• ϕ_i , i =1,2,…, n: ϕ₁ ⊕ ϕ₂ ⊕ … ⊕ ϕ_n

Modelling follows two steps:

• 1. Similar to step 1) of the connective DISJUNCTION (OR), but in this case the logical calculation must be defined as:

  ∀i/ϕ_i ∈ Z ∨ ϕ_i ∈ ℜ : ϕ_i ↔ ω_i = 1 [Reference f₃₅]

• 2. A quantitative selection specification is incorporated:

  $\sum \limits_{i/{\phi}_i\in \Re \vee {\phi}_i\in \mathrm{Z}}{\omega}_i+\sum \limits_{i/{\phi}_i\in \left\{0,1\right\}}{\alpha}_i=1$ [Reference f₃₆]

This means that one and only one atomic proposition can be fulfilled.

6.8.4 Modelling Compound Propositions with Various Operators

Compound propositions can join several atomic propositions using different operators. Examples can be the following:

Illustration 6.24: Compound Propositions with Several Operators

• EITHER ((x₁≥20 AND y₁≤10) OR α = 1

• ((x₁≥20 AND y₁≤10) OR NOT (x₃ ≥ 20))

• IF ((x₁≥20 OR y₁≤10) THEN NOT (α = 1 AND β =1)

• ((x₁≥20 AND y₁≤10) IF AND ONLY IF (α = 1 OR β =1)

• … .

The modelling process of a compound proposition with several operators is done from the lowest level in the structure of the proposition to the highest level. The level is determined by the priority of the operators, according to the structure of parentheses. The lower the level, the higher the execution priority of the operator.

The process will always end with a proposition that has only one type of operator and that will be modelled as defined in Sect. 6.8.3.

We call ψ the proposition that is part of the original compound proposition and in which only one operator type appears. The modelling process of ψ depending on the operator is as follows.

6.8.4.1 Negation Operator (NOT;¬):

The result of the negation operator modelling replaces ψ with ¬ψ in ϕ, but does not incorporate additional constraints into the model.

Illustration 6.25

• ϕ: EITHER (x₁≥8 AND x₂≤10) OR NOT(y≥10)

• ψ= NOT(y≥10)

• Model of ψ: ⇒Ref. f₁₁ ⇒ (y≤9) [we consider y as integer]

• Result: EITHER (x₁≥8 AND x₂≤10) OR (y≤9)

6.8.4.2 Disjunction Operator (OR;˅) and Exclusive Disjunction (EITHER… OR…;⊕):

The step 1 of the exclusive disjunction operator described for the cases in which the operator appears individually is modelled (Sect. 6.8.3.6.). This is:

• ψ = (ψ₁ ˅ ψ₂ ˅ … ˅ ψ_i ˅ …)

• or

• ψ = (ψ₁ ⊕ ψ₂ ⊕ … ⊕ ψ_i ⊕ …)

• ∀_i/ψ_i ∈ Z ∨ ψ_i ∈ ℜ : ψ_i ← ω_i = 1 [Reference f₃₅]

The constraint resulting from step 2 of the modelling process (Section 6.8.3.4 for disjunction operator and Section 6.8.3.6 for exclusive disjunction operator) is not incorporated as a constraint to the model, but instead replaces ψ in ϕ. With this we reduce operators of the original proposition ϕ.

Illustration 6.26

• ϕ: EITHER (x₁≥8 OR x₂≤10) OR (y≤9) [x₁, x₂ integers]

• ψ = (x₁≥8 OR x₂≤10)

• Model of ψ:

$$ {\displaystyle \begin{array}{l}\Rightarrow {\mathrm{f}}_{35}\Rightarrow {\omega}_1=1\mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\;{x}_1\ge 8\Rightarrow \\ {}\Rightarrow {\mathrm{f}}_{25}\Rightarrow {x}_1\ge 8{\omega}_1+\mathrm{LB}{x}_1\left(1-{\omega}_1\right)\end{array}} $$

(6.16)

$$ \Rightarrow {x}_1\le 7\left(1-{\omega}_1\right)+\mathrm{UB}{x}_1{\omega}_1 $$

(6.17)

$$ {\displaystyle \begin{array}{l}\Rightarrow {\mathrm{f}}_{35}\Rightarrow {\omega}_2=1\mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\;{x}_2\le 10\\ {}\Rightarrow {\mathrm{f}}_{24}\Rightarrow {x}_2\le 10+\left(\mathrm{UB}{x}_2-10\right)\left(1-{\omega}_2\right)\end{array}} $$

(6.18)

$$ \Rightarrow {x}_2\ge 11\left(1-{\omega}_2\right)+{\mathrm{LBx}}_2{\omega}_2 $$

(6.19)

(6.17), (6.18), (6.19), and (6.20) are constraints that are incorporated into the model.

• Result: ⇒ f₃₄ ⇒ EITHER (ω₁ + ω₂ ≥ 1) OR (y≤9)

The modelling for this could be carried out as described in Sect. 6.8.3.6.

6.8.4.3 Conjunction Operator (AND; ˄)

This operator had not been used individually for the obvious reasons that there was no need for any modelling exercise. However, within a proposal with more operators, it operates in a similar way to the OR and EITHER OR operators:

• $\psi =\left({\psi}_1\wedge {\psi}_2\wedge \dots \wedge {\psi}_{\mathrm{i}}\wedge \dots \wedge {\psi}_n\right)$

• ∀i/ψ_i ∈ Z ∨ ψ_i ∈ ℜ : ψ_i ↔ ω_i = 1 [Reference f₃₅]

2. An expression ϕ₀ is created with the following format:

• ${\phi}_{0:}\sum \limits_{i/{\psi}_i\in \Re \vee {\psi}_i\in \mathrm{Z}}{\omega}_i+\sum \limits_{i/{\psi}_i\in \left\{0,1\right\}}{\alpha}_i\ge n\kern1em \left[\mathrm{Reference}\ {\mathrm{f}}_{37}\right]$

Replacing ψ with ϕ₀ in ϕ.

Illustration 6.27

ϕ: EITHER (x₁≥8 AND x₂≤10 AND β =0) OR (y≤9) [x₁, x₂ integers; β binary]

ψ= (x₁≥8 AND x₂≤10 AND β =0)

Model of ψ:

$$ \Rightarrow {\mathrm{f}}_{35}\Rightarrow {\omega}_1=1\leftrightarrow {x}_1\ge 8\Rightarrow {f}_{25}\Rightarrow {x}_1\ge 8{\omega}_1+\mathrm{LB}{x}_1\left(1-{\omega}_1\right) $$

(6.20)

$$ \Rightarrow {x}_1\le 7\left(1-{\omega}_1\right)+\mathrm{UB}{x}_1{\omega}_1 $$

(6.21)

$$ \Rightarrow {\omega}_2=1\leftrightarrow {x}_2\le 10\Rightarrow {\mathrm{f}}_{24}\Rightarrow {x}_2\le 10+\left(\mathrm{UB}{x}_2-10\right)\left(1-{\omega}_2\right) $$

(6.22)

$$ \to {x}_2\ge 11\left(1-{\omega}_2\right)+\mathrm{LB}{x}_2{\omega}_2 $$

(6.23)

(6.20), (6.21), (6.22), and (6.23) are constraints that are incorporated into the model.

• ϕ₀: ω₁ + ω₂ + (1−β) ≥ 3

• Result: ⇒ f₃₇ ⇒ EITHER (ω₁ + ω₂ + (1−β) ≥ 3) OR (y≤9)

The modelling for this could again be carried out as described in Sect. 6.8.3.6.

6.8.4.4 Conditional and Biconditional Operators

The constraints resulting from operator modelling replace ψ.

Let π_1… π_r be constraints resulting from operator modelling

Proposition (π₁ AND π₂ AND … AND π_r) replaces ψ in ϕ.

Illustration 6.28

ϕ: EITHER x₁≥8 OR (IF x₁ + x₂ ≥8 THEN β = 1)

ψ = (IF x₁ + x₂ ≥8 THEN β = 1)

Model of ψ:

$$ {\displaystyle \begin{array}{l}\Rightarrow {\mathrm{f}}_3\Rightarrow \mathrm{IF}\beta =0\;\mathrm{THEN}\;{x}_1+{x}_2<8\\ {}\Rightarrow {\mathrm{f}}_7;{\mathrm{f}}_4\Rightarrow \mathrm{IF}\;1-\beta =1\;\mathrm{THEN}\;{x}_1+{x}_2\le 7\\ {}\Rightarrow {\mathrm{f}}_{14}\Rightarrow {x}_1+{x}_2\le 7+\left({\mathrm{UB}}_{x1+x2}-7\right)\left(1-{\omega}_1\right)\end{array}} $$

(6.24)

(6.24) replaces ψ in ϕ:

EITHER x₁≥8 OR x₁ + x₂ ≤7 + (UB_{x1 + x2} −7)(1−ω₁)

The modelling for this could again be carried out as described in Sect. 6.8.3.6.

A couple of illustrations to express the complete process.

Illustration 6.29

$$ \phi :\mathrm{IF}\ \left({x}_1\ge 20\ \mathrm{OR}\ {y}_1\le 10\right)\ \mathrm{THEN}\ \mathrm{NOT}\ \left(\alpha =1\ \mathrm{OR}\ \beta =0\right) $$

$$ \left[{x}_1,{y}_1\ \mathrm{integers},\alpha\ \mathrm{and}\ \beta\ \mathrm{binaries}\right] $$

$$ \Rightarrow {\mathrm{f}}_{7;}\ {\mathrm{f}}_{34}\Rightarrow \mathrm{IF}\ \left({x}_1\ge 20\ \mathrm{OR}\ {y}_1\le 10\right)\ \mathrm{THEN}\ \mathrm{NOT}\ \left(\alpha +\left(1-\beta \right)\ge 1\right) $$

$$ \Rightarrow {\mathrm{f}}_{11}\Rightarrow \mathrm{IF}\ \left({x}_1\ge 20\ \mathrm{OR}\ {y}_1\le 10\right)\ \mathrm{THEN}\ \alpha +\left(1-\beta \right)\le 0 $$

$$ \Rightarrow {\mathrm{f}}_{35}\Rightarrow {\omega}_1=1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ {x}_1\ge 20 $$

$$ \Rightarrow {\mathrm{f}}_{25}\Rightarrow {x}_1\ge 20{\omega}_1+\mathrm{LB}{x}_1\left(1-{\omega}_1\right) $$

(6.25)

$$ \Rightarrow {x}_1\le 19\left(1-{\omega}_1\right)+{UBx}_1{\omega}_1 $$

(6.26)

$$ \Rightarrow {\mathrm{f}}_{35}\Rightarrow {\omega}_2=1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ {y}_1\le 10 $$

$$ \Rightarrow {\mathrm{f}}_{24}\Rightarrow {y}_1\le 10+\left(\mathrm{UB}{y}_1-10\right)\left(1-{\omega}_2\right) $$

(6.27)

$$ \Rightarrow {y}_1\ge 11\left(1-{\omega}_2\right)+{LBy}_1{\omega}_2 $$

(6.28)

$$ \Rightarrow {\mathrm{f}}_{34}\kern0.5em \Rightarrow \mathrm{IF}\ {\omega}_1+{\omega}_2\ge 1\ \mathrm{THEN}\ \alpha +\left(1-\beta \right)\le 0\Rightarrow $$

$$ \Rightarrow \mathrm{IF}\ {\omega}_1+{\omega}_2\ge 1\ \mathrm{THEN}\ \alpha -\beta \le -1 $$

$$ \Rightarrow {\mathrm{f}}_{18}\Rightarrow {\omega}_1+{\omega}_2\ge \omega $$

(6.29)

$$ \Rightarrow {\omega}_1+{\omega}_2\le 2\omega $$

(6.30)

$$ \Rightarrow {\mathrm{f}}_{20}\Rightarrow \alpha -\beta \le -1+2\left(1-\omega \right) $$

(6.31)

Therefore, the starting proposition is modelled with a total of seven constraints (6.25–6.31).

Illustration 6.30

$$ \phi :\mathrm{EITHER}\ \left({x}_1\ge 1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ \alpha =1\right)\ \mathrm{OR}\ \left({x}_2\ge 1\ \mathrm{AND}\ {x}_3\ge 1\right) $$

$$ \left({x}_1,{x}_2,{x}_3\ge 0\ \mathrm{integers},\alpha\ \mathrm{binary}\right) $$

$$ \Rightarrow {\mathrm{f}}_{35}\Rightarrow {\omega}_1=1\kern0.5em \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\kern0.5em {x}_2\ge 1 $$

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{25}\mathbf{\Rightarrow}{x}_2\ge {\omega}_1 $$

(6.32)

$$ \mathbf{\Rightarrow}{x}_2\le \kern0.5em \mathrm{UB}{x}_2\ {\omega}_1 $$

(6.33)

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{35}\mathbf{\Rightarrow}{\omega}_2=1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ {x}_3\ge 1 $$

$$ \mathbf{\Rightarrow}\kern0.5em {\mathrm{f}}_{25}\mathbf{\Rightarrow}{x}_3\ge {\omega}_2 $$

(6.34)

$$ \mathbf{\Rightarrow}\kern0.5em {\mathrm{f}}_{25}\mathbf{\Rightarrow}{x}_3\le \kern0.5em \mathrm{LB}{x}_3{\omega}_2 $$

(6.35)

$$ \Rightarrow {\mathrm{f}}_{37}\Rightarrow \mathrm{EITHER}\ \left({x}_1\ge 1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ \alpha =1\right)\ \mathrm{OR}\ \left({\omega}_1+{\omega}_2\ge 2\right) $$

$$ \mathbf{\Rightarrow}\mathrm{Ref}.{\mathrm{f}}_{25}\kern0.5em \mathbf{\Rightarrow}{x}_1\ge \alpha $$

$$ \mathbf{\Rightarrow}\mathrm{Ref}.{\mathrm{f}}_{25}\kern0.5em \mathbf{\Rightarrow}{x}_1\le \kern0.5em {\mathrm{UB}}_{x1}\ \alpha $$

$$ \mathbf{\Rightarrow}\phi :\mathrm{EITHER}\ \left({x}_1\ge \alpha \kern0.5em \mathrm{AND}\ {x}_1\le {\mathrm{UB}}_{x1}\ \alpha \right)\ \mathrm{OR}\ \left({\omega}_1+{\omega}_2\ge 2\right) $$

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{35}\kern0.5em \mathbf{\Rightarrow}{\omega}_3=1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ {x}_1\ge \alpha $$

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{25}\mathbf{\Rightarrow}{x}_1-\alpha \kern0.5em \ge -\left(1-{\omega}_3\right) $$

(6.36)

$$ \mathbf{\Rightarrow}{x}_1-\alpha \kern0.5em \le -\left(1-{\omega}_3\right)+{\mathrm{UB}}_{\mathrm{x}1}{\omega}_3 $$

(6.37)

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{35}\kern0.5em \mathbf{\Rightarrow}{\omega}_4=1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ {x}_1\le {\mathrm{UB}}_{x1}\ \alpha $$

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{24}\mathbf{\Rightarrow}{x}_1-{\mathrm{UB}}_{x1}\alpha \le {\mathrm{UB}}_{x1}\left(1-{\omega}_4\right) $$

(6.38)

$$ \mathbf{\Rightarrow}{x}_1-{\mathrm{UB}}_{x1}\alpha \kern0.5em \ge \left(1-{\omega}_5\right)-{\mathrm{UB}}_{x1}{\omega}_4 $$

(6.39)

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{37}\kern0.5em \mathbf{\Rightarrow}\mathrm{EITHER}\ \left({\omega}_3+{\omega}_4\ge 2\right)\ \mathrm{OR}\ \left({\omega}_1+{\omega}_2\ge 2\right) $$

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{35}\kern0.5em \mathbf{\Rightarrow}{\omega}_5=1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ {\omega}_3+{\omega}_4\ge 2 $$

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{25}\mathbf{\Rightarrow}{\omega}_3+{\omega}_4\ge 2{\omega}_5 $$

(6.40)

$$ \mathbf{\Rightarrow}\kern0.5em {\mathrm{f}}_{25}\mathbf{\Rightarrow}{\omega}_3+{\omega}_4\le \left(1-{\omega}_5\right)+2{\omega}_5 $$

(6.41)

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{35}\kern0.5em \mathbf{\Rightarrow}{\omega}_6=1\ \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\ {\omega}_1+{\omega}_2\ge 2 $$

$$ \mathbf{\Rightarrow}\kern0.5em {\mathrm{f}}_{25}\mathbf{\Rightarrow}{\omega}_1+{\omega}_2\ge 2{\omega}_6 $$

(6.42)

$$ \mathbf{\Rightarrow}\kern0.5em {\mathrm{f}}_{25}\mathbf{\Rightarrow}{\omega}_1+{\omega}_2\le \left(1-{\omega}_6\right)+2{\omega}_6 $$

(6.43)

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{36}\mathbf{\Rightarrow}{\omega}_5+{\omega}_6=1 $$

(6.44)

(6.32) to (6.44) are incorporated as constraints to the model.

Regardless of this methodology, which is sufficient for the modelling of any proposition, we can also make use of the distributive law between propositions in order to present the concatenation of propositions in a different way:

If we have ϕ, ψ, and σ propositions, the distributive laws between expressions are defined as:

• ${\displaystyle \begin{array}{l}\phi \vee \left(\psi \wedge \sigma \right)\equiv \left(\phi \vee \psi \right)\wedge \left(\phi \vee \sigma \right)\kern1.50em \left[\mathrm{Reference}\ {\mathrm{f}}_{38}\right]\\ {}\phi \wedge \left(\psi \vee \sigma \right)\equiv \left(\phi \wedge \psi \right)\vee \left(\phi \wedge \sigma \right)\kern1.50em \left[\mathrm{Reference}\ {\mathrm{f}}_{39}\right]\end{array}}$

It is also possible to divide conditional propositions when they are at the highest level of the compound proposition:

We have ϕ₁, ϕ₂, …, ϕ_n, ϕ_m propositions:

• IF ϕ₁ v ϕ₂ v … v ϕ_n THEN ϕ_m ⇒

• ⇒ IF ϕ₁ THEN ϕ_m

• ⇒ IF ϕ₂ THEN ϕ_m [Reference f₄₀]

• ⇒ …

• ⇒ IF ϕ_n THEN ϕ_m

• IF ϕ_m THEN ϕ₂ ˄ ϕ₂ ˄ … ˄ ϕ_n ⇒

• ⇒ IF ϕ_m THEN ϕ₁

• ⇒ IF ϕ_m THEN ϕ₂ [Reference f₄₁]

• ⇒ …

• ⇒ IF ϕ_m THEN ϕ_n

6.8.5 Data as Propositions

Sometimes and whenever the specification refers to one or more sets of elements, we can propose propositions where the wording includes, among its atomic propositions, conditions on element data values. Let us take a look at some simple examples in the following illustration.

Illustration 6.31

There is a system for allocating distribution hubs to supermarkets. We have n hubs and m supermarkets. The distance between hubs and supermarkets and the demand of each supermarket is known. The system has the following specifications:

• 1. If the distance between a supermarket and a hub exceeds 50Km, the supermarket cannot be assigned to the hub.

• 2. If a supermarket has a demand higher than 1000 kgs, it will be assigned two hubs.

• 3. If hub 2 is assigned a supermarket, the supermarket should be less than 1 km away.

• 4. If a supermarket assigned to a hub exceeds the distance of 30 km, the hub will be limited to a maximum of ten supermarkets.

• Table of Elements (Table 6.28)

Table 6.28 Elements of Illustration 6.31

• Decision Activities

• Action: Allocate hubs to supermarkets

• Decision variables: α_ij = 1 if I allocate Hub i to Supermarket j; 0 otherwise.

• Specifications

The four specifications of the system are enunciated as conditional logical propositions. Let us take a look at this statement:

• 1. If the distance between a supermarket and a hub exceeds 50 km, the supermarket cannot be assigned to the hub.

If we apply it to any supermarket and any hub:

• ∀i,j: IF D_ij > 50 THEN α_ij=0

• 2. If the supermarket has a demand higher than 1000 kgs, it will be assigned two hubs.

If we apply it to any supermarket:

• $\forall j:\mathrm{IF}\kern0.5em {M}_j>1000\kern0.5em \mathrm{THEN}\kern1em \sum \limits_{i=1}^n{\alpha}_{ij}=2$

• 3. If hub 2 is allocated to a supermarket, the supermarket must be less than 1 km away.

If we apply it to any supermarket:

• ∀j: IF α_2j=1 THEN D_2j< 1

• 4. If a supermarket assigned to a hub exceeds the distance of 30 km, the hub will be limited to a maximum of 10 supermarkets.

If we apply it to any supermarket and any hub:

$\forall i,j:\mathrm{IF}\kern0.5em {\alpha}_{ij}=1\kern0.5em \mathrm{AND}\kern0.5em {D}_{ij}>1000\kern1em \mathrm{THEN}\kern1em \sum \limits_{j=1}^m{\alpha}_{ij}\le 10$

This casuistry does not imply an additional modelling exercise and the rules previously seen should not be followed. It is only necessary to extract the atomic propositions associated with data of the global proposition and include it as a condition of the elements on which the specification falls.

Let us call the data propositions with the term P_At, whether they are one or several data joined by operators.

We first distinguish the case of propositions with operators individually:

Let ϕ be a proposition of variables (Table 6.29).

Table 6.29 Model of propositions with data

In the case of several operators, references f₃₈, f₃₉, f₄₀, and f₄₁ must be used and operate as follows:

• 1. If the conditional operator or the biconditional operator does not exist in the upper level:

  1.1 If necessary, the distributive law (Ref. f₃₈ and f₃₉) is applied until obtaining a union of propositions of the form:

  (ϕ₁ OR P_At1) AND (ϕ₂ OR P_At2) AND …

  1.2. For each compound proposition united with the Operator AND, the following specification is created:

  Ref. f₄₂ ⇒ ∀ element/NOT(P_At1): ϕ₁

• 2. If the conditional operator exists in the upper level:

  2.1. If necessary, apply Ref. f38 and f39 until obtaining a proposal of the form:

• IF ϕ₁ OR P_At1 OR (ϕ₂ AND P_At2) OR (ϕ₃ OR P_At3) OR … THEN ψ

• Ref. f₄₀ ⇒ IF ϕ₁ THEN ψ ⇒ …

IF PAt1THEN ψ ⇒ Ref. f45 ⇒∀ element/PAt1: ψ

IF (ϕ2 AND PAt2) THEN ψ ⇒∀ element/ PAt2: IF ϕ2 THEN ψ

IF (ϕ3 OR PAt3) THEN ψ ⇒∀ element/ NOT(PAt3): IF ϕ THEN ψ

⇒ ∀ element/P_At3: ψ

…

Next, we model the propositions of Illustration 6.31.

Illustration 6.32: Modelling the propositions of 6.31

• (1)

• ∀i,j : IF D_ij > 50 THEN α_ij=0

• ⇒ f₄₅ ⇒ ∀i,j/D_ij > 50: α_ij=0

• (2)

• $\forall j:\mathrm{IF}\kern0.5em {M}_j>1000\kern1em \mathrm{THEN}\kern1em \sum \limits_{i=1}^n{\alpha}_{ij}=2$

• ⇒ f₄₅ ⇒ ∀j/M_j > 1000: $\sum \limits_{i=1}^n{\alpha}_{ij}=2$

• (3)

• ∀j: IF α2j=1 THEN D2j< 1

• ⇒ f₃ ⇒ ∀j: IF NOT (D2j< 1) THEN NOT(α2j=1) ⇒ IF D2j≥ 1 THEN α2j= 0

• ⇒ f₄₅ ⇒ ∀j/D2j≥ 1: α2j=0

• (4)

• $\forall i,j:\mathrm{IF}\kern0.5em {\alpha}_{ij}=1\kern0.5em \mathrm{AND}\kern0.5em {D}_{ij}>1000\kern1em \mathrm{THEN}\kern1em \sum \limits_{k=1}^m{\alpha}_{ik}\le 10$

• ${\displaystyle \begin{array}{l}\Rightarrow \forall i,j:\mathrm{IF}\kern0.5em \left(\forall i,j/{D}_{ij}>1000:{\alpha}_{ij}=1\right)\kern1em \mathrm{THEN}\kern1em \sum \limits_{k=1}^m{\alpha}_{ik}\le 10\\ {}\Rightarrow \forall i,j/{D}_{ij}>1000:\mathrm{IF}\kern0.5em {\alpha}_{ij}=1\kern0.5em \mathrm{THEN}\kern1em \sum \limits_{k=1}^m{\alpha}_{ik}\le 10\end{array}}$

• ⇒ Ref. f₁₄ $\Rightarrow \forall i,j/{D}_{ij}>1000:\sum \limits_{k=1}^m{\alpha}_{ik}\le 10+\left(m-10\right)\left(1-{\alpha}_{ij}\right)$

6.8.6 Logical Propositions That Express Possibility

When the statement of a system refers to possibilities not subject to conditions, no specification is really being established unless some additional imposition is expressed (e.g., “you can buy at most 10 units”). In most cases, possibilities only serve to establish associations between elements to form activities. The verb we use when talking about possibilities is the verb “can.” Let us look at an example:

“Provider A can supply units of product 1”: The statement does not generate any constraint. It is established that provider A participates in the supply of product 1 action.

“Provider B can supply more than 50 units of product 2”: The statement does not create any constraint. It is established that provider B participates in the supply of product 2 action.

If any limitation is included in the statement, then it may be necessary to establish a specification:

“Provider B can only supply product 1.”

In those cases, it is necessary to model the specification by expressing the statement of impossibility, about what cannot be done: If the supplier can only supply product 1, then it cannot supply product 2.

If the possibility statement is part of a logical proposition because it has a condition or is described with any logical connective, then it is necessary to model that proposition in all cases. For the modelling of this type of logical proposition, it is necessary to rephrase the proposition to express it in negative. It is about converting the proposition of possibility into a proposition of impediment. Let us see some illustrations:

• 1. “Provider A can supply units of product 1 if provider B does not supply units of that product”: When there is a simple proposition within the compound proposition that expresses possibility, we rephrase the statement to express it as an impediment:

  “Provider A cannot supply units of product 1 if supplier B does not supply supplies units of that product”

• 2. “Provider B can supply more than 50 units of product 2 if provider A supplies more than 10 units of product 1”:

  “Provider B cannot supply more than 50 units of product 2 if provider A supplies more than 10 less than 11 units of product 1”

The logical process is simple. The verb “can” expresses possibility. The opposite, “cannot,” expresses that there is no possibility, but both are not disjunctive. Being able to perform an action includes doing it and not doing it. Not being able to do it expresses only the option of not doing it. That is why it is necessary to model the expression that imposes a specification, which is the negative.

Let’s take a look at an illustration based on a mathematical environment.

Illustration 6.33

There is a system of assigning workers to tasks. We have 15 tasks and 4 operators. The tasks have a duration time. Two specifications are established in the assignment:

• An operator can carry out more than two tasks if he partially performs a task

• The working time of an operator may be more than 10 hours in the case of doing more than 3 tasks.

Based on the description it is clear that the tasks are divisible in the system, because they can be partially carried out by several operators, so they have a measurable character. It is a statement that lacks a description of other norms and an objective; in this case we will only focus on the two specifications indicated.

• Table of Elements (Table 6.30)

Table 6.30 Elements of Illustration 6.33

• Decision Activities

• Action: Assign [tasks to Operators]

• Decision variables: x_ij = Amount of time of Task i assigned to Operator j.

• Specifications

• 1. An operator can carry out more than two tasks if he partially performs a task

The specification refers to each operator j=1…4.

First, it is necessary to express the calculation of the number of tasks performed by an operator as an auxiliary calculation that will use a logical calculation to know if an operator has been assigned to each task:

• Binary logical calculation: Operator assigned to task

• Applied to: Each Operator j=1…4 and each task i=1…15

• Variables: α_ij = 1 if operator j is assigned to task i; 0 otherwise. i=1…15; j=1…4

• Logical proposition: ∀i, ∀ j : α_ij = 1 IF AND ONLY IF x_ij > 0

The number of tasks performed by each operator can be expressed by an auxiliary calculation:

• Auxiliary calculation: Number of tasks performed by each operator

• Applied to: Each operator j=1…4

• Variables: y_j = number of operator tasks j

• Constraints that define the calculation:

• $\forall j:\kern1em {y}_j=\sum \limits_{i=1}^{15}{\alpha}_{ij}$

Second, we also have to create a logical calculation to know if an operator has partially carried out a task:

• Binary logical calculation: Operator partially performs a task

• Applied to: Each Operator j=1…4 and each task i=1…15

• Variables:

• β_ij = 1 if the operator j partially performs task i; 0 otherwise. i=1…15; j=1…4

• Logical proposition:

• ∀i, ∀ j : β_ij = 1 IF AND ONLY IF x_ij > 0  AND x_ij < D_i

We could also create an auxiliary calculation for collecting the total number of partially performed tasks:

• Auxiliary calculation: Number of tasks partially performed by an operator

• Applied to: Each Operator j=1…4

• Variables: z_j = number of partial tasks of the operator j

• Constraints that define the calculation:

• $\forall j:\kern1em {z}_j=\sum \limits_{i=1}^{15}{\beta}_{ij}$

We return to the starting specification:

• “An operator can carry out more than two tasks if he partially completes a task”

And we express it in negative:

• “An operator cannot perform more than two tasks if he does not partially do any task”⇒ “If an operator does not partially do any task, he cannot perform more than two tasks”

Mathematically:

• ∀j : IF z_j = 0 THEN y_j ≤ 2

• 2. The working time of an operator may be more than 10 hours in the case of doing more than three tasks.

Working time can be collected in an auxiliary calculation:

• Auxiliary calculation: Working time of an operator

• Applied to: Each Operator j=1…4

• Variables: w_j = Working time of operator j

• Constraints that define the calculation:

• $\forall j:\kern1em {w}_j=\sum \limits_{i=1}^{15}{x}_{ij}$

We express the specification as an impediment:

• “The working time of an operator cannot exceed 10 hours in the case of performing no more than three tasks” ⇒

• ⇒ “If you perform at most three tasks, the working time of an operator cannot exceed 10 hours”

Mathematically:

• ∀j : IF y_j ≤ 3 THEN w_j ≤ 10

6.9 Objective Criterion

The objective function is the criterion that guides the search for solutions. Defining an objective function in the system results in the complete definition of an optimization problem. As we discussed in the introductory chapter, the illustrations will focus on problems with a single objective function. However, the typologies and modelling of the functions that we will explain below can also serve to develop multiobjective problems or simply to create a function that integrates diverse weighted functions.

Once a criterion has been defined, all the costs, positive or negative (profits), of the activities and calculations that participate in that function will be expressed in the objective function. Therefore, the objective function can be used a priori to identify decision activities or calculations, since any action that entails a cost will correspond to a decision activity or calculation.

The normal or most usual situation in a system is that the unit cost of an activity represented in a variable does not vary whatever the value of the variable. For example, let x be the decision activity associated with buying units from a supplier and let c be the cost of a unit. Typically, the cost c is the cost associated with the purchase of units, regardless of the value of x. The total cost of that activity will be cx. This will happen as long as the variable is binary, since it only takes 2 values (Value 0, no cost; Value 1, cost c). Therefore, the objective function is usually the simplest specification of the system in most cases. It is enough to identify which variables have cost data with respect to the proposed objective.

However, there are problems in which for a generic variable x, integer or continuous, the cost that is applied may depend on the value that variable x takes. The cases that may arise are:

• 1. The cost of variable x depends on the range of values on which the variable falls

• 2. The cost of variable x depends on the value that another variable takes

• 3. The cost depends on the deviation of the variable with respect to reference threshold.

We explain and illustrate below the modelling of each of the cases. Some of the ideas have been based on the modelling presented by Sarker and Newton (2007).

6.9.1 Cost According to Interval of Values

With a variable x, we define a set of n intervals (U_i−1, U_i] i=1…n, U_i ≥ 0 i=0…n, and a cost c_i associated with each interval (Fig. 6.9).

Fig. 6.9

Value intervals

Since we need to know on what interval (U_i−1, U_i], i=1 … n the variable x has fallen, it is necessary to define logical calculations, but first, to unify the modelling process, and it is also necessary to define the closed intervals for each cost value. The first interval corresponds to [U₀, U₁]. From the second interval, the first value is determined by U_i−1+A (A = 1 if x is integer, A = ξ if x is continuous). To unify the intervals, we define n intervals [U_i−1+B, U_i], where B = 0 if i=1, B=A if i> 1.

• Binary logical calculation: x belongs to the interval [U_i−1+B, U_i]

• Applied to: Each interval i=1…n

• Variables:

• ${\alpha}_i=\left\{\begin{array}{l}1\kern1em \mathrm{if}\ x\in \left[{U}_{i-1}+B,{U}_i\right]\ \\ {}0\kern1em \mathrm{otherwise}\end{array}\right.$

• Logical proposition:

• ∀i : α_i = 1 IF AND ONLY IF x ≥ U_i − 1 + B AND x ≤ U_i 

• Model:

• ⇒f₃₅ ⇒  ∀ i : ω_i1 = 1 IF AND ONLY IF x ≥ U_i − 1 + B

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{25}\mathbf{\Rightarrow}x\ge \left({U}_{i-1}+\mathrm{B}\right){\omega}_{i1}+{\mathrm{LB}}_x\ \left(1-{\omega}_{i1}\right) $$

(6.45)

$$ \mathbf{\Rightarrow}{\mathrm{f}}_{25}\mathbf{\Rightarrow}x\le \left({U}_{i-1}+B-1\right)\left(1-{\omega}_{i1}\right)+{\mathrm{UB}}_x\ {\omega}_{i1} $$

(6.46)

$$ \Rightarrow {\mathrm{f}}_{35}\Rightarrow \forall i:{\omega}_{i2}=1\kern1em \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\kern0.5em x\le {U}_i $$

$$ \Rightarrow \kern0.5em {\mathrm{f}}_{24}\Rightarrow x\le {U}_i+\left({\mathrm{UB}}_x-{U}_i\right)\left(1-{\omega}_{i2}\right) $$

(6.47)

$$ \Rightarrow \kern0.5em {\mathrm{f}}_{24}\Rightarrow x\ge \left({U}_{i+1}\right)\left(1-{\omega}_{\mathrm{i}2}\right)+{\mathrm{LB}}_x{\omega}_{i2} $$

(6.48)

$$ \Rightarrow {\mathrm{f}}_{37}\Rightarrow \forall i:{\alpha}_i=1\kern0.5em \mathrm{IF}\ \mathrm{AND}\ \mathrm{ONLY}\ \mathrm{IF}\kern0.5em {\omega}_{i1}+{\omega}_{i1}\ge 2 $$

$$ \Rightarrow {\mathrm{f}}_{25}\Rightarrow \forall i:{\omega}_{i1}+{\omega}_{i1}\ge 2{\alpha}_i $$

(6.49)

$$ \Rightarrow {\mathrm{f}}_{25}\Rightarrow \forall i:{\omega}_{i1}+{\omega}_{i1}\le 1+{\alpha}_i $$

(6.50)

In addition, we need a non-binary logical calculation that collects the value of x in each interval in order to maintain the linearity when expressing the cost in the objective function. Only with the variables α_i,, the definition of the cost of x depending on the interval would be defined as:

• $\sum \limits_{i=1}^n{c}_i{\alpha}_ix$

So, we would have a non-linear expression. To avoid this, we must pick up the value of x, according to the interval on which it falls. The calculation would be:

• Non-binary logical calculation: Collect the value of x in each interval [U_i−1+B, U_i]

• Applied to: Each interval i=1…n

• Variables:

• ${x}_i=\left\{\begin{array}{l}x\kern1em \mathrm{if}\ {\alpha}_{\mathrm{i}}=1\\ {}0\kern1em \mathrm{if}\ {\alpha}_{\mathrm{i}}=0\end{array}\right.$

• Logical propositions: ∀i: IF α_i = 1 THEN x_i = x

• ∀i: IF α_i = 0 THEN x_i = 0

• Model:

$$ \forall i:\mathrm{IF}{\alpha}_i=1\ \mathrm{THEN}\kern0.5em {x}_i=x\Rightarrow {\mathrm{f}}_{16}\Rightarrow \forall i:x\le {x}_i+{\mathrm{UB}}_x\left(1-{\alpha}_i\right) $$

(6.51)

$$ \Rightarrow \forall i:x\ge {x}_i $$

(6.52)

$$ \forall :\mathrm{IF}{\alpha}_i=0\ \mathrm{THEN}\kern0.5em {x}_i=0\Rightarrow {\mathrm{f}}_7\Rightarrow \forall i:\mathrm{IF}\ 1-{\alpha}_i=1\ \mathrm{THEN}\kern0.5em {x}_i=0 $$

$$ \Rightarrow {\mathrm{f}}_{16}\Rightarrow \forall i:{x}_i\le {U}_i{\alpha}_i $$

(6.53)

$$ \Rightarrow {\mathrm{f}}_{16}\Rightarrow \forall i:{x}_i\ge 0 $$

(6.54)

The expression of the objective function that collects the cost of the variable x would be defined as:

• $\sum \limits_{i=1}^n{c}_i{x}_i$

Simplification of Constraints

Proposition ∀i : α_i = 1 IF AND ONLY IF x ≥ U_i − 1 + B AND x ≤ U_i  can be simplified by Ref. S_V taking advantage of the characteristics of the variables. The variable x cannot fall onto more than one interval, without imposing it as a condition. That means that it would suffice to impose the relationship between α_i and x:

$$ \mathrm{Only}\kern0.5em \mathrm{variable}\kern0.5em {\alpha}_i\kern0.5em \mathrm{will}\kern0.5em \mathrm{take}\kern0.5em \mathrm{value}\kern0.5em 1:\sum \limits_{i=1}^n{\alpha}_i=1 $$

(6.55)

$$ \forall i:\mathrm{IF}\ {\alpha}_i=1\kern1em \mathrm{THEN}\kern1em x\ge {U}_{i-1}+B\kern0.5em \mathrm{AND}\kern0.5em x\le {U}_i $$

Model:

$$ {\displaystyle \begin{array}{c}\Rightarrow {\mathrm{f}}_{41}\Rightarrow \forall i:\mathrm{IF}\ {\alpha}_i=1\kern1em \mathrm{THEN}\kern0.5em x\ge {U}_{i-1}+B\kern0.5em \\ {}\forall i:\mathrm{IF}\ {\alpha}_i=1\kern1em \mathrm{THEN}\kern0.5em x\le {U}_i\end{array}} $$

$$ \Rightarrow {\mathrm{f}}_{15}\Rightarrow \forall i:x\ge \left({U}_{i-1}+B\right)\kern0.5em {\alpha}_i $$

(6.56)

$$ \Rightarrow {\mathrm{f}}_{14}\Rightarrow \forall i:x\le {U}_i{\alpha}_i+{UB}_x\left(1-{\alpha}_i\right) $$

(6.57)

In addition to (6.55), (6.56), and (6.57), we should also include (6.51), (6.52), (6.53), and (6.54) to complete the modelling, although even (6.51) and (6.52) can also be substituted for a single equality function:

$$ x=\sum \limits_{i=1}^n{x}_i $$

(6.58)

Since with the proposition “IF α_i = 0 THEN x_i = 0”, all x_i take value 0 minus one, that index i for which α_i = 1. By imposing (6.58), the x_i that does not take value 0 will automatically take the value of x.

Illustration 6.34

In a purchase system, we have a supplier that offers the following prices for the product:

• $16 if we buy a maximum of 100 pcs.

• $15 if we buy more than 100 pcs.

• $14 if we buy more than 500 pcs.

If x is the variable associated with the activity of purchasing units of the product from that supplier, the cost of x is determined by the interval in which x falls:

The constraints generated by determining the cost would be:

• By (6.53) ⇒${\displaystyle \begin{array}{l}{x}_1\le 100{\alpha}_1\kern1em \\ {}{x}_2\le 500{\alpha}_2\\ {}{x}_3\le {UB}_x{\alpha}_3\end{array}}$

• By (6.55) ⇒α₁ + α₂ + α₃ = 1

• By (6.56) and (6.57)⇒ $\left|\begin{array}{l}x\ge 1{\alpha}_1\\ {}x\le 100{\alpha}_1+{UB}_x\left(1-{\alpha}_1\right)\\ {}x\ge 101{\alpha}_2\\ {}x\le 500{\alpha}_2+{UB}_x\left(1-{\alpha}_2\right)\\ {}x\ge 501{\alpha}_3\\ {}x\le {UB}_x\end{array}\right|$

• By (6.58) ⇒ x = x₁ + x₂ + x₃

In the objective function, we would introduce the cost terms:

• Min … + 16x₁ + 15x₂ + 14x₃ + …

6.9.2 Cost According to the Value of Another Variable

Although the variable that determines the cost is integer or continuous, it will be reduced to depend on the value of one or more binary variables. The modelling is almost identical to the previous case.

Let y be the variable that determines the cost of x, y integer or continuous. Generally, the cost of x will depend on the range of values in which y falls (Fig. 6.10).

Fig. 6.10

Value intervals for variable y

To know in which interval [U_i−1 + B, U_i] i = 1…n the value of y has fallen, we can just define a logical calculation for each interval in the following way:

• Binary logical calculation: y belongs to the interval [U_i−1+B, U_i]

• Applied to: Each interval i=1…n

• Variables:

• ${\alpha}_i=\left\{\begin{array}{l}1\kern1em \mathrm{if}\ y\in \left[{U}_{i-1}+B,{U}_i\right]\\ {}0\kern1em \mathrm{otherwise}\end{array}\right.$

• Logical propositions: As in the reduction of Sect. 6.9.1, it is not necessary to define the two values of α_i, but only impose that:

• Only a α_i will take value 1:

$$ \sum \limits_{i=1}^n{\alpha}_i=1 $$

(6.59)

• ⇒ Ref. S_V ⇒∀i : IF α_i = 1 THEN y ≥ U_i − 1 + B AND y ≤ U_i

• Model:

$$ {\displaystyle \begin{array}{l}\Rightarrow {\mathrm{f}}_{41}\Rightarrow \forall i:\mathrm{IF}\ {\alpha}_i=1\kern1em \mathrm{THEN}\kern0.5em y\ge {U}_{i-1}+B\kern0.5em \\ {}\kern2.4em \forall i:\mathrm{IF}\ {\alpha}_i=1\kern1em \mathrm{THEN}\kern0.5em y\le {U}_i\end{array}} $$

$$ \Rightarrow {\mathrm{f}}_{15}\Rightarrow \forall i:y\ge \left({U}_{i-1}+B\right)\kern0.5em {\alpha}_i $$

(6.60)

$$ \Rightarrow {\mathrm{f}}_{14}\Rightarrow \forall i:y\le {U}_i{\alpha}_i+{UB}_y\left(1-{\alpha}_i\right) $$

(6.61)

• Variables α_i will determine the cost of x:

• With α₁=1, the cost of x = c₁

• With α₂=1, the cost of x = c₂

• …

If the starting variable y had been binary, the previous process would not be necessary, we would simply continue from this moment, since:

• With y = 1 (α₁ = y), the cost of x = c₁

• With y = 0 ⇒ f₇ ⇒ 1−y = 1 (α₂ =1−y), the cost of x = c₂

To model this process, it is sufficient to collect the value of x in one variable for each possible cost value:

• Non-binary logical calculation: Collect the value of x according to α_i

• Applied to: Each interval i=1…n

• Variables:

• ${x}_i=\left\{\begin{array}{l}x\kern1em \mathrm{if}\ {\alpha}_{\mathrm{i}}=1\\ {}0\kern1em \mathrm{if}\ {\alpha}_{\mathrm{i}}=0\end{array}\right.$

• Logical propositions:

• IF α_i = 1 THEN x_i = x

• IF α_i = 0 THEN x_i = 0

• Model: (identical to that expressed in 6.9.1) Resulting expressions: (6.51), (6.52), (6.53), and (6.54). Similarly, (6.51) and (6.52) can be reduced to (6.58).

The expression of the objective function that collects the cost of variable x would be defined as:

• $\sum \limits_{i=1}^n{c}_i{x}_i$

Illustration 6.35

In a purchase system, we have a product whose purchase cost depends on whether we have signed a contract with the supplier. That contract implies a cost C. The price of the product unit is $c ₁ with the signing of the contract and $c ₂ without the contract.

The system would have two decision activities:

• Buy product from the supplier

• Sign contract with supplier

This would generate the variables:

• x = Product units purchased from the supplier.

• β = 1 If I sign a contract with the supplier; 0 otherwise.

• The cost of x depends on the value taken by the variable β

• β = 1 ⇒ Cost of x = c₁

• β = 0 ⇒ 1− β = 1 ⇒ Cost of x = c₂

• Constraints generated are:

• By (6.53): ${\displaystyle \begin{array}{l}{x}_1\le {\mathrm{UB}}_x\beta \\ {}{x}_2\le {\mathrm{UB}}_x\left(1-\beta \right)\end{array}}$

• By (6.58): x = x₁ + x₂

In the objective function we would include the cost of signing the contract and the cost of purchasing units:

• Min … + Cβ + c₁x₁ + c₂x₂ + …

6.9.3 Costs Depending on the Deviation of the Variable

In some situations, a reference value can be imposed on the values of a variable, so that we can be interested in the approach of the variable to that reference value or we are interested in distancing from it. The distance from this reference is not imposed as a specification in the problem, but the variable has freedom, penalizing or rewarding the deviation on the reference value in the objective function.

The bonuses or penalties imposed affect the units deviated from the reference value.

The following table summarizes all the possibilities that may arise (Table 6.31):

Table 6.31 Cases of deviation

6.9.3.1 Penalty by Excess

Given

• U: Reference value (attribute or variable)

• p: unit penalty (attribute)

• Affected variable: x

• Auxiliary variables:

  x_d: Deviated units by default of x over U

  x_e: Deviated units by excess of x over U

These variables come from defining a free auxiliary variable y, collecting the difference between U and x: x + y = U. In order to use variables ≥ 0, we perform the change of variables: y = x_d − x_e, x_d ≥ 0 and x_e ≥ 0, and the resulting constraint would be:

• x + x_d − x_e = U

Although that expression would allow values to be given simultaneously to x_d and x_e, this would never occur even in the best case of the problem since the excess implies a cost, and therefore it is important that x_e be as low as possible.

In the objective function, the cost term p x_e is included.

Illustration 6.36

Within a sales system, we have a customer to whom we offer the following prices for the product:

• $16 for the first 100 units purchased

• $15 for units that exceed 100 units.

The affected variable would be the quantity sold of product units to the customer, which we call x.

The reference value is U = 100

The company suffers a penalty for excess, p = $1 ($16−$15)

Having defined x_d and x_e, this means that:

• x + x_d − x_e = 100

In the objective function we incorporate the terms of the profit of the sale x and the penalty:

• Max … + 16x − 1x_e

Being a function of maximizing, the penalty has a minus sign because it is a cost.

6.9.3.2 Bonus by Excess

Given

• U: Reference value (attribute or variable)

• b: unit bonus (attribute)

• Affected variable: x

• Auxiliary variables:

• x_d: Deviated units by default of x over U

• x_e: Deviated units by excess of x over U

• Binary variables from logical calculations:

• α_d: x_d>0 IF AND ONLY IF α_d =1

• α_e: x_e>0 IF AND ONLY IF α_e =1

Constraints:

In this case it would not be worth imposing only x + x_d − x_e = U, since it interests the greatest possible value of x_e, so that x_d and x_e would grow to infinity simultaneously. Therefore, the logical calculations are defined to know if x_d and x_e have become positive and then it is imposed that both cannot be made positive simultaneously.

Simplifying the definition of the logical calculations to:

• α_d: IF x_d>0 THEN α_d =1

• α_e: IF x_e>0 THEN α_e =1

The resulting constraints of this process are:

• ${\displaystyle \begin{array}{l}x+{x}_d-{x}_e=U\\ {}{x}_d\le U\ast {\alpha}_d\\ {}{x}_e\le \left({UB}_x-U\ast \right){\alpha}_e\\ {}{\alpha}_d+{\alpha}_e\le 1\end{array}}$

* If the reference value U is a variable, we have to use another upper bound for x_d and x_e in the modeling process.

In the objective function, the profit term bx_e is incorporated and x would enter in the function with its base cost.

Illustration 6.37

Within a purchasing system, we have a supplier that offers the following prices for the product:

• $16 for the first 100 units purchased

• $15 for units that exceed 100 units.

The affected variable would be the purchased quantity of product units to the supplier, which we call x.

The reference value is U = 100

The bonus for excess is b = $1 ($16−$15)

Having defined x_d, x_e, α_d and α_e, this means that:

• ${\displaystyle \begin{array}{l}x+{x}_d-{x}_e=100\\ {}{x}_d\le 100{\alpha}_d\\ {}{x}_e\le \left({\mathrm{UB}}_x-100\right){\alpha}_e\\ {}{\alpha}_d+{\alpha}_e\le 1\end{array}}$

In the objective function we incorporate the terms of the cost of x and the bonus

• Min … + 16x − 1x_e

that in a minimizing function would have a minus sign because it is a profit.

6.9.3.3 Penalty by Default

Equivalent to Sect. 6.9.3.1.

Given

• U: Reference value (attribute or variable)

• p: Unit penalty (attribute)

• Affected variable: x

• Auxiliary variables:

• x_d: Deviated units by default of x over U

• x_e: Deviated units by excess of x over U

• Constraint: x + x_d − x_e = U

The objective function incorporates the cost term px_d

Illustration 6.38

In a system of production and sale of product units we have signed with a customer to supply 1000 units per month, so that if we do not meet that supply we have a penalty of $P for each unit not delivered.

There is a default penalty with a reference number of U = 1000 units.

The affected variable would be the quantity supplied to the customer, which we call x.

The default penalty, p = $P

Having defined x_d, x_e this means that:

• x + x_d − x_e = 1000

In the objective function we would incorporate the penalty:

• Min … + Px_d + …

6.9.3.4 Bonus by Default

Equivalent to Sect. 6.9.3.2.

• ${\displaystyle \begin{array}{l}x+{x}_d-{x}_e=U\\ {}{x}_d\le U{\alpha}_d\\ {}{x}_e\le \left({UB}_x-U\right){\alpha}_e\\ {}{\alpha}_d+{\alpha}_e\le 1\end{array}}$

If the reference value U is a variable, we have to use another upper bound for x_d and x_e in the modeling process.

In the objective function, the benefit term bx_d is incorporated.

Illustration 6.39

After the Kyoto protocol, the state proposes bonuses on the gas emissions of our company in the case of not exceeding the A kg/year, meliorating with $A for each Kg/year deviated by default.

6.10 Identification of Specifications

The specifications of a system include the standards and operation regulations declared within it.

From the statement or description of the system, the first task for modelling involves the identifying of specifications. Extracting the specifications of a system consists of identifying all the declared norms, both those that are presented explicitly in the statement and those that are assumed from the nature of the elements and activities and do not have an explicit description.

Norms that appear explicitly in the description are easy to identify and one only has to look for verbs of imposition or logical propositions. Those that are found implicitly in a system, without there being the need to declare them, are specifications that are based on data of elements, quantitative selection rules, logical conditions between activities, impositions of flow balance, or bounds of measurable activities:

• Based on data: attributes that express a continuous or integer magnitude of intrinsic capacity, availability, or demand on a collective or measurable element always have a specification associated with capacity consumption, capacity contribution, demand or balance, depending on the system operation. These specifications may not be defined as such, only the attribute. The same happens with relational data between elements, for example, of incompatibility of some action, that probably define constraints regarding decision activities, but they are not made explicit because they are defined with the attribute itself.

• Quantitative selection rules: many systems assume without making explicit the norms that define the quantitative selection specifications for certain logic decision activities between sets of elements. Therefore, it will be necessary to analyze if there are selection rules on each of the elements that participate in the activity (Sect. 6.3).

• Logical conditions between activities: sometimes definitions of decision activities have an implicit relationship between them defined by a logical proposition. This does not mean that any activity represents a calculation, but some of the values of one variable condition the value of another.

When a variable defines a calculation, all its values are obtained from the values of other variables, or they are negligible values in the system. The logical conditions between activities also occur when we identify a logical calculation as a decision activity. By not defining it as a calculation, we ignore the logical proposition that defines it. This logical proposition cannot be ignored from the model, and it would be represented as a specification.

• Bounds of discrete measurable activities: they appear in measurable decision activities in which there is an upper bound of measurement of the activity, individually generally, but also jointly with other measurable activities, without this information being explicitly included in the statement.

• Flow balance constraints: in the system, equilibrium relationships between activities and calculations are established, when there are measurable elements and generally over a set of time periods, and these restrictions are assumed in the operation of the system without these relationships being explicit.

The modeller must analyze the following aspects in the identification of specifications:

• The data of elements that can refer to capacity, availability, or demand, fundamentally

• The selection rules in decision activities

• The decision activities identified in the system in case there is any implicit relationship between them or if any of them were really a logical calculation

• Balance relationships between variables

• The upper bound of discrete measurable activities

The description of a system should always avoid wrong interpretations, so it is desirable that the number of implicit specifications be as low as possible, with all the details indicated in the statement, although some are obvious.

Let’s look at some examples of identifying specifications in systems.

Illustration 6.40: Assigning objects to positions (Romero and Romeijn 2005)

There is a set of n objects and m positions, m> n. Each object has a weight. Each position has a maximum weight supported. It is about assigning objects to positions. There is a cost involved in assigning each object to each position. It is about minimizing the cost of the assignment.

• Table of Elements (Table 6.32)

Table 6.32 Elements of Illustration 6.40

• Decision Activities

Action: Assign objects to positions

Decision variables:

α_ij =1 if I assign Object i to Position j; 0 otherwise. i=1…n, j=1…m

• Specifications

The statement does not present any explicit specification. All specifications are given implicitly in the description:

• Specifications I1. Based on data: each position has a capacity attribute, the maximum weight supported; therefore, it will be necessary to define a consumption specification in this case on each position.

• Constraints:

• $\forall j:\sum \limits_{i=1}^n{p}_i{\alpha}_{ij}\le {M}_j$

• Specifications I2. Quantitative selection rules: the activities of the system are logic; therefore, it will be necessary to analyze which are the quantitative norms in the selection (Table 6.33):

Table 6.33 Selection diagram

The most logical analysis is to assume that an object occupies exactly one position. If it could occupy more than one position, it should have been specified in the statement. And that amount is mandatory and does not act as a higher level, since you must place all objects. Therefore, there is an implicit selection rule for each object. Regarding the positions, there is no rule.

Logically with any position, we can always impose as an upper bound all objects and as a lower bound no objects, but those specifications would not be necessary and therefore are not defined.

• Specifications I3. Logical conditions between activities: there are no relationships between activities, since there is only one activity.

• Specifications I4. Bounds of discrete measurable activities: there are no discrete measurable activities.

• Specifications I5. Flow balance constraints: they do not exist.

Illustration 6.41: Ham distribution

A ham distribution company has designed a set of 20 delivery routes for distribution. The company has a portfolio of 350 customers. Each delivery route goes through a series of known customers.

The company has ten vehicles for the distribution. Each vehicle has a given capacity or number of Iberian hams that it can transport.

The demand for ham is known from each customer and must be attended to. Each vehicle that delivers Iberian hams must choose a single route, because more than one would take too long. We know the delivery cost of each route.

• Table of Elements (Table 6.34)

Table 6.34 Elements of Illustration 6.41

In the Route_Customer attribute, customers of each route are annotated. It is therefore shared between routes and customers.

Decision Activities

• Action: Deliver Iberian hams with vehicles to customers.

• Decision variables:

• x_kj = Number of Iberian hams delivered with vehicle k to customer j.

• k=1…10, j=1…350

• Action: Choose routes for vehicles.

• Decision variables:

• α_ik =1 if I choose Route i for Vehicle k; 0 otherwise. k=1…10, i=1…20

Explicit Specifications

This statement does present explicit impositions:

• “The demand for ham from each customer is known and must be attended to”: It is an imposition of demand contribution. The specification refers to satisfying a demand, so if that imposition had not been explicitly specified, it would have been logical to identify it implicitly.

• Constraints:

• $\forall j:\sum \limits_{k=1}^{10}{x}_{kj}={D}_j$

Unitary contributions validate the equality sign

• “Each vehicle that delivers Iberian hams must choose a single route”: Explicitly, a selection rule is being presented for each vehicle in the activity of choosing a route (Table 6.35):

Table 6.35 Selection diagram of decision activity “Choose routes for vehicles”

Note that it would be a mistake to assume that the route selection rule for each vehicle would be equal to 1, since we would assign a route to each vehicle. The specification states that a route is chosen for each vehicle that distributes, so we cannot consider that everyone will perform the delivery.

In addition, the phrase “each vehicle that delivers” brings light to an implicit specification existing in the problem, a logical condition between activities (I3).

Implicit Specifications

• Specifications I1. Based on data: each vehicle has a capacity attribute, the number of Iberian hams that can be transported; therefore it will be necessary to define a capacity consumption specification for each vehicle. Each customer also has a demand attribute that will give rise to a demand contribution specification, although we have already mentioned that it is given explicitly.

  Constraints: $\forall k:\sum \limits_{j=1}^{350}{x}_{jk}\le {K}_k$

• Specifications I2. Quantitative selection rules: the selection rule for each vehicle with respect to routes appears explicitly.

• Specifications I3. Logical conditions between activities: as mentioned, between the two decision activities there is a logical condition reflected in the phrase “Each vehicle that delivers ham slices must choose only one route.” This phrase refers to the fact that in order for a vehicle to distribute ham, it must have a route assigned to it. If we do not assign a route, it will not distribute Iberian hams.

Logical proposition: If a vehicle delivers ham, then it must have been assigned a route.

(If a vehicle delivers ham to a customer then it must have been assigned a route)

Logical proposition with mathematical formulation:

• ∀k,j: IF x_kj> 0 THEN $\sum \limits_{i=1}^{20}{\alpha}_{ik}=1$

In addition to this, it is necessary to contemplate that it is not worth assigning any route, but only one that passes by the customer to whom it delivers:

Logical proposition: If a vehicle delivers Iberian hams to a customer, then the vehicle must have assigned a route that passes by that customer.

Logical proposition with mathematical formulation:

• ∀k,j: IF x_kj> 0 THEN$\sum \limits_{i/{RC}_{ij}=1}{\alpha}_{ik}=1$

This second logical proposition encompasses the previous one, since if it is fulfilled the previous one is fulfilled, so we can omit the first one.

• Specifications I4. Bounds of discrete measurable activities: Measurable activities do not have a given upper bound.

• Specifications I5. Flow balance constraints: The measurable activities participate in specifications that have already been reflected.

Illustration 6.42: Supermarket Allocation

There is a supermarket company that has several locations (j =1…6) to install a maximum of 3 product distribution centers.

The cost of installing a center in each location is established in CI _j m.u.

The Company has 30 supermarkets to be supplied from locations with distribution centers.

In addition, the following rules must apply in the system:

• Each location with a distribution center can supply a maximum of ten supermarkets.

• For legal requirements, if the company installs a center in location 3 and another in location 5, it cannot install any in location 6.

Objective Function

Minimize the cost of the problem taking into account that if the number of supermarkets assigned to a location is less than 8, it is penalized with a cost of F m.u.

• Table of Elements (Table 6.36)

Table 6.36 Elements of Illustration 6.42

In the configuration carried out, the locations have been considered as unitary, since they are different, apart from the fact that they are referred to in a particular way. Distribution centers and supermarkets are considered collectives, since they are identical items, determined in the case of supermarkets and indeterminate in the case of distribution centers. And on the other hand, we can avoid referring to those instances in a particular way in the statement, so we only refer to numerals of the collective element.

• Decision Activities

• Action: Install distribution centers in locations.

• Decision variables:

• x_j = Number of distribution centers installed in location j. j = 1…6

• Action: Supply supermarkets from locations.

• Decision variables:

• y_j =Number of supermarkets supplied from location j; j = 1…30

• Explicit Specifications

The statement explicitly presents the following specifications:

• E1. “install a maximum of 3 product distribution centers”:

• E2. “30 supermarkets to be supplied from locations with distribution centers”

• E3. “Each location with a distribution center can supply a maximum of 10 supermarkets”

• E4. “If the company installs a center in location 3 and another in location 5, it cannot install any in location 6”

The first three correspond to specifications that are based on data, although they are explicitly described. The fourth specification corresponds to a logical proposition.

Constraints:

• E1. $\sum \limits_{j=1}^6{x}_j\le 3$

• E2. $\sum \limits_{j=1}^6{y}_j=30$

• E3. ∀j : y_j ≤ 10

• E4. IF y₃=1 and y₅=1 THEN y₆=0

Implicit Specifications

• Specifications I1. Based on data: as mentioned, the specifications that could be based on data have been made explicit.

• Specifications I2. Quantitative selection rules: there are no decision activities selected.

• Specifications I3. Logical conditions between activities: between the two activities there is a conditional relationship, which is mentioned in the following sentence:

“30 supermarkets to be supplied from locations with distribution centers”

We have considered as explicit the norm of supplying a total of 30 supermarkets, but in this sentence, we also allude to the conditional relationship between the two activities: in order for a location to supply supermarkets, it must have installed a distribution center.

Mathematically:

We are going to express it negatively because we are dealing with a proposition of possibility:

• “A location can supply supermarkets if it has a distribution center”

• “If a location does not have a center installed, then it cannot supply any supermarket”

• ∀j: IF x_j= 0 THEN y_j=0

• Specifications I4. Bounds of discrete measurable activities: in the problem we have two measurable activities. The first of the activities, installing centers in locations, carries an implicit type I4 specification, since the most sensible thing to do is to assume that a distribution center will be installed in a physical location at most. It would be strange to think that there may be more or other specifications.

  ∀j: x_j ≤ 1

Regarding the second activity, supplying supermarkets, its measurement is not limited by a specific value.

• Specifications I5. Flow balance constraints: they do not exist.