Integer Programming: Optimal Decisions with Whole Numbers

Part 30 of 12-Week BusinessMath Series

What You’ll Learn

• Understanding when integer constraints are necessary
• Implementing branch-and-bound for exact integer solutions
• Using relaxation techniques for faster approximate solutions
• Modeling binary (0/1) decision variables
• Solving scheduling, assignment, and selection problems
• Performance trade-offs: exact vs. heuristic methods

The Problem

Many business decisions require whole numbers:

• Capital budgeting: How many machines to purchase? (Can’t buy 2.7 machines)
• Workforce planning: How many employees to hire? (Can’t hire 14.3 people)
• Project selection: Which projects to fund? (Binary yes/no)
• Production scheduling: How many batches to produce? (Integer batch sizes)

Continuous optimization solvers give you fractional answers—but you need integers.

The Solution

BusinessMath provides integer programming solvers that find optimal whole-number solutions. The core technique is branch-and-bound: solve relaxed continuous problems, then systematically explore integer solutions.

Pattern 1: Capital Budgeting (0/1 Knapsack)

Business Problem: You have $500K budget. Which projects should you fund?

import BusinessMath

// Define projects
struct Project {
    let name: String
    let cost: Double
    let npv: Double
    let requiredStaff: Int
}

let projects = [
    Project(name: "New Product Launch", cost: 200_000, npv: 350_000, requiredStaff: 5),
    Project(name: "Factory Upgrade", cost: 180_000, npv: 280_000, requiredStaff: 3),
    Project(name: "Marketing Campaign", cost: 100_000, npv: 150_000, requiredStaff: 2),
    Project(name: "IT System", cost: 150_000, npv: 200_000, requiredStaff: 4),
    Project(name: "R&D Initiative", cost: 120_000, npv: 180_000, requiredStaff: 6)
]

let budget = 500_000.0
let availableStaff = 10

// Binary decision variables: x[i] ∈ {0, 1} (fund project i or not)
// Objective: Maximize total NPV
// Constraints: Total cost ≤ budget, total staff ≤ available

// Create solver with binary integer specification
let solver = BranchAndBoundSolver>(
    maxNodes: 1000,
    timeLimit: 30.0
)

let integerSpec = IntegerProgramSpecification.allBinary(dimension: projects.count)

// Objective: Maximize NPV (minimize negative NPV)
let objective: @Sendable (VectorN) -> Double = { decisions in
    -zip(projects, decisions.toArray()).map { project, decision in
        project.npv * decision
    }.reduce(0, +)
}

// Constraint 1: Budget (inequality: totalCost ≤ budget)
let budgetConstraint = MultivariateConstraint>.inequality { decisions in
    let totalCost = zip(projects, decisions.toArray()).map { project, decision in
        project.cost * decision
    }.reduce(0, +)
    return totalCost - budget  // ≤ 0
}

// Constraint 2: Staff availability (inequality: totalStaff ≤ availableStaff)
let staffConstraint = MultivariateConstraint>.inequality { decisions in
    let totalStaff = zip(projects, decisions.toArray()).map { project, decision in
        project.requiredStaff * Int(decision.rounded())
    }.reduce(0, +)
    return Double(totalStaff) - Double(availableStaff)  // ≤ 0
}

// Binary bounds: 0 ≤ x[i] ≤ 1 for each decision variable
let binaryConstraints = (0..>.inequality { x in -x[i] },  // x[i] ≥ 0
        MultivariateConstraint>.inequality { x in x[i] - 1.0 }  // x[i] ≤ 1
    ]
}

// Solve using branch-and-bound
let result = try solver.solve(
    objective: objective,
    from: VectorN(repeating: 0.5, count: projects.count),
    subjectTo: [budgetConstraint, staffConstraint] + binaryConstraints,
    integerSpec: integerSpec,
    minimize: true
)

// Interpret results
print("Optimal Project Portfolio:")
print("Status: \(result.status)")
var totalCost = 0.0
var totalNPV = 0.0
var totalStaff = 0

