459


            Cloud calculations within the optional course
             Optimization Problems for 10th-11th graders

       Iryna V. Lovianova1[0000-0003-3186-2837], Dmytro Ye. Bobyliev1[0000-0003-1807-4844]
                       and Aleksandr D. Uchitel2[0000-0002-9969-0149]
    1 Kryvyi Rih State Pedagogical University, 54, Gagarina Ave., Kryvyi Rih, 50086, Ukraine

               lirihka22@gmail.com, dmytrobobyliev@gmail.com
      2 Kryvyi Rih Metallurgical Institute of the National Metallurgical Academy of Ukraine,

                        5, Stepana Tilhy Str., Kryvyi Rih, 50006, Ukraine
                                     o.d.uchitel@i.ua



         Abstract. The article deals with the problem of introducing cloud calculations
         into 10th-11th graders’ training to solve optimization problems in the context of
         the STEM-education concept. After analyzing existing programmes of optional
         courses on optimization problems, the programme of the optional course
         Optimization Problems has been developed and substantiated implying solution
         of problems by the cloud environment CoCalc. It is a routine calculating
         operation and not a mathematical model that is accentuated in the programme. It
         allows considering more problems which are close to reality without adapting the
         material while training 10th-11th graders. Besides, the mathematical apparatus of
         the course which is partially known to students as the knowledge acquired from
         such mathematics sections as the theory of probability, mathematical statistics,
         mathematical analysis and linear algebra is enough to master the suggested
         course. The developed course deals with a whole class of problems of
         conventional optimization which vary greatly. They can be associated with
         designing devices and technological processes, distributing limited resources and
         planning business functioning as well as with everyday problems of people.
         Devices, processes and situations to which a model of optimization problem is
         applied are called optimization problems. Optimization methods enable optimal
         solutions for mathematical models. The developed course is noted for building
         mathematical models and defining a method to be applied to finding an efficient
         solution.

         Keywords: optimization problem, cloud calculation, CoCalc.


1        Introduction

1.1      Problem statement and its topicality substantiation
Modern society is evolving fast. The character of current changes is conditioned, first
of all, by rapid informatization of people’s life. The scientific-technical and
informational advance of the 20th-21st centuries has caused transition from the industrial
society to the informational one. These changes are going on. Experts predict the so-
___________________
Copyright © 2019 for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
460


called smart society appearing in the nearest decade. Rapid paces of life dictate their
terms of success to people.
   A person has to be able to make his/her activity and surrounding processes efficient
in terms of time expenditures for study, work and transport losses. The problems of
optimizing control over a small group of classmates working on a project or managing
a business, etc. should also be solved.


1.2    Analysis of the latest researches and publications
Development of optional and selective courses with the inter-subject integral content is
one of the most urgent issues of subject-oriented instruction of senior school students.
These courses allow students, on the one hand, to better visualize prospects of a chosen
future profession, on the other hand, – to satisfy their educational needs to the fullest.
   It is worth noting that in solving optimization problems, the notion of an
optimization problem model is as important as that of an optimization problem.
Correspondingly, a target function is a mathematical function to be optimized in a
problem, while limitation is a set of requirements to problem parameters in the form of
equations or inequalities. If the target function is linear and linear limitations are
imposed on its arguments, a corresponding optimization problem refers to the problem
class of linear programming.
   From the practical point of view, optimization problem solution means that a person
in his/her activity aimed at achieving a set goal always strives for the best or the most
efficient ways of action if there is an opportunity to choose out of an endless variety of
methods the one that helps to achieve it. Ways of action or strategies are often
characterized by a value. In this case, the problem of choosing the best strategy implies
finding an extremum – the minimum or the maximum of this value.
   It is also important to admit that the mathematical apparatus of optimization problem
solution is used not only as a tool of ordinary calculation. It is also essential for decision
making while choosing the most efficient variant to achieve the best result.
   It is essential to accentuate the importance of optimization problem solution aimed
