Mixed-Integer Programming (MIP)

MIP is the core optimization engine for solving the Vehicle Routing Problem (VRP) and its variants. It models discrete decisions like vehicle-task assignment and route sequencing, while respecting capacity constraints, time windows, and heterogeneous vehicle capabilities. Key formulations include:

• Binary variables to assign orders to specific vehicles and routes.
• Integer variables to sequence stops and track cumulative load.
• Continuous variables for travel times and service start times. This enables optimal fleet utilization, minimizing total distance, fuel cost, or number of vehicles required.

In manufacturing, MIP schedules jobs across machines to minimize makespan or total tardiness. It encodes:

• Precedence constraints between operations.
• Machine eligibility and setup times.
• Resource constraints (e.g., tools, operators). A classic model is the Job Shop Scheduling problem, where binary variables indicate if operation i precedes operation j on a given machine. MIP solvers find sequences that maximize throughput and adhere to complex production calendars.

MIP determines where to open facilities (warehouses, factories, charging stations) and how to design distribution networks. It uses:

• Binary variables for opening/closing a facility.
• Continuous variables for flow of goods between nodes.
• Constraints for demand fulfillment and capacity limits. This solves the Capacitated Facility Location Problem, balancing fixed opening costs with variable transportation costs to serve customer demand optimally.

Airlines, railways, and hospitals use MIP to create legally compliant work schedules. The model incorporates:

• Binary variables assigning employees to shifts or duties.
• Integer variables tracking cumulative work hours.
• Complex labor rules (minimum rest, maximum consecutive shifts, skill matching). The objective minimizes labor costs or the number of crew members required while covering all operational tasks.

In finance, MIP selects a discrete set of investments under budget constraints. It extends classic Markowitz portfolio theory by adding:

• Binary variables for project selection.
• Logical constraints (e.g., project B requires project A).
• Cardinality constraints limiting the number of assets. This allows for modeling fixed transaction costs, minimum investment lots, and interdependencies between assets, moving beyond continuous fraction allocations.

MIP minimizes material waste when cutting large stock (metal, wood, fabric) into smaller pieces or packing items into containers. It involves:

• Integer variables for how many times a specific cutting pattern is used.
• Binary variables for assigning items to bins in packing.
• Constraints ensuring demand fulfillment and bin capacity. These NP-hard problems are central to logistics and manufacturing efficiency, directly reducing material costs.

A declarative programming paradigm for solving combinatorial problems by stating relations between variables as constraints. Unlike MIP's focus on linear objectives, CP excels at finding feasible solutions to problems with complex, non-linear logical constraints (e.g., sequencing, resource allocation). It uses powerful propagation algorithms to prune the search space and is often combined with MIP in hybrid solvers for problems like scheduling and routing.

The fundamental exact algorithm at the heart of most MIP solvers. It systematically explores the solution space by:

• Branching: Dividing the problem into smaller subproblems by fixing integer variables.
• Bounding: Calculating lower (for minimization) and upper bounds for each subproblem.
• Pruning: Eliminating subproblems that cannot contain a better solution than the current best. This process constructs a search tree and is essential for proving optimality, not just finding good solutions.

A quintessential NP-hard combinatorial optimization problem solved using MIP. It involves determining the optimal set of routes for a fleet of vehicles to service a set of customers, minimizing cost or distance. Key MIP model elements include:

• Binary decision variables indicating if a vehicle travels between two locations.
• Flow conservation constraints to ensure route continuity.
• Capacity constraints for vehicle load.
• Time window constraints for customer service. Real-world extensions (VRPTW, HFVRP) are core to heterogeneous fleet orchestration.

An advanced online control strategy for dynamic systems that repeatedly solves a MIP (or other optimization) problem over a receding horizon. At each control interval:

1. It measures the current system state (e.g., fleet positions, task status).
2. It solves a MIP to optimize a sequence of control actions for a short future window.
3. It implements only the first action. This closed-loop approach is fundamental to real-time replanning engines in fleet orchestration, allowing systems to adapt to disruptions and uncertainty.