What Is Discrete Optimization?

Discrete optimization problems, also known as integer programming (linear integer programming), integer programming refers to the variables (all or part) in the plan are restricted to integers. If the variables are restricted to integers in a linear model, it is called integer linear programming. The current popular methods for solving integer programming are often only applicable to integer linear programming, which is a type of mathematical programming that requires all or part of the variables in the solution of the problem to be integers. From the composition of constraints, it can be subdivided into linear, quadratic and nonlinear integer programming.

Discrete optimization problem

A number of criteria for establishing integer programming have been developed, and people use it to obtain some useful models. This usually means that on a computer, the model will be solved in a relatively short time. Here are some guidelines ^[1]

Example 1 Suppose the limited volume of the backpack is V. The existing

Kind of item

You can put it inside

Each item has a volume of

With value

. The goal of packing a backpack is to limit the volume of the backpack. What kind of loading method can maximize the total value of the items packed in the backpack. If we define

To pack into the backpack

Number of items, this problem can be written as

constraint:

And is an integer

.

This model is a generalized backpack problem, where

Can take any non-negative integer. In other words, more than one item can fit in a backpack. One of the special cases of knapsack problem is to limit every variable

The value is 0 or 1, so you can't put more than one item in the backpack.

The knapsack problem is a pure integer programming with only one constraint. There are two reasons why this problem is important. First, many integer programming problems, such as capital budget, machine tool load, and program selection, can point to its backpack equivalent form. Second, there are already many effective algorithms for solving the knapsack problem, and they have become the basis for new algorithms for solving general integer programming problems.

The algorithms for discrete optimization problems that have been developed are typically divided into three categories: enumeration methods, cut-plane methods, and group theory methods ^[1] .