at demonstrating applicability of inter-subject connections between mathematics and
other subjects. It should be noted that complex optimization problems associated with
long calculations should be solved professionally, while 10th-11th graders are able to
deal with less complicated ones. Such problems include those of the external ballistics
theory (determining the maximum missile range, building a safety parabola equation),
optimization problems in studying the topic Percentage, etc.
   Thus, optional courses dealing with optimization problems allow showing 10th-11th
graders how to formalize decision making problems, solve them by applying
mathematical tools and how to apply obtained solutions to practice.
   At present, there are not so many authors’ optional courses dealing with optimization
problems. Yet, the available ones do not accentuate application of information
technologies to providing instruction which is a sign of meeting modern requirements
to training organization under the STEM concept. Some researchers [2; 4; 5; 6; 7; 9;
10; 11] think that CoCalc can be one of software tools to be applicable to solving
optimization problems.
                                                                                       461


1.3    Research methods
Research methods include theoretical analysis and synthesis of data from research and
scientific-pedagogical literature concerning the research problem, analysis of
regulatory and legal documents in education that regulate optional courses,
investigation into training programmes, teaching aids, programmes of standard and
optional courses for 10th-11th graders in similar subjects.


2      Inside the optional course Optimization Problems

The STEM-concept in education is aimed at forming students’ basic ideas of
understanding unity of informational principles of building and functioning of various
systems and management processes in nature, engineering and society.
   Considering these postulates, we have developed the course Optimization Problems.
Its relevance is explained by rapid updating of science-intensive technologies calling
for highly-qualified specialists of a new type – active, creative, able to enrich their
knowledge on elaborating and mastering new generations of machines and industrial
processes. According to the competence-oriented approach, there appears a necessity
for new interpretation of subject instruction and new conditions of incorporating
instruction into formation of students’ competences. Therefore, it is required to find
critically new characteristics of subject instruction. New educational standards aimed
at self-development, self-identity and self-realization make educators look for new
approaches and forms of training organization as well as new content of traditional
training forms. In view of this, principles of training organization are changing. Out-
of-class forms of training are prioritized, while principles of independent work
organization are becoming more extensive. Independent work is a cognitive activity
associated not only with knowledge acquisition, but also with practical experience in
the context of competences.
   The developed course considers the whole class of conventional optimization
problems that vary in their content. They can be associated with designing devices and
technological processes, distributing limited resources and planning business
functioning as well as with everyday problems of people. Devices, processes and
situations to which a model of optimization problem is applied are called optimization
objects. Optimization methods enable optimal solutions to mathematical models. The
developed course is noted for building mathematical models and defining the method
to be applied to finding an efficient solution.
   The specific feature of the suggested course is simple presentation of the training
material based on concrete examples and problems. Studying linear programming by
applying mathematical materials and solving optimization problems which are
understandable for senior school students is of particular interest in this course. In this
case, optimization problems are treated as those reduced to finding the maximum or the
minimum value. These problems are also called extremal ones as finding the maximum
and the minimum value is neither more nor less than finding an extremum – the
maximum or the minimum of a function.
462


   While solving such problems, scientific thinking and the ability to see a situation as
a whole are formed. Cognitive interests and abilities to find a way out of critical
situations with minimum losses are also developed. It is evident that an employee
possessing these qualities is much more valuable for society.
   Basic principles of optimization problem solution by using computer technologies
can be taught at Informatics classes with enhanced mathematics study as they require
fundamental mathematical training. As the range of topics is very wide, it is reasonable
to treat solving even one of them as a project.
   Let us look into some variants of projects to be proposed to students within the
optional course Optimization Problems. First, students should be provided with basic
algorithms in CoCalc [4; 8]. While doing a project, students get acquainted with
methods of optimization problem solution. One should accentuate the
recommendations for improving functioning of a process to be simulated while
discussing project results.
   There are several stages in teaching optimization problem solution.
   Optimization problem 1. Any port in a storm [1]: there is significant danger to boats
caught out in the open sea during a storm. Ideally, boats will dock before the storm hits
and wait it out. The map above shows 20 orange boats out at sea. With a storm
approaching, each boat needs to be directed to one of three docks. Docks have a limited
number of spaces available for boats (indicated by the rectangular spaces). Altogether,
there are 20 boat spaces available. The boats are clustered into three areas and each area
varies in distance to the docks (as indicated by the black arrows). All boats must be
assigned to one space in a dock. Question: What is the minimum possible total
distance traveled by all boats? More detailed information is presented in Fig. 1.




                        Fig. 1. Figure to the Optimization problem 1