for (project, decision) in zip(projects, result.solution.toArray()) {
    if decision > 0.5 {  // Binary: 1 means funded
        print("  ✓ \(project.name)")
        print("    Cost: \(project.cost.currency(0)), NPV: \(project.npv.currency(0)), Staff: \(project.requiredStaff)")
        totalCost += project.cost
        totalNPV += project.npv
        totalStaff += project.requiredStaff
    }
}

print("\nPortfolio Summary:")
print("  Total Cost: \(totalCost.currency(0)) / \(budget.currency(0))")
print("  Total NPV: \(totalNPV.currency(0))")
print("  Total Staff: \(totalStaff) / \(availableStaff)")
print("  Budget Utilization: \((totalCost / budget).percent())")
print("  Nodes Explored: \(result.nodesExplored)")

Pattern 2: Production Scheduling with Lot Sizes

Business Problem: Minimize production costs. Each product has a fixed setup cost and must be produced in minimum lot sizes.

// Products with setup costs and lot size requirements
struct ProductionRun {
    let product: String
    let setupCost: Double
    let variableCost: Double
    let minimumLotSize: Int
    let demand: Int
}

let productionRuns = [
    ProductionRun(product: "Widget A", setupCost: 5_000, variableCost: 10, minimumLotSize: 100, demand: 450),
    ProductionRun(product: "Widget B", setupCost: 3_000, variableCost: 8, minimumLotSize: 50, demand: 280),
    ProductionRun(product: "Widget C", setupCost: 4_000, variableCost: 12, minimumLotSize: 75, demand: 350)
]

let maxProductionCapacity = 1000

// Decision variables: number of lots to produce (integer)
// Objective: Minimize total cost (setup + variable)
// Constraints: Meet demand, don't exceed capacity, minimum lot sizes

// Create solver for general integer variables (not just binary)
let productionSolver = BranchAndBoundSolver>(
    maxNodes: 5000,
    timeLimit: 60.0
)

// Specify which variables are integers (all of them: lots for each product)
let productionSpec = IntegerProgramSpecification(integerIndices: Set(0..) -> Double = { lots in
    zip(productionRuns, lots.toArray()).map { run, numLots in
        if numLots > 0 {
            return run.setupCost + (run.variableCost * numLots * Double(run.minimumLotSize))
        } else {
            return 0.0
        }
    }.reduce(0, +)
}

// Constraint 1: Meet demand for each product (inequality: production ≥ demand)
let demandConstraints = productionRuns.enumerated().map { i, run in
    MultivariateConstraint>.inequality { lots in
        let production = lots[i] * Double(run.minimumLotSize)
        return Double(run.demand) - production  // ≤ 0 means production ≥ demand
    }
}

// Constraint 2: Total production within capacity (inequality: total ≤ capacity)
let capacityConstraint = MultivariateConstraint>.inequality { lots in
    let totalProduction = zip(productionRuns, lots.toArray()).map { run, numLots in
        numLots * Double(run.minimumLotSize)
    }.reduce(0, +)
    return totalProduction - Double(maxProductionCapacity)  // ≤ 0
}

// Bounds: 0 ≤ lots[i] ≤ 20 for each product
let lotBoundsConstraints = (0..>.inequality { x in -x[i] },  // x[i] ≥ 0
        MultivariateConstraint>.inequality { x in x[i] - 20.0 }  // x[i] ≤ 20
    ]
}

// Solve
let productionResult = try productionSolver.solve(
    objective: costObjective,
    from: VectorN(repeating: 5.0, count: productionRuns.count),
    subjectTo: demandConstraints + [capacityConstraint] + lotBoundsConstraints,
    integerSpec: productionSpec,
    minimize: true
)

