Shulou(Shulou.com)06/03 Report--

This article mainly explains "how to simulate annealing algorithm Integer programming in Python Mathematical Modeling Learning". Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Next let the editor to take you to learn "Python mathematical modeling learning how to simulated annealing algorithm integer programming" it!

1. Integer programming problem

The optimal solution of linear programming problem may be fractional or decimal. However, many practical problems often require that some variables must be integer solutions, such as the number of machines, the number of people working or the number of vehicles loaded. According to the different requirements of decision variables, integer programming can be divided into: pure integer programming, mixed integer programming, 0mur1 integer programming, mixed 0mur1 programming.

The only difference between integer programming and linear programming is the addition of integer constraints. At first glance, it seems that the integer solution can be obtained by rounding the non-integer solution obtained by linear programming, but the integer solution is not necessarily the optimal solution, or even may not be a feasible solution. Therefore, it is usually necessary to use special methods to solve integer programming, which is much more complex than linear programming, so that there is no general polynomial solution so far. Therefore, integer programming is regarded as one of the most difficult problems in mathematical programming, even in mathematics.

The successful and popular methods for solving integer programming are branch-and-bound method and cut plane method. The core idea is to decompose the integer programming problem into a series of linear programming problems, and track the upper bound (optimal feasible solution) and lower bound (optimal linear relaxation solution) of the integer programming problem, and gradually iterate and converge to the optimal solution. Because of the exponential complexity of the accurate algorithm, the global optimal solution can not be obtained in finite time, only the approximate optimal solution can be obtained. YouCans

At present, the main optimization solvers of integer programming problems are: IBM Cplex,Gurobi,FICO Xpress,SCIP. In 2018, the Chinese Academy of Sciences issued the CMIP mixed integer programming solver. You can use Lingo to solve integer programming problems, and Matlab can also use intlinprog functions to solve integer programming problems. In fact, they all use the built-in solver in the software. Python can also use third-party libraries to solve integer programming problems, such as Cvxpy, PuLp can solve integer programming problems, Cplex, Gurobi also have their own python API.

2. Simulated annealing algorithm deals with integer constraints.

Because the integer programming problem can not get the global optimal solution in a finite time, the heuristic algorithm has the opportunity to give full play to its ability. Next we discuss the simulated annealing algorithm to deal with integer constraints and solve integer programming problems.

In the previous paper, we discussed that when the simulated annealing algorithm deals with the constraints of linear programming, the method is much more complex than other commonly used algorithms. However, when dealing with integer constraints, the simulated annealing algorithm is extremely simple:

For the general optimization problem in which the decision variables are continuous variables, the basic simulated annealing algorithm randomly produces the initial solution in the range of the decision variables, and the new solution is generated by disturbance in the neighborhood of the existing solution. the algorithm is realized by random numbers with uniform distribution or normal distribution.

XInitial = random.uniform (xMin, xMax)

# random.uniform (min,max) randomly generates a real number in the range of [min,max]

XNew = xNow + scale * (xMax-xMin) * random.normalvariate (0,1)

# random.normalvariate (0,1): generate random real numbers with normal distribution with a mean value of 0 and a standard deviation of 1

XNew = max (min (xNew, xMax), xMin) # guarantee that the new solution is within the [min,max] range

For the integer programming problem, as long as the random real number generators random.uniform and random.normalvariate which produce the initial value / new solution are changed to the random integer generator random.randint:

XInitial = random.randint (xMin, xMax)

# random.randint (xMin, xMax) generates random integers between [min,max]

Because the simulated annealing algorithm is independent of the problem (Problem-independent), generally speaking, this treatment will not affect the performance of the algorithm: neither will it cause the infeasible solution, nor do you have to worry about not getting the optimal solution-- the approximate algorithm can only get the approximate optimal solution, and can get the approximate optimal solution.

Such being the case, a simpler processing method, which does not even need a random integer generator, can directly round up the non-integer solution obtained by linear programming:

XNew = round (xNow + scale * (xMax-xMin) * random.normalvariate (0,1))

# random.normalvariate (0,1): generate random real numbers with normal distribution with a mean value of 0 and a standard deviation of 1

XNew = max (min (xNew, xMax), xMin) # guarantee that the new solution is within the [min,max] range

The advantages of this approach are: (1) it is simple and direct, and (2) it is easy to achieve the required probability distribution.

3. Numerical simulation case

For ease of understanding, the previous case is still used in this article.

3.1 description of the problem:

When a factory produces two kinds of beverages An and B, for every 100 cases of A beverages, 6 kg of raw materials and 10 workers are needed, with a profit of 100000 yuan; for every 100 cases of B drinks, 5 kg of raw materials and 20 workers are needed, with a profit of 90, 000 yuan.

Now the factory has a total of 60 kg of raw materials and 150 workers, and due to other conditions, the output of A beverage is limited to no more than 800 cases.

(5) if bulk cartons are not allowed (production according to 100 cartons), how to arrange the production plan, that is, how much each of the two beverages are produced to maximize profits?

3.2 problem Analysis:

Problem (5) requires production according to 100 boxes, that is, the decision variable is required to be an integer, which is an integer programming problem.

For the simulated annealing algorithm, the initial values / new solutions in the basic algorithm are randomly generated floating-point real numbers (uniform distribution or normal distribution). For the integer programming problem, as long as the random real number generator which produces the initial value / new solution can be changed to the random integer generator, or the non-integer solution obtained by linear programming can be rounded.

3.3 problem modeling:

Decision variables:

X1: a beverage output, positive integer (unit: 100 cases)

X2: B beverage output, positive integer (unit: 100 cases)

Objective function:

Max fx = 10*x1 + 9*x2

Constraints:

6*x1 + 5*x2

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.