0-1 Programming

0-1 Programming

A special form of integer programming. The decision variables of this kind of planning only take the value 0 or 1, so they are called 0-1 variables or binary variables, because a non-negative integer can be represented by several 0-1 variables using binary notation. 0-1 variables can quantitatively describe the logical relationships, sequential relationships, and mutually exclusive constraints between discrete variables reflected in phenomena such as on and off, taking and discarding, presence and absence, etc. Therefore, 0-1 planning is very suitable for describing And solve various problems that people are concerned about such as line design, factory location, production planning, travel shopping, backpack problems, personnel arrangements, code selection, reliability, etc. In fact, all integer programming with bounded variables can be converted into 0-1 programming for processing. Due to its profound background and wide application, 0-1 planning has been valued by people for decades.

The main method for solving 0-1 planning is the implicit enumeration method (such as the branch and bound method). There are some more effective methods for some special problems. For example, for assignment problems, it is more convenient and effective to use the Hungarian method invented by D. Koenig.