print("Optimal Production Schedule:")
print("Status: \(productionResult.status)")
for (run, numLots) in zip(productionRuns, productionResult.solution.toArray()) {
    let lots = Int(numLots.rounded())
    let totalUnits = lots * run.minimumLotSize
    let cost = lots > 0 ? run.setupCost + (run.variableCost * Double(totalUnits)) : 0.0

    print("  \(run.product): \(lots) lots × \(run.minimumLotSize) units = \(totalUnits) units")
    print("    Demand: \(run.demand), Excess: \(totalUnits - run.demand)")
    print("    Cost: \(cost.currency(0))")
}

let totalCost = productionResult.objectiveValue
print("\nTotal Production Cost: \(totalCost.currency(0))")
print("Nodes Explored: \(productionResult.nodesExplored)")

Pattern 3: Assignment Problem (Workers to Tasks)

Business Problem: Assign workers to tasks to minimize total time, where each worker has different efficiencies.

// Workers and their time to complete each task (hours)
let workers = ["Alice", "Bob", "Carol", "Dave"]
let tasks = ["Task 1", "Task 2", "Task 3", "Task 4"]

// Time matrix: timeMatrix[worker][task] = hours
let timeMatrix = [
    [8, 12, 6, 10],   // Alice's times
    [10, 9, 7, 12],   // Bob's times
    [7, 11, 9, 8],    // Carol's times
    [11, 8, 10, 7]    // Dave's times
]

// Binary assignment matrix: x[i][j] = 1 if worker i assigned to task j
// Objective: Minimize total time
// Constraints: Each worker assigned to exactly one task, each task assigned to exactly one worker

// Flatten assignment matrix to 1D vector for optimizer
let numWorkers = workers.count
let numTasks = tasks.count
let numVars = numWorkers * numTasks

// Create solver for assignment problem
let assignmentSolver = BranchAndBoundSolver>(
    maxNodes: 10000,
    timeLimit: 120.0
)

let assignmentSpec = IntegerProgramSpecification.allBinary(dimension: numVars)

