An optimization or feasibility problem in mathematics where some or all variables must be integers is known as an integer programming problem. The phrase frequently applies to integer linear programming (ILP), where the objective function and constraints (aside from the integer constraints) are linear.

Programming in integers is NP-complete. One of Karp's 21 NP-complete problems is the case of 0-1 integer linear programming, in which the unknowns are binary, and only the limitations need to be met.

The issue is a mixed-integer programming problem if some decision variables are not discrete.

Mixed-Integer Programming (MIP) Problems

When some of the decision variables must have integer values at the best solution (i.e. whole integers like -1, 0, 1, 2, etc.), the problem is referred to as mixed-integer programming (MIP). When you employ integer variables, you may define and solve a far more comprehensive range of practical optimization problems.

A decision variable, X1 that can only be either 0 or 1 at the solution is a particularly significant situation. These variables, also known as 0-1 or binary integer variables, can simulate yes-or-no choices, such as whether to construct a plant or purchase a piece of machinery. Unfortunately, an optimization problem becomes non-convex and much more challenging to solve when it has integer variables. In addition, as you add more integer variables, your memory and solution time might increase rapidly.

Despite modern approaches and supercomputers, models with a few hundred integer variables have never been optimally solved. It is due to the need to test numerous combinations of particular integer values for the variables. We must solve a "typical" linear or nonlinear optimization problem for each variety. The possible combinations might grow exponentially as the challenge gets more extensive.

Constraint Programming (CP) Problems

The phrase "constraint programming" is derived from artificial intelligence research, where various issues call for assigning symbolic values to variables that adhere to particular limitations, such as locations on a chessboard. The symbolic values are drawn from a finite set of possibilities that integers may quantify.

"Higher-level" constraints that apply to integer variables are defined through constraint programming. For example, the most common and practical higher-level restriction demands a set of n choice variables to adopt a permutation (non-repeating ordering) of numbers from 1 to n.

Solving MIP and CP Problems

Some systematic, potentially exhaustive searches must resolve MIP and CP problems because they are non-convex. Branch and Bound is the name of the "traditional" approach to handling these issues. This method finds the optimal "relaxation" solution without integer limitations (via standard linear or nonlinear optimization methods). There is no need for additional effort if the decision variables with integer constraints in this solution have integer values. The Branch and Bound approach select one of the integer variables with non-integral solutions and "branches," generating two new subproblems where the variable's value is more strictly bound. Until a solution that fulfils all integer constraints is discovered, these subproblems are resolved, and the procedure is repeated.

Alternative techniques, including genetic and evolutionary algorithms, produce potential solutions randomly while adhering to the integer limitations. These methods start with initial solutions that are typically far from optimal. Still, they then use techniques like integer- or permutation-preserving mutation and crossover to turn existing solutions into new candidate solutions that still satisfy the integer constraints but may have better objective values. Iterations of this method are carried out until a "good solution" is attained. Unfortunately, these techniques typically cannot "prove the optimality" of the solution.