mixedinteger

Mixed integer refers to optimization problems that involve both continuous variables and integer (often binary) variables. When the problem is linear in both the objective and constraints, it is called mixed-integer linear programming (MILP). If nonlinearities are present, it is called mixed-integer nonlinear programming (MINLP). The discrete variables typically model decisions such as on/off status, yes/no choices, assignments, or routing, while continuous variables represent quantities that can vary smoothly.

MILP formulations express the objective as a linear function of decision variables and impose linear constraints. A typical MILP problem minimizes c^T x subject to Ax ≤ b, with some components of x required to be integers. 0-1 variables are common for modeling selection decisions. Solving MILP generally relies on branch-and-bound techniques, often enhanced with cutting planes, leading to branch-and-cut or branch-and-price methods in practice. The problem is NP-hard in general, but if the number of integer variables is fixed, Lenstra’s theorem shows it can be solved in polynomial time in the size of the data.

MINLP broadens MILP to include nonlinear objective or constraints. If the nonlinearities are convex, specialized methods such as outer-approximation, generalized Benders decomposition, or combination with nonlinear programming inside a MILP framework are used. Non-convex MINLP poses greater challenges and typically requires global optimization techniques like spatial branch-and-bound or problem-specific reformulations.

Applications span operations research and engineering, including scheduling, production planning, facility location, vehicle routing with discrete decisions, energy system design, and various combinatorial optimization problems. Mixed-integer models provide a rigorous way to capture both continuous quantities and discrete decisions within a unified framework.