let assignmentObjective: (VectorN) -> Double = { assignments in
    var totalTime = 0.0
    for i in 0..>.equality { assignments in
        let sum = (0..>.equality { assignments in
        let sum = (0..>.inequality { x in -x[i] },
        MultivariateConstraint>.inequality { x in x[i] - 1.0 }
    ]
}

// Solve
let assignmentResult = try assignmentSolver.solve(
    objective: assignmentObjective,
    from: VectorN(repeating: 0.25, count: numVars),
    subjectTo: workerConstraints + taskConstraints + assignmentBounds,
    integerSpec: assignmentSpec,
    minimize: true
)

print("Optimal Assignment:")
print("Status: \(assignmentResult.status)")
var totalTime = 0
for i in 0.. 0.5 {
            let time = timeMatrix[i][j]
            print("  \(workers[i]) → \(tasks[j]) (\(time) hours)")
            totalTime += time
        }
    }
}

print("\nTotal Time: \(totalTime) hours")
print("Nodes Explored: \(assignmentResult.nodesExplored)")

// Compare to greedy heuristic
print("\nGreedy Heuristic (for comparison):")
var greedyTime = 0
var assignedWorkers = Set()
var assignedTasks = Set()

// Sort all (worker, task, time) pairs by time
var allPairs: [(worker: Int, task: Int, time: Int)] = []
for i in 0..

How It Works

Branch-and-Bound Algorithm

1. Relax: Solve continuous version (allows fractional values)
2. Branch: If solution is fractional, split into two subproblems:
   • Subproblem A: x[i] ≤ floor(fractional_value)
   • Subproblem B: x[i] ≥ ceil(fractional_value)
3. Bound: Track best integer solution found so far
4. Prune: Discard subproblems that can’t improve on best solution
5. Repeat: Continue until all subproblems explored or pruned

Performance Characteristics

Rule of Thumb: For problems with >100 integer variables, use heuristics (genetic algorithms, simulated annealing) for approximate solutions.

Real-World Application

Logistics: Truck Routing and Loading

Company: Regional distributor with 8 warehouses, 40 delivery locationsChallenge: Minimize delivery costs while meeting delivery windows

Integer Variables:

• Number of trucks to deploy from each warehouse (integer)
• Which customers each truck serves (binary assignment)

Before BusinessMath:

• Manual routing with spreadsheet
• Rules of thumb (“send 3 trucks from Warehouse A”)
• No optimization, high fuel costs

After BusinessMath:

let routingOptimizer = TruckRoutingOptimizer(
    warehouses: warehouseLocations,
    customers: customerOrders,
    trucks: truckFleet
)

let optimalRouting = try routingOptimizer.minimizeCost(
    constraints: [
        .deliveryWindows,
        .truckCapacity,
        .driverHours
    ]
)

Results:

• Fuel costs reduced: 18%
• Trucks required: 12 (down from 15)
• On-time deliveries: 97% (up from 89%)

Try It Yourself

import BusinessMath

// Define projects
struct Project {
	let name: String
	let cost: Double
	let npv: Double
	let requiredStaff: Int
}

let projects_knapsack = [
	Project(name: "New Product Launch", cost: 200_000, npv: 350_000, requiredStaff: 5),
	Project(name: "Factory Upgrade", cost: 180_000, npv: 280_000, requiredStaff: 3),
	Project(name: "Marketing Campaign", cost: 100_000, npv: 150_000, requiredStaff: 2),
	Project(name: "IT System", cost: 150_000, npv: 200_000, requiredStaff: 4),
	Project(name: "R&D Initiative", cost: 120_000, npv: 180_000, requiredStaff: 6)
]

let budget_knapsack = 500_000.0
let availableStaff_knapsack = 10

// Binary decision variables: x[i] ∈ {0, 1} (fund project i or not)
// Objective: Maximize total NPV
// Constraints: Total cost ≤ budget, total staff ≤ available

// Create solver with binary integer specification
let solver_knapsack = BranchAndBoundSolver>(
	maxNodes: 1000,
	timeLimit: 30.0
)

let integerSpec_knapsack = IntegerProgramSpecification.allBinary(dimension: projects_knapsack.count)

// Objective: Maximize NPV (minimize negative NPV)
let objective_knapsack: @Sendable (VectorN) -> Double = { decisions in
	-zip(projects_knapsack, decisions.toArray()).map { project, decision in
		project.npv * decision
	}.reduce(0, +)
}

// Constraint 1: Budget (inequality: totalCost ≤ budget)
let budgetConstraint_knapsack = MultivariateConstraint>.inequality { decisions in
	let totalCost = zip(projects_knapsack, decisions.toArray()).map { project, decision in
		project.cost * decision
	}.reduce(0, +)
	return totalCost - budget_knapsack  // ≤ 0
}

// Constraint 2: Staff availability (inequality: totalStaff ≤ availableStaff)
let staffConstraint_knapsack = MultivariateConstraint>.inequality { decisions in
	let totalStaff = zip(projects_knapsack, decisions.toArray()).map { project, decision in
		project.requiredStaff * Int(decision.rounded())
	}.reduce(0, +)
	return Double(totalStaff) - Double(availableStaff_knapsack)  // ≤ 0
}

// Binary bounds: 0 ≤ x[i] ≤ 1 for each decision variable
let binaryConstraints_knapsack = (0..>.inequality { x in -x[i] },  // x[i] ≥ 0
		MultivariateConstraint>.inequality { x in x[i] - 1.0 }  // x[i] ≤ 1
	]
}

// Solve using branch-and-bound
let result_knapsack = try solver_knapsack.solve(
	objective: objective_knapsack,
	from: VectorN(repeating: 0.5, count: projects_knapsack.count),
	subjectTo: [budgetConstraint_knapsack, staffConstraint_knapsack] + binaryConstraints_knapsack,
	integerSpec: integerSpec_knapsack,
	minimize: true
)

