Integer Programming: Practical Guide for Data-Driven Decisions

Your warehouse needs to decide which 15 distribution centers to operate from 47 candidates, route 200 delivery trucks across 1,200 stops, and staff 35 shifts with exactly 6 qualified workers each, all while minimizing total cost. You can't operate 14.7 distribution centers or assign 5.3 workers to a shift. These decisions are binary: yes or no, 0 or 1, open or closed. When a choice must use whole units or yes-or-no answers, integer programming can help. It may fit when the goal and rules use sums of values and fixed rates. The sections below show how to set it up and what can go wrong.

Worked Example (Simulated)

Question: Which two of six sites cover the most demand across eight zones?

The site reach and zone demand are made-up numbers from a seeded random generator (seed 41). Each site choice is zero or one, and we pick two sites. A zone counts once if either chosen site can reach it. The goal is to cover the most demand. The script is a brute-force check, not a solver run: it tries every pair of sites and adds up the demand of the zones each pair reaches.

import itertools
import numpy as np

seed = 41
rng = np.random.default_rng(seed)
facilities = [f"Site {i}" for i in range(1, 7)]
zones = [f"Zone {j}" for j in range(1, 9)]
demand = rng.integers(20, 81, size=len(zones))
coverage = rng.integers(0, 2, size=(len(facilities), len(zones)), dtype=np.int8)

best = None
for chosen in itertools.combinations(range(len(facilities)), 2):
    served = np.any(coverage[list(chosen)] == 1, axis=0)
    value = int(demand[served].sum())
    row = (value, chosen, served)
    if best is None or row[0] > best[0]:
        best = row

value, chosen, served = best
print(f"Simulated data, seed {seed}")
print("Question: Which two of six sites cover the most demand across eight zones?")
print("Assumptions: a chosen site covers a zone when its simulated coverage "
      "entry is 1; each zone's demand counts once if covered.")
print("Zone demand:", ", ".join(f"{z}={int(d)}" for z, d in zip(zones, demand)))
print("Covered demand by site pair:")
amounts = {}
for pair in itertools.combinations(range(len(facilities)), 2):
    served_pair = np.any(coverage[list(pair)] == 1, axis=0)
    amount = int(demand[served_pair].sum())
    amounts[pair] = amount
    print(f"  {facilities[pair[0]]} + {facilities[pair[1]]}: {amount}")
print("Best choice:", f"{facilities[chosen[0]]} + {facilities[chosen[1]]}")
print("Demand covered:", f"{value} of {int(demand.sum())}")
print("Zones covered:", ", ".join(z for z, yes in zip(zones, served) if yes))
tied = [f"{facilities[p[0]]} + {facilities[p[1]]}"
        for p, a in amounts.items() if a == value]
print("Pairs tied at the top:", " and ".join(tied), f"(each covers {value})")
print("Limit: this small model treats coverage as yes/no and does not "
      "include cost, travel time, or capacity.")

Printed output:

Simulated data, seed 41
Question: Which two of six sites cover the most demand across eight zones?
Assumptions: a chosen site covers a zone when its simulated coverage entry is 1; each zone's demand counts once if covered.
Zone demand: Zone 1=60, Zone 2=78, Zone 3=70, Zone 4=66, Zone 5=63, Zone 6=27, Zone 7=35, Zone 8=70
Covered demand by site pair:
  Site 1 + Site 2: 255
  Site 1 + Site 3: 391
  Site 1 + Site 4: 364
  Site 1 + Site 5: 325
  Site 1 + Site 6: 364
  Site 2 + Site 3: 268
  Site 2 + Site 4: 249
  Site 2 + Site 5: 192
  Site 2 + Site 6: 276
  Site 3 + Site 4: 346
  Site 3 + Site 5: 328
  Site 3 + Site 6: 346
  Site 4 + Site 5: 406
  Site 4 + Site 6: 241
  Site 5 + Site 6: 406
