Linear Programming vs. Mixed-Integer Programming

Linear programming (LP) and mixed-integer programming (MILP, sometimes MIP) solve the same kind of problem — minimize or maximize an objective subject to constraints — but they differ in one crucial way: what values the variables are allowed to take.

Linear programming: continuous decisions

In an LP, every variable can take any value within its range — 3.7 units, 128.4 hours, 62% of a budget. The objective and every constraint must be linear (no multiplying two variables together, no if/then logic). That restriction is what makes LP fast: the simplex method and interior-point solvers find the provably optimal answer to problems with millions of variables in a fraction of a second.

LP is the right tool when your decisions are genuinely divisible — how much of a raw material to blend, how many hours of machine time to allocate across products, how to split a budget across continuous spend categories.

Mixed-integer programming: whole numbers and yes/no decisions

Many real decisions aren't divisible. You either hire a person or you don't. You either select a project or you don't. A truck holds a whole number of pallets, not 4.3 of them. MILP extends LP with integer and binary variables to represent exactly that — plus logical constraints an LP can't express at all, like “if we open warehouse A, we must also lease truck route D” or “at most one of projects B and C can be selected.”

That extra expressiveness comes at a cost: MILP is NP-hard in the worst case. Solvers handle it with branch-and-bound — solving relaxed LP versions of the problem, then branching on fractional integer variables and pruning branches that can't beat the best solution found so far — often accelerated with cutting planes that tighten the search. In practice, well-formulated MILPs with thousands of variables still solve in seconds; the art is in the formulation, not brute force.

Which one do you need?

• Continuous quantities only, no logical if/then rules → LP.
• Any yes/no selection, whole-unit counts, or conditional rules between decisions → MILP.

Most real business problems — staff scheduling, project selection, routing, capacity commitment — need at least a few integer or binary variables somewhere, which is why Solvicus's general-purpose solver supports both LP and MILP through the same interface. See it in the Linear & Integer Programming solver, or read what mathematical optimization is if you're starting from scratch.