[PYTHON] [Part 1] What is optimization? --Study materials for learning mathematical optimization

: straight_ruler: Introduction

This is the first study material for learning mathematical optimization for the first time. From now on, let's learn mathematical optimization through each session.

** Mathematical optimization **

It sounds like it's difficult to hear it for the first time, but it's not enough to hold it. "Well, this way of thinking, solve it like this ~" Let's learn it. If you learn new knowledge as an engineer, you can apply it in other fields and there must be merit. By the way, if it becomes a job with this, I wonder if it will be a bite !?

: straight_ruler: Teaching materials

In this article, we will proceed while looking at the exercises in the reference text "Problem-solving series using Python: How to create an optimization model using a data analysis library" for mathematical optimization models. The details of the text are below.

■ Reference text "Problem-solving series using Python: How to create an optimization model using a data analysis library" Tsutomu Saito [Author] / Modern Science Co., Ltd. [Publishing]

: straight_ruler: What is mathematical optimization?

I will quote from the reference text. Optimization is a means to solve the following problems.

: one: I want to know the shortest route to get to the office from the nearest station at home. : two: I want to maximize the total value of the products I put in my rucksack. : three: I want to minimize the cost of transporting raw materials from the warehouse to the factory.

In addition, there are the following differences between optimization and machine learning.

** Machine learning ** Know the future by pointing to the past optimisation Determine the future by pointing to the model

What is a model? After this, I will explain about the model.

: straight_ruler: Optimized model

A model is a form in which a real problem can be replaced with a mathematical formula to calculate some solution. When searching for the shortest path, consider a mathematical formula that expresses the search route and use it as a model. In addition, the rucksack stuffing problem is modeled on a mathematical formula that expresses the stuffed state.

After building the model, the next task is to get the answer using the software of the computer called the solver.

There are paid and free solvers. Here, we use the free ** CBC ** (Coin Or branch and Cut) as the solver. In addition, ** OR-Tools ** provided by Google, which is a dedicated library for solving combination optimization, is used.

This OR-Tools is written in Python. Please refer to the following for OR-Tools.

■ Google's free tool "OR-Tools" https://developers.google.com/optimization

: straight_ruler: Model components and constraints

There are three components to building a model:

① ** Variable ** A numerical container that can take various values on the model. The object to which the formula is applied. ② ** Objective function ** An index for finding a good solution. The solution is obtained by expressing it as a function using a mathematical formula using variables and calculating so that the function is the maximum or the minimum. ③ ** Constraints ** Conditions to be observed as a combination of variables and mathematical formulas.

Constraints are written in one of the following ways. You can specify multiple conditions, but all of them must be observed. Formula ≧ Formula Formula = Formula Formula ≤ Formula

• Here, ≠ <> cannot be used.

Models are called mathematical models because they are expressed using mathematical formulas. In addition, it is said to formulate the expression of a model strictly using only mathematical formulas.

: straight_ruler: Type of optimization

There are three types of optimization problems:

: one: Linear optimization problem 　(LP：Linear programming Problem) Only continuous variables can be used. The objective function and constraints must be linear expressions. The problem is easy to solve. Even problems with thousands of constraints have been solved. : two: Mixed integer optimization problem 　(MIP：Mixed Integer programming Problem) Continuous and discrete variables can be used. The objective function and constraints must be linear expressions. Basically it is not easy to solve. It is easy to solve if the number of variables and constraints is small. : three: General optimization problem There are no restrictions on variables, objective functions, or constraints. In the research, it is treated as a classification called Non-Linear Programming Problem (NLP). It can be solved in some cases, but it is basically difficult.

• A continuous variable is a variable that takes a real value. Discrete variables, on the other hand, are variables that can take only discrete values, such as integers.

: straight_ruler: At the end

Next time, I will talk about the second, typical problem. I hope you can read it.

For this article, the author is also a beginner in optimization. I think there are misunderstandings and typographical errors, so please feel free to send us your opinions and suggestions.