Students must build a mathematical model of the problem. To solve the problem we
offer students the following code in CoCalc [8]:
                                                     463


A=matrix(QQ, [[…,…,…],[…,…,…]],[…,…,…]]); A
m=A.nrows()    #p
n=A.ncols()    #q
isoptimal=0
isunbounded=0
XVar=[]
TVar=[]
for i in range(n-1):
  XVar.append('X'+`i+1`)
for j in range(m-1):
  TVar.append('T'+`j+1`)
p=-1
q=-1
isfeasible=1
problemfeasible=0
#Atemp=matrix(QQ, m,n)
while (isoptimal==0 and isunbounded==0):
  isoptimal=1
  isunbounded=1
  isfeasible=1
  problemfeasible=1
  p=-1
  q=-1
  #checks to see if current position is feasible
  for i in range(m-1):
    if A[i,n-1]<0 and p<0:
      p=i
      isfeasible=0
      isoptimal=0
      isunbounded=0
  #Checks to see if problem is feasible
  if isfeasible==0:
    problemfeasible=0
    for k in range(n-1):
      if A[p,k]<0 and q<0:
        q=k
        problemfeasible=1
  if problemfeasible==0:
    print('The problem has no feasible solutions')
    p
    q
  else:
    #checking last row to see if optimal (step 1),
    #it's optimal when all are negative
    for i in range(n-1):
