Introduction to Optimization Problems Combining Cone Optimization, Integer Optimization, and Network Models Problem Solving with Python Series

Summary

Python will be a general-purpose programming language with many excellent features, such as being easy to learn, easy to write readable code, and usable for a wide range of applications Python was developed by Guido van Rossum in 1991.

As a relatively new language, Python can utilize a variety of effective programming techniques, including object-oriented programming, procedural programming, and functional programming. It is also widely used in web applications, desktop applications, scientific and technical computing, machine learning, artificial intelligence, and other fields because of the many libraries and frameworks available. Furthermore, it is cross-platform and runs on many operating systems such as Windows, Mac, and Linux, etc. Python is an interpreted language, which means that it does not require compilation and has a REPL-like structure, which speeds up the development cycle.

This section discusses optimization methods using python using “Introduction to Optimization Problems – Combination of Python Optimization, Integer Optimization, and Network Models – Problem Solving with Python Series”.

In this article, I will discuss the reading notes.

Introduction to Optimization Problems Combining Cone Optimization, Integer Optimization, and Network Models Problem Solving with Python Series

Optimization is the process of choosing among countless alternatives the one that best serves the purpose. It is used in various fields such as business, engineering, and science.

In optimization, the best choice can be made using mathematical formulas. The software for the calculation is also available. In this section, we will discuss how to solve optimization problems expressed using mathematical formulas using Python.

In order to successfully express a problem that is encountered for the first time in a mathematical expression, it is effective to combine several typical problems. To do so, it is necessary to know typical problems and how to find their answers.

There are two types of optimization problems: those that can be solved with current technology and those that cannot. In this section, we focus on the pyramidal linear optimization problem as a solvable problem. The cone linear optimization problem is a generalization of the linear optimization problem (linear programming problem). The linear optimization problem is one of the most commonly used optimization problems, and software is available for it. The cone linear optimization problem, which is a generalization of the linear optimization problem, requires more computation to solve, but recently it has become possible to solve even fairly large-scale problems.

Optimization problems such as choosing a number among integers are combinatorially difficult, but with various innovations in software implementation, it has become possible to obtain answers in many cases (although there are still no theoretical guarantees). Therefore, in this paper, cone linear optimization problems involving integer variables are also discussed as solvable problems.

In addition, five combinatorial optimization problems are discussed, classified according to the target to be solved. All of them can be conveniently used to model various practical problems. For these problems, multiple modeling and solving methods are presented to show that there are multiple ways to look at and solve a single problem.

Also, here, one and the same problem is solved with several different packages. If the goal is to solve a problem that is expected to be solved with a particular method/algorithm/package, there is no reason to get hung up on a particular method/algorithm/package, it is better to use the most appropriate one for the situation from among various approaches to achieve the goal.

The specifics are as follows.

Chapter 1: Setting up the environment for optimization in Python
1.1 Installing Python
1.2 Installing the package
1.3 The runtime environment
Chapter 2: Classifying Mathematical Optimization Problems
2.1 Classification by equation form
2.1.1 Linear optimization problems
Equation
C ∈ ℝn is an n-dimensional real vector
x ∈ ℝn is an n-dimensional real vector
A ∈ ℝmxn is a real matrix of dimension mxn
b ∈ ℝm is a real vector of dimension m
x≥0 indicates that each element xi of x is non-negative
How to solve linear optimization problems
simplex method
interior-point method
2.1.2 Cone linear optimization problem
2.1.3 Mixed integer optimization problem
2.2 Classification by Object to be Solved
2.2.1 Set partitioning problem
2.2.2 Knapsack problem
2.2.3 Network optimization problems
2.2.4 Traveling Salesman Problem
2.2.5 The delivery planning problem
Chapter 3 Modeling Mathematical Optimization Problems with the Python Package
3.1 Linear optimization problems
3.1.1 Various modeling interfaces
3.1.2 Using PuLP
3.1.3 How to use Pyomo
3.2 Cone Linear Optimization Problem
How to use PICOS
3.3 Network Optimization Problems
How to use NetworkX
3.4 Mixed Integer Optimization Problems
How to Use PICOS
Chapter 4 Optimization Problems Divided into Mathematical Forms
4.1 How to Solve Linear Optimization Problems
4.1.1 Nutrition Problem
4.1.2 Column Generation and Resection Planes
4.2 Quadratic cone optimization problems
4.2.1 Quadratic cone optimization problem with rotation
4.2.2 Robust linear optimization problem
4.3 How to Solve Semi-Positive Definite Optimization Problems
4.3.1 Relaxation for the maximum cut problem
4.3.2 Polynomial Optimization
4.4 How to solve mixed integer optimization problems
4.4.1 Relaxation problems and convex hull
4.4.2 Facility assignment problem
4.4.3 Formulation using Perspective
Chapter 5 Classification by Object to be Solved
5.1 How to solve the set partitioning problem
5.1.1 Formulation as a 0-1 integer linear optimization problem
5.1.2 Modeling with PuLP
5.2 How to solve the knapsack problem
5.2.1 Formulation as a 0-1 integer linear optimization problem
5.2.2 Branch-and-bound method
5.2.3 Dynamic programming
5.3 How to solve network optimization problems
5.3.1 Solving the Shortest Path Problem
5.3.2 Solving the maximum flow problem
5.3.3 Solving the Timed Shortest Path Problem
5.3.4 Using road data with OpenStreetMap
5.4 Solving the Traveling Salesman Problem
5.4.1 Formulation as a 0-1 integer linear optimization problem
5.4.2 Modeling with PuLP and NetworkX
5.5 How to Solve the Shipping Problem
5.5.1 Formulation as a Set Partitioning Problem
5.5.2 Implementing the Column Generation Method with PuLP
Translated with www.DeepL.com/Translator (free version)