Best choice: Site 4 + Site 5
Demand covered: 406 of 469
Zones covered: Zone 1, Zone 2, Zone 3, Zone 4, Zone 6, Zone 7, Zone 8
Pairs tied at the top: Site 4 + Site 5 and Site 5 + Site 6 (each covers 406)
Limit: this small model treats coverage as yes/no and does not include cost, travel time, or capacity.

Result: Site 4 + Site 5 and Site 5 + Site 6 tie at 406 of 469; Zone 5 is uncovered in both. The script keeps the first pair it finds with the top value, so it names Site 4 + Site 5. The next best pair, Site 1 + Site 3, covers 391.

Limit: This small model counts reach as yes or no. It leaves out cost, travel time, and site size limits, so it shows how the choice is set up, not what a real network should do.

Integer programming extends linear programming by adding a brutal constraint: some or all variables must be whole numbers. This single requirement makes the general problem NP-hard in the worst case, so the number of possible answers can grow very fast. Some instances still solve quickly, and how hard yours is depends on its structure. A scheduling problem with 50 binary decisions has 1.1 quadrillion possible combinations. The difficulty is real: a model can run for a long time without proving its best answer.

Three Common Mistakes with Integer Programming

Most organizations approach integer programming the same way they'd approach linear programming: build a model, throw it at a solver, wait for results. This works for continuous optimization. For integer programming, this approach guarantees frustration.

The first mistake: treating all integer programming problems as equivalent. A problem with 50 binary variables and tight constraints might solve instantly. A problem with 500 binary variables and loose constraints might never converge. The structure of your constraints matters more than the size of your problem. Teams that ignore problem structure waste weeks tuning solver parameters when they should be reformulating their model.

The second mistake: ignoring the LP relaxation. Before adding integer constraints, solve your problem as a standard linear program allowing fractional values. If this relaxation solution is far from realistic or the objective value is drastically different from what you expect, your integer problem will struggle. A loose relaxation means the solver has to search through massive portions of the solution space. Tightening the relaxation through better constraints is the single most impactful way to improve solve times.

The third mistake: pursuing provable optimality when good-enough solutions exist in minutes. Integer programming solvers maintain two bounds: the best integer solution found so far (the incumbent), and the best possible objective value (the bound from LP relaxation). The MIP gap is the percent difference between the best whole-number answer found so far and the best bound proven so far. The bound often comes from LP relaxation: LP, or linear programming, uses sums and fixed rates, and relaxation means the model drops its whole-number rule. The gap helps show how close the answer is to the solver's limit. Closing the last bit of the gap can take far longer than reaching a small one, so set a stopping gap that fits the decision.

Integer Programming vs. Heuristics vs. Constraint Programming: Which Solves Your Problem?

Integer programming isn't your only option for discrete optimization. Three fundamentally different approaches exist, and choosing wrong costs you weeks of wasted effort.

When Pure Integer Programming Wins

Use integer programming (specifically mixed-integer programming solvers) when you need proven solution quality bounds and your problem has strong linear structure. MIP solvers excel at problems where the objective function and constraints are linear, weighted sums of variables without multiplication between variables or complex nonlinear relationships.

The killer feature of MIP solvers: they provide guaranteed bounds on solution quality. When the solver reports a 5% MIP gap, you know your solution is within 5% of theoretical optimality even if you stop before proving optimality. This guarantee matters for high-stakes decisions where you need to defend solution quality.

MIP works best for: production planning, facility location, capital budgeting, network design, workforce scheduling, transportation logistics, and portfolio optimization. Any problem that resembles "select a subset of options to maximize value subject to resource constraints" is MIP territory.

When Heuristics Beat Exact Methods

Heuristics (algorithm strategies that find good solutions without optimality guarantees) can beat exact MIP in some cases: a very large model, constraints that give weak relaxations, or a need for an answer in a very short time. Where the line falls depends on the model's structure and the hardware.

A genetic algorithm, simulated annealing, or tabu search can explore massive solution spaces and often finds near-optimal solutions in minutes where MIP struggles for hours. The tradeoff: you get no quality guarantees. Your solution might be 5% from optimal or 50% from optimal. You simply don't know.