// Interpret results
print("Optimal Project Portfolio:")
print("Status: \(result_knapsack.status)")
var totalCost_knapsack = 0.0
var totalNPV_knapsack = 0.0
var totalStaff_knapsack = 0

for (project, decision) in zip(projects_knapsack, result_knapsack.solution.toArray()) {
	if decision > 0.5 {  // Binary: 1 means funded
		print("  ✓ \(project.name)")
		print("    Cost: \(project.cost.currency(0)), NPV: \(project.npv.currency(0)), Staff: \(project.requiredStaff)")
		totalCost_knapsack += project.cost
		totalNPV_knapsack += project.npv
		totalStaff_knapsack += project.requiredStaff
	}
}

print("\nPortfolio Summary:")
print("  Total Cost: \(totalCost_knapsack.currency(0)) / \(budget_knapsack.currency(0))")
print("  Total NPV: \(totalNPV_knapsack.currency(0))")
print("  Total Staff: \(totalStaff_knapsack) / \(availableStaff_knapsack)")
print("  Budget Utilization: \((totalCost_knapsack / budget_knapsack).percent())")
print("  Nodes Explored: \(result_knapsack.nodesExplored)")

// MARK: - Production Scheduling with Lot Sizes

// Products with setup costs and lot size requirements
struct ProductionRun {
	let product: String
	let setupCost: Double
	let variableCost: Double
	let minimumLotSize: Int
	let demand: Int
}

let productionRuns_prodSched = [
	ProductionRun(product: "Widget A", setupCost: 5_000, variableCost: 10, minimumLotSize: 100, demand: 450),
	ProductionRun(product: "Widget B", setupCost: 3_000, variableCost: 8, minimumLotSize: 50, demand: 280),
	ProductionRun(product: "Widget C", setupCost: 4_000, variableCost: 12, minimumLotSize: 75, demand: 350)
]

let maxProductionCapacity_prodSched = 1000

// Decision variables: number of lots to produce (integer)
// Objective: Minimize total cost (setup + variable)
// Constraints: Meet demand, don't exceed capacity, minimum lot sizes

// Create solver for general integer variables (not just binary)
let productionSolver_prodSched = BranchAndBoundSolver>(
	maxNodes: 5000,
	timeLimit: 60.0
)

// Specify which variables are integers (all of them: lots for each product)
let productionSpec_prodSched = IntegerProgramSpecification(integerVariables: Set(0..) -> Double = { lots in
	zip(productionRuns_prodSched, lots.toArray()).map { run, numLots in
		if numLots > 0 {
			return run.setupCost + (run.variableCost * numLots * Double(run.minimumLotSize))
		} else {
			return 0.0
		}
	}.reduce(0, +)
}

// Constraint 1: Meet demand for each product (inequality: production ≥ demand)
let demandConstraints_prodSched = productionRuns_prodSched.enumerated().map { i, run in
	MultivariateConstraint>.inequality { lots in
		let production = lots[i] * Double(run.minimumLotSize)
		return Double(run.demand) - production  // ≤ 0 means production ≥ demand
	}
}

// Constraint 2: Total production within capacity (inequality: total ≤ capacity)
let capacityConstraint_prodSched = MultivariateConstraint>.inequality { lots in
	let totalProduction = zip(productionRuns_prodSched, lots.toArray()).map { run, numLots in
		numLots * Double(run.minimumLotSize)
	}.reduce(0, +)
	return totalProduction - Double(maxProductionCapacity_prodSched)  // ≤ 0
}

// Bounds: 0 ≤ lots[i] ≤ 20 for each product
let lotBoundsConstraints = (0..>.inequality { x in -x[i] },  // x[i] ≥ 0
		MultivariateConstraint>.inequality { x in x[i] - 20.0 }  // x[i] ≤ 20
	]
}

// Solve
let productionResult_prodSched = try productionSolver_prodSched.solve(
	objective: costObjective_prodSched,
	from: VectorN(repeating: 5.0, count: productionRuns_prodSched.count),
	subjectTo: demandConstraints_prodSched + [capacityConstraint_prodSched] + lotBoundsConstraints,
	integerSpec: productionSpec_prodSched,
	minimize: true
)