464


      if A[m-1,i]>0:
        isoptimal=0
    if isoptimal==1 and isfeasible==1:
      print('This is optimal, ignore everything after
this')

      #finding the right [p,q] to pivot on and will only
      # pivot if point is feasible
      if isoptimal!=1 and isfeasible==1:
        q=-1
        #finding position q to pivot on
        for i in range(n-1):
          if A[m-1,i]>0 and q<0:
            q=i; q

       #checking column q to see if all negative (step 4)
       for k in range(m-1):
         #A[k,q]
         if A[k,q]>0:
           isunbounded=0

        if isunbounded==1:
          print('This is unbounded')
        p=-1
        #finding position p to pivot on (step 5)
        for j in range(m-1):
          if A[j,q]!=0:
            if A[j,n-1]/A[j,q]>=0 and A[j,q]>0:
              if p<0:
                p=j; p
              if p>=0 and A[j,n-1]/A[j,q]<A[p,n-1]/A[p,q]:
                p=j; p
        print('pivot on position')
        p
        q
      #the temporary matrix pivots on [p,q]
      Atemp=matrix(QQ, m,n)
      for i in range(m):
        for j in range(n):
          if i==p and j==q:
            Atemp[i,j]=1/A[p,q]
          if i==p and j!=q:
            Atemp[i,j]=A[i,j]/A[p,q]
          if i!=p and j==q:
            Atemp[i,j]=-1*A[i,j]/A[p,q]
                                                                                       465


          if i!=p and j!=q:
            Atemp[i,j]=(A[i,j]*A[p,q]-A[i,q]*A[p,j])/A[p,q]
      Xp=XVar[q];Xp
      Tp=TVar[p];Tp
      XVar[q]=Tp
      TVar[p]=Xp
      Atemp
      A=Atemp
      XVar
      TVar

Optimization problem 2. Cell Towers [3]: as the head of analytics for a cell phone
company, you have been asked to optimize the location of cell towers in a new area
where your company wants to provide service. The new area is made up of several
neighborhoods. Each neighborhood is represented by a black house icon in the
accompanying image. A cell tower can be placed on any square (including squares with
or without a neighborhood). Once placed, a cell tower provides service to 9 squares
(the 8 adjacent squares surrounding it and the 1 it sits on). For example, if you placed
a cell tower in B2, it would provide service to A1, B1, C1, A2, B2, C2, A3, B3, and
C3. The company recognizes that it may not be worthwhile to cover all neighborhoods,
so it has instructed you that it needs to cover only 70% of the neighborhoods in the new
area. Each cell tower is expensive to construct and maintain so it is in your best interest
to only use the minimum number of cell towers. Question: What is the minimum
number of cell towers needed to provide service to at least 70% of the
neighborhoods? More detailed information is presented in Fig. 2.




                        Fig. 2. Figure to the Optimization problem 2

Students must build a mathematical model of the problem. To solve the problem, we
offer students the same code as in optimization problem 1.
466


   Optimization problem 3. For the project, students can be offered the task of finding
the optimal route with restrictions. More detailed information is presented in Table 1
and Fig. 3. There are a certain number of containers in each quarter, each with a capacity
1,1 m3. Just such containers 110. The following additional conditions are met: the
volume of the truck body is limited and equal 43 m3. The point of departure of a filled
truck is point B. The truck starts its journey from Base to Point A. The following flights
provide a quarterly cycle (from Point B to Point B). The last point of arrival van-tag
with an empty body – Point A. Students should independently ask questions and solve
the problem.

                       Table 1. The number of containers in the area.

           No         Number of containers          No         Number of containers

           1                     4                   16                 1
           2                     5                   17                 3
           3                     6                   18                 3
           4                     4                   19                 2
           5                     5                   20                 4
           6                     3                   21                 5
           7                     2                   22                 2
           8                     5                   23                 6
           9                     4                   24                 2
           10                    3                   25                 1
           11                    6                   26                 1
           12                    3                   27                 4
           13                    3                   28                 3
           14                    7                   29                 5
           15                    8

  To solve the problem, we offer students the following code in CoCalc:
g = graphs.ChvatalGraph()
g = g.minimum_outdegree_orientation()
p = MixedIntegerLinearProgram()
f = p.new_variable(real=True, nonnegative=True)
s, t = 0, 2
for v in g:
  if v != s and v != t:
    p.add_constraint(
      sum(f[(v,u)] for u in g.neighbors_out(v))
      - sum(f[(u,v)] for u in g.neighbors_in(v)) == 0)
                                                                                           467


for e in g.edges(labels=False):
  p.add_constraint(f[e] <= 1)
p.set_objective(sum(f[(s,u)] for u in
g.neighbors_out(s)))
p.solve() # rel tol 2e-11




                         Fig. 3. Figure to the Optimization problem 3

Stage 1. Studying theoretical principles. It includes the notion of an optimization
problem and the necessity to solve such problems in modern life. There are some
problem examples provided.
    Various situations require absolutely different solutions depending on the chosen or
set criterion.
    For example, it is possible to spend 50 minutes driving from one city to another. But
if part of the route is covered by railway and then by bus, it will take 30 minutes only.
It is evident that the latter solution is better if it is necessary to get to one’s destination
in the shortest time possible. In other words, this solution is the best by the criterion of
468


time minimization. According to another criterion (for example, reduction of
expenditures or the number of changes), the former solution is better. Thus, to solve
problems, it is essential to analyze quantitative parameters – minimum expenditures,
minimum deviations from the standard, maximum speeds, revenues, etc.
   Stage 2 is studying the general plan of optimization problem solution. Here, the
notions of a target function, admissible solutions, and the system of limitations are
introduced.
   The general plan of optimization problem solution includes:
─ investigation into an object to define parameters required to solve the problem;
─ descriptive simulation, i.e. determining basic connections and dependencies between
  parameters;
─ mathematical simulation;
─ choice or development of the method for solving the problem;
─ computerized implementation of the solution;
─ analysis of the solution obtained.
One of the problems is considered in the form of a mathematical model as a theoretical
basis to receive practical solutions on the computer. Next, a practical method is selected
and implemented. After obtaining the result, one should analyze it considering various
variants of optimizing the process by the ready-made algorithm with initial data
changed.
   Stage 3. Theoretical and practical implementation of solving any optimization
problem by applying systems of computer mathematics or other tools.
   The ability to solve optimization problems is essential for modern people. This
should be taught. Introduction of the project course Optimization Problem could be a
way out.
   If the current variant of training is used without any chance of introducing an
optional course like this, the work can be organized as follows. Mathematical models
can be created at Mathematics classes, while algorithms of solving these problems by
means of CoCalc can be implemented at Informatics classes. Abilities acquired through
studying under this mode will help students become successful in new social
conditions.
   The course programme was based on existing programmes of optional courses of
similar character as well as teaching aids and programmes of optional courses.
   The developed course is connected with secondary school basic courses of
Mathematics (sections Linear Equations and Inequities, Solution of Systems of Linear
Equations and Inequities) and Informatics (Mathematical Simulation, Spreadsheets).
   The developed course is aimed at theoretical and practical study of basic notions and
methods of optimization as well as basic principles of the decision making theory to
form students’ ideas of applying the mathematical apparatus to solving problems of
finding efficient solutions. While achieving the set aim, a number of tasks are solved:
─ getting students acquainted with basic principles of the decision making theory and
  optimization methods;
─ demonstrating application of optimization methods to practical activities;
                                                                                     469


─ introducing methods of solving linear programming problems and their application
  to students;
─ forming students’ abilities of solving decision making problems by applying studied
  optimization methods.
The optional course Optimization Problems comprises 35 hours designed for a
semester. The recommended number of hours per week in the 10th grade is 2, in the 11th
grade – 1.
   The course consists of two main content modules:
1. The role of the theory and methods of decision making in the modern world (17
   hours);
2. Linear optimization (17 hours).
The content of the first module includes general statement of the decision making
problem in various spheres of human activity as well as some decision making methods.
Presentation of theoretical materials of this section should be illustrated by concrete
examples and problems. This module covers the following topics:
─ The decision making theory (basic notions and definitions);
─ The decision making theory in economics;
─ Mathematical simulation of decision making;
─ Collective decision making. Models of collective choice;
─ Decision making in the organization theory.
The second module includes the most important, yet at the same time, simple section
of the decision making theory – linear programming. It enables students to comprehend
applicability of systems of linear equations and inequities, methods of studying and
building function diagrams, mathematical modules of real-life objects and processes to
human activity. Presentation of theoretical materials of this section should also be
illustrated by concrete examples and problems. This module covers the following
topics:
─ Basic principles of linear programming;
─ Linear optimization problems;
─ The graphical method of solving linear programming problems;
─ The simplex-method of solving linear programming problems;
─ Solving linear programming problems by means of CoCalc.
The suggested programme of the optional course is of a rough character and open to
changes to enable a teacher to correct and modify the course depending on the type of
an educational institution where the course is taught. It should be noted that the course
programme includes some modules and topics that can be used as independent optional
courses if their content is expanded.
   The course programme provides theoretical and practical classes and independent
work (solo work on problem solution). The distance mode of training is recommended.
470


  After mastering the programme material, a student can get an idea of practical
application of the decision making theory and optimization methods to everyday life
and professional activity. Besides, there are the following requirements to students’
knowledge and abilities to be formed after mastering the course:
─ The student knows basic notions of the decision making theory, methods of decision
  making and optimization, basic problems of linear programming, the simplex-
  method of solving linear programming problems;
─ The student is able to correctly choose a relevant solving method to optimize a
  problem and implement it;
─ The student possesses methods of solving problems of linear programming, abilities
  of applying CoCalc and modern mathematical tools to solving practical problems.


3       Conclusions

After analyzing existing programmes of optional courses on optimization problems, the
programme of the optional course Optimization Problems has been developed and
substantiated implying solution of problems by the cloud environment CoCalc. It is a
routine calculating operation and not a mathematical model that is accentuated in the
programme. It allows considering more problems which are close to reality without
adapting the material while training 10th-11th graders. Besides, the mathematical
apparatus of the course which is partially known to students as the knowledge acquired
from such mathematics sections as the theory of probability, mathematical statistics,
mathematical analysis and linear algebra is enough to master the suggested course. The
developed course deals with a whole class of problems of conventional optimization
which vary greatly. They can be associated with designing devices and technological
processes, distributing limited resources and planning business functioning as well as
with everyday problems of people. Devices, processes and situations to which a model
of optimization problem is applied are called optimization problems. Optimization
methods enable optimal solutions for mathematical models. The developed course is
noted for building mathematical models and defining a method to be applied to finding
an efficient solution.


References
 1.   Any Port In A Storm. The PuzzlOR. http://puzzlor.com/2017-02_PortInAStorm.html
      (2017). Accessed 21 Oct 2018
 2.   Bobylyev, D.Ye., Popel, M.V.: Pidtrymka samostiinoi roboty zasobamy SageMathCloud
      pry navchanni kursu «Dyferentsialni rivniannia» maibutnikh vchyteliv matematyky
      (Support for independent students’ work by tools SageMathCloud in the learning of
      “Differential equations” for future mathematics teachers). New computer technology 15,
      201–205 (2017)
 3.   Cell Towers. The PuzzlOR. http://puzzlor.com/2016-04_CellTowers.html (2016).
      Accessed 21 Oct 2018
                                                                                            471


 4.   Markova, O., Semerikov, S., Popel, M.: CoCalc as a Learning Tool for Neural Network
      Simulation in the Special Course “Foundations of Mathematic Informatics”. In: Ermolayev,
      V., Suárez-Figueroa, M.C., Yakovyna, V., Kharchenko, V., Kobets, V., Kravtsov, H.,
      Peschanenko, V., Prytula, Ya., Nikitchenko, M., Spivakovsky A. (eds.) Proceedings of the
      14th International Conference on ICT in Education, Research and Industrial Applications.
      Integration, Harmonization and Knowledge Transfer (ICTERI, 2018), Kyiv, Ukraine, 14-
      17 May 2018, vol. II: Workshops. CEUR Workshop Proceedings 2104, 338–403.
      http://ceur-ws.org/Vol-2104/paper_204.pdf (2018). Accessed 30 Nov 2018
 5.   Modlo, E.O., Semerikov, S.O.: Development of SageMath filter for Moodle. New computer
      technology 12, 233–243 (2014)
 6.   Popel, M.V., Bobyliev, D.Ye.: Dyferentsiatsiia navchannia maibutnikh vchyteliv
      matematyky kompleksnomu analizu zasobamy CoCalc (Differentiation of student learning
      to complex analysis using CoCalc). New computer technology 17, 192–200 (2019)
 7.   Popel, M.V.: Orhanizatsiia navchannia matematychnykh dystsyplin u SageMathCloud
      (Organization of teaching mathematical disciplines in SageMathCloud). Publishing
      Department of the Kryviy Rih National University, Kryviy Rih (2016)
 8.   SageMath, Inc.: CoCalc - Collaborative Calculation in the Cloud. https://cocalc.com (2019).
      Accessed 21 Mar 2019
 9.   Semerikov, S.O., Shokaliuk, S.V.: Orhanizatsiia rozpodilenykh obchyslen zasobamy MMS
      Sage (The organization of distributed computing using MME Sage). Pedahohichni nauky:
      teoriia, istoriia, innovatsiini tekhnolohii 2(4), 338–345 (2010)
10.   Semerikov, S.O., Teplyckyj, I.O.: Mobilne matematychne seredovyshhe Sage: novi
      mozhlyvosti ta perspektyvy rozvytku (Mobile mathematical environment Sage: a new
      features and development prospects). In: Tezy dopovidej VII Vseukrainskoi naukovo-
      praktychnoi konferencii “Informacijni tehnologii v osviti, nauci i tehnici” (ITONT-2010).
      vol. 2, p. 71. Cherkaskyj derzhavnyj tehnologichnyj universytet, Cherkasy (2010)
11.   Shokaliuk, S.V., Markova, O.M., Semerikov, S.O.: SageMathCloud yak zasib khmarnykh
      tekhnolohii kompiuterno-oriientovanoho navchannia matematychnykh ta informatychnykh
      dystsyplin (SageMathCloud as the Learning Tool Cloud Technologies of the Computer-
      Based Studying Mathematics and Informatics Disciplines). In: Soloviov, V.M. (ed.)
      Modeling in Education: State. Problems. Prospects, pp. 130-142. Brama, Cherkasy (2017)