Use heuristics when approximate solutions are acceptable and you can validate quality through comparison testing. If a greedy heuristic gives you $470,000 profit and you can't prove whether $500,000 is achievable, you need to decide: is the business value of potentially finding 6% more worth weeks of modeling effort? Often, no.

Practical approach: start with heuristics to establish baseline solution quality quickly, then invest in exact MIP only if the business value of improvement justifies the effort. A heuristic taking 30 seconds to find a solution worth $470,000 beats an exact method taking 30 hours to prove the optimum is $485,000.

When Constraint Programming Dominates

Constraint programming (CP) excels at feasibility problems and highly combinatorial scheduling with complex logical constraints. Where MIP requires expressing everything as linear inequalities, CP naturally handles "if-then" logic, disjunctions, and global constraints like "all variables must be different."

The classic CP domain: scheduling problems with precedence constraints, resource capacity limits, and no-overlap requirements. Assigning tasks to machines where tasks have different durations, machines have availability windows, and some tasks must complete before others can start. This creates a constraint satisfaction problem where CP often outperforms MIP.

Hybrid approaches combining CP and MIP leverage both strengths: use CP to find feasible solutions quickly, then use MIP to optimize among feasible options. Modern solvers (IBM CP Optimizer, Google OR-Tools) integrate both paradigms seamlessly.

The Formulation Trap: Why Your Model Won't Solve

Your problem formulation determines solution speed more than solver choice. A poorly formulated problem won't solve regardless of computational power. A well-formulated problem solves quickly even with modest hardware.

Symmetry: The Hidden Solver Killer

Symmetry occurs when multiple solutions are equivalent by swapping variables. Assigning worker A to shift 1 and worker B to shift 2 is identical to assigning worker B to shift 1 and worker A to shift 2 if workers are interchangeable. The solver wastes time exploring these equivalent solutions separately.

A scheduling problem with 10 identical workers and 10 shifts has 10! = 3.6 million symmetric solutions representing a single operational assignment. The solver explores each separately unless you break symmetry through ordering constraints or reformulation.

Breaking symmetry: add constraints forcing arbitrary ordering. If workers are truly identical, require worker 1's assignment to precede worker 2's in some ordering. This eliminates symmetric duplicates without excluding any fundamentally different solutions.

Big-M Constraints: Use Sparingly, Choose Wisely

Big-M formulations model conditional logic using large constants. "If we open facility i, then throughput must be at least 100 units" becomes: throughput_i ≥ 100 * binary_open_i - M * (1 - binary_open_i). The M must be large enough that the constraint is non-binding when facility is closed.

The problem: poorly chosen M values create terrible LP relaxations. If M = 1,000,000 but realistic throughput never exceeds 5,000, the relaxation allows fractional solutions that are nowhere near integer-feasible. The solver must explore huge portions of the search space.

Best practice: use the smallest valid M. Calculate the actual maximum value the constraint could take and set M just above that. If throughput can never exceed 10,000 units, use M = 10,000 not M = 999,999. Tighter M values create stronger relaxations and dramatically improve solve times.

Better practice: avoid Big-M formulations entirely when possible. Modern solvers support indicator constraints that model "if-then" logic directly without artificial M constants. Use them. Indicator constraints create stronger formulations and eliminate the M-tuning problem.

The Power of Reformulation

The same optimization problem can be formulated dozens of ways. Some formulations solve in seconds. Others never converge. Reformulation is the difference between success and failure.

Example: a facility location problem can be formulated with assignment variables (is customer j served by facility i?) or flow variables (how many units flow from facility i to customer j?). These are mathematically equivalent but computationally drastically different. The formulation with tighter LP relaxation solves faster.

Test the LP relaxation for every formulation candidate. Solve the problem without integer constraints and check: how many variables take fractional values? How close is the relaxation objective to realistic integer solutions? A relaxation where 90% of binaries are naturally 0 or 1 will solve far faster than one where most are fractional.

Common reformulation techniques that improve performance:

• Aggregate when possible: Instead of binary variables for each worker-shift-day combination, use variables for worker-weekly schedule patterns if daily assignments follow standard patterns
• Use strong inequalities: Add valid cuts that eliminate fractional solutions from relaxation without excluding integer solutions. Many cuts are problem-specific but dramatically tighten relaxations
• Exploit special structure: If part of your problem is a network flow, use network formulations with specialized algorithms rather than generic linear constraints
• Consider alternative variable definitions: Sometimes modeling "what we don't do" is easier than modeling "what we do", try both

Solver Selection: Commercial vs. Open-Source Reality Check

Solver choice matters. But not as much as formulation quality. A great formulation solves quickly even with mediocre solvers. A terrible formulation struggles even with the best commercial solver.

The Performance Gap Nobody Talks About

Commercial solvers (CPLEX, Gurobi, FICO Xpress) are generally faster than open-source solvers (CBC, SCIP, GLPK) on large, complex MIP problems, and the gap tends to widen as binary variable counts and constraint complexity grow.

Why the gap exists: commercial solvers invest millions in research on cutting plane algorithms, primal heuristics, branching strategies, and parallel processing. Modern MIP solving is algorithmically sophisticated, and the commercial vendors are at the frontier.

When open-source works fine: small to medium problems (under 500 binary variables), problems with very strong LP relaxations (most binaries are naturally integer in relaxation), prototyping and development, or when solve time isn't critical. If your problem already solves quickly with an open-source solver, a faster commercial solver may add little business value.

When commercial is essential: production systems solving business-critical problems daily, problems with more than 1,000 binary variables, weak LP relaxations requiring extensive branching, or real-time requirements under 5 minutes. Compare the licence cost of a commercial solver with the value of faster or better solutions on your own problem. A large speedup can be the difference between a solution and no solution.

Solver Recommendations by Use Case

Academic research and learning: GLPK or CBC. Free, adequate documentation, handles textbook problems. Limitations don't matter when you're learning concepts.

Prototyping and proof-of-concept: Google OR-Tools or COIN-OR CBC. Free, Python/C++ APIs, good for validating whether optimization approach works before investing in commercial licensing.

Production systems solving daily: Gurobi or CPLEX. Commercial licensing required, but performance gap justifies cost. Both offer similar performance: choose based on language support and API preferences. Gurobi has cleaner Python API; CPLEX integrates better with IBM ecosystem.

Cloud and scalable systems: Gurobi Cloud or commercial solver with floating licenses. Pay per use rather than fixed licensing. Scales with demand. Good for variable workloads.

Embedded optimization in SaaS products: Commercial solver with OEM licensing or Google OR-Tools for cost control. Negotiate volume licensing if embedding in products with thousands of customers.

Binary Variables vs. General Integers: Make the Right Choice

Binary variables (0 or 1 only) and general integer variables (any integer value) seem similar. They're computationally different. Choose wrong and your problem won't solve.

Why Binary is Better When Possible

Solvers are heavily optimized for binary variables. Branching algorithms, cutting planes, and primal heuristics all work better with binaries than general integers. A problem with 500 binary variables often solves faster than one with 100 general integer variables.

Binary variables also create stronger LP relaxations. A binary variable in relaxation is bounded between 0 and 1. A general integer bounded between 0 and 1000 has 1000x larger domain in relaxation, creating weaker bounds and more branching.

Use binary variables whenever you're modeling yes/no decisions: open this facility or not, assign this worker to this shift or not, include this project in the portfolio or not, select this route or not. These are naturally binary.

When General Integers Are Unavoidable

Some decisions require integer counts: produce 147 units, hire 23 employees, purchase 8 vehicles, schedule 12 shifts. You can't model these quantities with single binary variables.

For small integer ranges (0-10), consider binary expansion. Instead of one general integer variable for "number of units," use 10 binary variables representing "produce at least 1 unit," "produce at least 2 units," etc. This seems inefficient, 10 variables instead of 1, but binary formulations often solve faster due to solver optimization for binaries.

For large integer ranges (0-1000), general integers are necessary. But ask first: do you really need exact integer values? If you're sizing workforce over a month, does hiring exactly 23 workers matter versus 23.4 workers? If you can round the continuous solution, use continuous variables and round afterward. This works surprisingly often for aggregate resource planning.