print("Optimal Production Schedule:")
print("Status: \(productionResult_prodSched.status)")
for (run, numLots) in zip(productionRuns_prodSched, productionResult_prodSched.solution.toArray()) {
	let lots = Int(numLots.rounded())
	let totalUnits = lots * run.minimumLotSize
	let cost = lots > 0 ? run.setupCost + (run.variableCost * Double(totalUnits)) : 0.0

	print("  \(run.product): \(lots) lots × \(run.minimumLotSize) units = \(totalUnits) units")
	print("    Demand: \(run.demand), Excess: \(totalUnits - run.demand)")
	print("    Cost: \(cost.currency(0))")
}

let totalCost_prodSched = productionResult_prodSched.objectiveValue
print("\nTotal Production Cost: \(totalCost_prodSched.currency(0))")
print("Nodes Explored: \(productionResult_prodSched.nodesExplored)")


// MARK: - Assignment Problem - Workers to Tasks

// Workers and their time to complete each task (hours)
let workers_assignment = ["Alice", "Bob", "Carol", "Dave"]
let tasks_assignment = ["Task 1", "Task 2", "Task 3", "Task 4"]

// Time matrix: timeMatrix[worker][task] = hours
let timeMatrix_assignment = [
	[8, 12, 6, 10],   // Alice's times
	[10, 9, 7, 12],   // Bob's times
	[7, 11, 9, 8],    // Carol's times
	[11, 8, 10, 7]    // Dave's times
]

// Binary assignment matrix: x[i][j] = 1 if worker i assigned to task j
// Objective: Minimize total time
// Constraints: Each worker assigned to exactly one task, each task assigned to exactly one worker

// Flatten assignment matrix to 1D vector for optimizer
let numWorkers_assignment = workers_assignment.count
let numTasks_assignment = tasks_assignment.count
let numVars_assignment = numWorkers_assignment * numTasks_assignment

// Create solver for assignment problem
let assignmentSolver_assignment = BranchAndBoundSolver>(
	maxNodes: 10000,
	timeLimit: 120.0
)

let assignmentSpec_assignment = IntegerProgramSpecification.allBinary(dimension: numVars_assignment)

let assignmentObjective_assignment: @Sendable (VectorN) -> Double = { assignments in
	var totalTime = 0.0
	for i in 0..>.equality { assignments in
		let sum = (0..>.equality { assignments in
		let sum = (0..>.inequality { x in -x[i] },
		MultivariateConstraint>.inequality { x in x[i] - 1.0 }
	]
}

// Solve
let assignmentResult_assignment = try assignmentSolver_assignment.solve(
	objective: assignmentObjective_assignment,
	from: VectorN(repeating: 0.25, count: numVars_assignment),
	subjectTo: workerConstraints_assignment + taskConstraints_assignment + assignmentBounds_assignment,
	integerSpec: assignmentSpec_assignment,
	minimize: true
)

print("Optimal Assignment:")
print("Status: \(assignmentResult_assignment.status)")
var totalTime_assignment = 0
for i in 0.. 0.5 {
			let time = timeMatrix_assignment[i][j]
			print("  \(workers_assignment[i]) → \(tasks_assignment[j]) (\(time) hours)")
			totalTime_assignment += time
		}
	}
}

print("\nTotal Time: \(totalTime_assignment) hours")
print("Nodes Explored: \(assignmentResult_assignment.nodesExplored)")

// Compare to greedy heuristic
print("\nGreedy Heuristic (for comparison):")
var greedyTime_assignment = 0
var assignedWorkers_assignment = Set()
var assignedTasks_assignment = Set()

// Sort all (worker, task, time) pairs by time
var allPairs_assignment: [(worker: Int, task: Int, time: Int)] = []
for i in 0..