Mixed Integer vs. Pure Integer Programs

Mixed-integer programs (MIP) combine integer and continuous variables. Pure integer programs restrict all variables to integers. MIP is more flexible and often easier to solve, continuous variables don't require branching.

Use continuous variables for quantities that are naturally divisible: money, raw materials in bulk, time durations, percentages. Use integer variables only where indivisibility matters operationally: discrete units, people, vehicles, machines, facilities.

A production planning model might use integer variables for "number of batches to produce" and continuous variables for "total raw material consumption." The batches must be whole numbers (you can't make 3.7 batches), but raw material is continuous. This mixed formulation solves faster than forcing raw material to be integer.

Branch and Bound: What's Actually Happening When Your Solver Runs

Understanding the core algorithm helps you interpret solver behavior and know when to intervene versus when to wait.

The Branch-and-Bound Process

Branch-and-bound is the foundation of all modern MIP solvers. The algorithm maintains two critical values: the best integer solution found (the incumbent) and the best possible solution (the bound from LP relaxation). The MIP gap is the percentage difference between these.

Step 1: Solve LP relaxation (allow fractional values). This provides a bound: the optimal objective can't be better than this relaxation value. If the relaxation solution happens to be integer-feasible, you're done. Usually, it's not.

Step 2: Branch on a fractional variable. If x = 0.7 in the relaxation, create two subproblems: one with x ≤ 0 (forcing x = 0) and one with x ≥ 1 (forcing x = 1). Solve both relaxations.

Step 3: Continue branching on fractional variables, building a tree of subproblems. Each subproblem has tighter constraints than its parent. Eventually, you hit a subproblem where the relaxation solution is integer-feasible. This becomes a candidate incumbent.

Step 4: Prune branches where the relaxation bound is worse than the current incumbent. If the incumbent has objective value 1000 and a branch's relaxation gives bound 950, that entire branch can be discarded: no integer solution in that branch can beat the incumbent.

Step 5: Continue until all branches are either solved to integer solutions or pruned. The best integer solution found is proven optimal.

Why Some Problems Never Converge

The branching tree can grow exponentially. A problem with 500 binary variables has a theoretical maximum tree of 2^500 nodes, computationally impossible to enumerate. Solver performance depends on pruning effectively through strong bounds.

Problems that struggle: weak LP relaxations where relaxation bounds don't improve much with branching. If the root relaxation gives bound 1000 and after 1 million branches the bound is still 995 while the best integer solution is 800, you have a 20% gap that won't close.

Warning signs your problem won't solve: MIP gap stays above 10% after 30 minutes, solver log shows the bound improving very slowly (less than 1% every 10 minutes), or branching tree size exceeds millions of nodes without convergence. These indicate formulation problems, not insufficient compute time.

When to Stop and Accept a Gap

Set time limits and gap tolerances based on business value, not mathematical purity. If your problem is worth $500,000 and has 5% MIP gap after 10 minutes, you're within $25,000 of optimal. Waiting 2 hours to get to 1% gap saves at most $20,000: is that worth 2 hours of compute time and delayed decisions?

Production systems should use aggressive time limits: 5-10 minutes for daily operational problems, 30-60 minutes for weekly planning, 2-4 hours maximum for strategic annual planning. Accept whatever gap the solver achieves. Uncertainty in your input data (demand forecasts, cost estimates) typically exceeds 5% anyway, making sub-1% gaps meaningless.

Key Metrics: How to Know Your Integer Program Is Working

Track these metrics to evaluate whether your integer programming implementation is delivering value or wasting computational resources.

MIP Gap Trajectory

Monitor MIP gap over time as the solver runs. The gap should decrease steadily, even if slowly. A gap that stays flat for more than 10 minutes indicates the solver is struggling and unlikely to converge further without intervention.

Good trajectory: gap decreases from 15% to 5% in first 5 minutes, then to 2% by 15 minutes. Acceptable to stop here. Poor trajectory: gap decreases from 15% to 12% in 30 minutes, then stalls. Reformulate rather than wait.

LP Relaxation Quality

Compare LP relaxation objective to best integer solution. If relaxation gives $1 million and best integer is $800,000, you have a 20% gap indicating weak relaxation. Strong relaxations have gaps under 5%.

This metric predicts solvability before investing hours in branch-and-bound. A weak relaxation warns you immediately that the problem will struggle. Fix the formulation before attempting full solve.

Solution Value vs. Baseline

Compare optimized solution to current practice or heuristic baseline. If optimization delivers only 3% improvement over a simple heuristic, question whether the complexity is justified. If optimization delivers 25% improvement, the investment clearly pays off.

This puts MIP gap in perspective. A 5% MIP gap on a solution delivering 25% improvement over baseline still gives you 20% net improvement, excellent. A 2% MIP gap on a solution delivering 3% improvement over baseline gives marginal value, maybe the heuristic was good enough.

Solve Time Relative to Business Cadence

If you're solving daily operational problems, solutions must complete in under 30 minutes (ideally under 10). If solving weekly planning, 2-4 hours is acceptable. If solving strategic annual decisions, 24 hours is fine.

When solve time exceeds business cadence requirements, you have three options: accept larger gaps with time limits, reformulate for better performance, or use heuristics instead of exact optimization. Don't let the perfect be the enemy of the actionable.

Common Pitfalls: The Mistakes That Waste Weeks

These are common mistakes in business integer programming models. Avoid them.

Pitfall 1: Modeling Everything That Might Matter

The temptation: include every constraint and objective component that could possibly affect the decision. The result: a massive, unsolvable formulation with weak relaxation.

Start minimal. Model only the biggest cost drivers and hardest constraints. Get that solving, validate results, then incrementally add complexity only if the additional precision matters for business decisions. A simple model that solves outperforms a comprehensive model that doesn't.

Pitfall 2: Ignoring Solver Output and Logs

Solver logs tell you what's happening: which constraints are causing problems, whether heuristics are finding integer solutions, how much of the time is in LP solves versus branching. Read them.

If the log shows "no integer solution found after 1000 nodes," your problem might be infeasible or your constraints are too tight. If it shows "LP relaxation infeasible," you have contradictory constraints. If it shows constant branching without bound improvement, your relaxation is weak. These diagnostics guide reformulation.

Pitfall 3: Treating Solver Parameters as Magic

Default solver parameters are often enough. Tuning parameters can help, but only after you've exhausted reformulation options. Teams waste weeks tweaking MIPFocus, Cuts, and Heuristics parameters when the real problem is formulation structure.

The one parameter worth setting always: time limit. Everything else: try defaults first. If defaults don't work, reformulate before tuning.

Pitfall 4: Forgetting to Validate Against Reality

Your model is wrong. Every model is wrong. Some are useful. Validate optimized solutions against operational constraints not captured mathematically. Have subject matter experts review recommended actions for feasibility.

A facility location model might recommend closing a distribution center that happens to serve a strategically critical customer with specialized requirements. The model doesn't know about the strategic relationship. Human validation catches this before implementation.

Taking Action: Your Integer Programming Implementation Checklist

Follow this sequence to avoid the common mistakes and build integer programs that actually solve.

Step 1: Verify Integer Programming Is the Right Tool

Ask: do I truly need discrete decisions (whole units, yes/no choices)? Or can I solve a continuous optimization and round? Rounding continuous solutions works for many resource allocation problems and avoids NP-hard complexity entirely.

Ask: is my objective function and constraints linear? Integer programming requires linearity. If you have multiplication between variables, nonlinear functions, or complex logic, consider constraint programming or nonlinear optimization instead.

Step 2: Start with Minimal Formulation

Include only the most critical constraints and the primary objective term. Get this solving first. A 70% accurate model that solves beats a 98% accurate model that doesn't.

Test LP relaxation quality. If relaxation objective is realistic and most binary variables are naturally near 0 or 1, proceed. If relaxation is nonsensical or all variables are fractional, reformulate before attempting integer solve.

Step 3: Choose Your Solver Based on Problem Size

Under 500 binary variables with strong formulation: Google OR-Tools with SCIP is free and adequate. Over 500 binary variables or weak relaxation: invest in commercial solver (Gurobi or CPLEX). The performance gap justifies licensing cost for business-critical problems.

Step 4: Set Aggressive Time Limits and Gap Tolerances

Don't wait for proven optimality unless you're publishing academic research. Set 5% gap tolerance and 10-30 minute time limit for operational problems. Accept whatever solution emerges. Test whether it outperforms your current approach by meaningful margin.

Step 5: Validate Business Logic Before Trusting Output

Review optimal solution with operational experts. Does it make sense? Are there obvious improvements the model missed? If experts immediately spot problems, your formulation is missing constraints or objectives that matter operationally.

Compare recommended solution to current practice or heuristic baseline. Quantify the improvement. If it's under 5%, question whether optimization complexity is justified. If it's over 15%, you have clear business case.

Step 6: Implement with Monitoring and Iteration

Deploy the solution and measure actual results versus model predictions. Differences reveal model limitations or input data quality issues. Refine the formulation based on production feedback.

Integer programming is iterative. Your first formulation won't be optimal. Build feedback loops to continuously improve model accuracy and solution quality over time.

Advanced Topics: When Basic MIP Isn't Enough

Once you've mastered standard integer programming, these extensions handle more complex scenarios.

Stochastic Integer Programming

Standard MIP assumes all parameters are known with certainty. Reality involves uncertainty: demand forecasts, equipment failures, weather delays. Stochastic integer programming explicitly models uncertainty through scenarios or probabilistic constraints.

Two-stage stochastic programs separate "here-and-now" decisions (build facilities, hire staff) from "wait-and-see" decisions (assign resources after uncertainty resolves). This captures the value of flexibility more accurately than deterministic models.

The computational cost: each scenario multiplies the problem size. A 500-variable MIP with 100 scenarios becomes a 50,000-variable stochastic program. Use scenario reduction techniques and accept larger gaps. For many business problems, 10-20 well-chosen scenarios capture enough uncertainty without making the problem unsolvable.

Robust Optimization

Robust optimization finds solutions that remain feasible under all realizations within an uncertainty set, rather than optimizing for expected value. This protects against worst-case outcomes.

Use robust optimization when infeasibility is catastrophic: missing contractual service commitments, violating regulatory requirements, or creating safety hazards. The cost is conservatism: robust solutions sacrifice some expected-case performance to guarantee worst-case protection.

Column Generation for Massive Problems

Some integer programs have millions or billions of variables, too many to enumerate explicitly. Column generation generates variables dynamically only as needed, solving massive problems that couldn't be formulated explicitly.

Classic application: airline crew scheduling with millions of possible crew pairings. Column generation considers only promising pairings rather than enumerating all possibilities. This technique requires sophisticated implementation but enables solving problems orders of magnitude larger than standard branch-and-bound.

Related Techniques and When to Use Each

Integer programming is one tool in a broader optimization toolkit. Understanding when to use related techniques prevents forcing problems into wrong frameworks.

Assignment Problem and Transportation Problem

These are special cases of integer programming with network structure enabling specialized fast algorithms. If your problem is one-to-one matching (workers to shifts) or many-to-many distribution (warehouses to customers), use assignment problem or transportation algorithms instead of general MIP. They solve in polynomial time versus NP-hard complexity.

Linear Programming with Rounding

Before committing to integer programming complexity, try solving the LP relaxation and rounding. For many resource allocation problems (workforce sizing, production quantities, budget allocation) rounded solutions are feasible and near-optimal. You avoid NP-hard complexity entirely.

Rounding works best when integer variables represent large aggregates (monthly production in hundreds of units) rather than individual binary decisions. It fails when rounding creates infeasibility or violates critical constraints.

Nonlinear Programming

If your objective or constraints involve nonlinear relationships (quadratic costs, exponential decay, probability distributions) you need nonlinear programming not linear integer programming. Some solvers handle mixed-integer nonlinear programs (MINLP), but they're significantly harder to solve than MIP. Consider whether linearization or piecewise-linear approximation lets you stay in MIP framework.

Dynamic Programming

For sequential decision problems with state-dependent transitions, dynamic programming often outperforms integer programming. Inventory management over time, equipment replacement scheduling, and investment timing problems have natural dynamic programming formulations that avoid the combinatorial explosion of MIP formulations.

Your turn

Bring your own data and the question you actually need answered.

MCP AnalyticsData science by email Send us your data and your question, and we will reply. ds@mcpanalytics.ai

Frequently Asked Questions

What's the difference between linear programming and integer programming?

Linear programming allows variables to take any continuous value, while integer programming restricts variables to whole numbers. This seemingly small constraint changes everything. Linear programming problems can be solved in polynomial time, while integer programming is NP-hard. A 1000-variable LP solves in seconds; the same problem with integer constraints might take hours or be unsolvable. Use integer programming only when you genuinely need discrete decisions: assigning whole trucks, hiring whole employees, or making yes/no choices.

When should I use a commercial solver versus an open-source solver?

Use commercial solvers (CPLEX, Gurobi, FICO Xpress) when your problems exceed 500 binary variables, require solutions within minutes, or need advanced features like callbacks and lazy constraints. Open-source options (CBC, SCIP, GLPK) work well for smaller problems, prototyping, or budget-constrained scenarios. For production systems solving business-critical problems worth millions, commercial licensing costs are trivial compared to solution quality improvements.

How do I know if my integer programming problem is too large to solve?

Check the LP relaxation bound first. If the gap between relaxation and any integer-feasible solution exceeds 10%, you'll likely struggle. Watch the solver's progress: if the MIP gap isn't decreasing after 30 minutes, consider reformulation or heuristics. Problem size matters less than structure: a large problem with good structure can solve in minutes, while a small problem with poor formulation may never converge. The branching tree size and symmetry in your problem determine solvability more than variable count alone.

Should I use binary variables or general integer variables?

Use binary variables whenever possible: solvers are optimized for them and they often produce stronger relaxations. If you need integer counts, ask whether you really need exact integers or if rounding a continuous solution works. For quantities like production units or workforce sizing, general integers may be unavoidable. But for assignment, selection, or scheduling decisions, binary variables are both more efficient and create tighter formulations. Converting general integers to binary expansions sometimes improves solver performance despite adding variables.

What's a good MIP gap to target before stopping the solver?

For business decisions, 1-5% MIP gap is typically sufficient: the difference between a 2% gap solution and proven optimality rarely justifies hours of additional computation. If you're solving a scheduling problem worth $500,000, a 3% gap means you might be $15,000 from optimal, often acceptable given uncertainty in your input data. Set time limits rather than pursuing zero gap. In production systems, we typically allow 5-10 minutes for daily operational problems and accept whatever gap the solver achieves. Perfect is the enemy of good in integer programming.

Conclusion: Optimization That Actually Works

Integer programming solves real business problems that continuous optimization can't touch. When decisions are inherently discrete, which facilities to operate, which routes to serve, which projects to fund, which workers to assign: integer programming provides the mathematical framework for provably good solutions.

But success requires avoiding common pitfalls. Formulation matters more than solver choice. LP relaxation quality predicts solvability before you invest days in computation. Good-enough solutions delivered quickly beat perfect solutions that never arrive. Binary variables outperform general integers when possible. Time limits and gap tolerances prevent perfectionism from blocking progress.

The path forward: start minimal, test relaxation quality, choose your solver based on problem size and structure, set aggressive stopping criteria, and validate business logic before trusting optimization output. This pragmatic approach delivers working solutions in days instead of failed projects lasting months.

The difference between organizations that succeed with integer programming and those that fail isn't mathematical sophistication. It's pragmatic focus on formulation quality, realistic expectations about solution time and optimality gaps, and willingness to validate models against operational reality rather than trusting mathematical elegance alone.

Your discrete optimization problems aren't going away. Learning to solve them with integer programming can help you make allocation decisions on purpose instead of by guesswork.