Discrete Optimization

Discrete optimization deals with optimization of a discrete-domain function. The objective is to maximize or minimize the function over its domain. The domain may be subjected to additional constraints. Due to discrete domain, functions cannot be optimized by taking its derivative. This makes the problem challenging compared to the optimization of functions with continuous domain.

Linear mixed integer programming

Linear mixed integer programming has both continuous and discrete unknown variables. Also, the objective function and constraints are linear in unknown variables.

\[\max cx+hy: Ax+Gy\leq b, x\in Z^n_+, y\in \mathbb{R}^p_+\]

Linear pure integer programming

Linear mixed integer programming has discrete unknown variables. Also, the objective function and constraints are linear in unknown variables.

\[\max cx: Ax\leq b, x\in Z^n_+\]

Linear programming

Linear mixed integer programming has continuous unknown variables. Also, the objective function and constraints are linear in unknown variables.

\[\max hy: Gy\leq b, y\in \mathbb{R}^p_+\]

Combinatorial optimization

Combinatorial optimization problems aim is to calculate the best possible subset of a set; a value function assigns value to each possible subset. Let \(N=\{1,2,\ldots,n\}, v=(v_1,v_2,\ldots,v_n)\). For \(F\subset N, v(F):=\sum_{i\in F}v_i\). A combinatorial optimization problem is

\[\max v(F), F\in\mathcal{F}\]

An example of a combinational optimization is 2d packing problem. In 2d packing problem, the challenge is to efficiently place 2d shapes on a sheet without overlaping two shapes and minimizing overall sheet wastage.

Standard problems

Knapsack problem

Knapsack problem is an example of combinatorial optimization problem . There are \(n\) objects with with cost vector \(c_1,c_2,\ldots,c_n\) and value vector \(v_1,v_2,\ldots,v_n\). Let \(x\in B^n\) be a binary vector. Given a budget \(b \in \mathbb{R}^+\), the knapsack problem is

\[\max_{x\in B^n} \sum_{i=1}^n v_i x_i: \sum_i^n x_i c_i \leq b\]

Assignment and matching problem

Assignment and matching problem is an example of combinatorial optimization problem . There are \(n\) people and \(m\) jobs where \(n\geq m\). Cost of person \(j\) doing job \(i\) is \(c_{ij}\). \(x\in B^{m\times n}\) is a binary matrix. Each job must be done by exactly one person. Each person can do at max one job. The assignment problem is

\[\min_{x\in B^{m\times n}} \sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij}: \sum_{i=1}^m x_{ij}=1, \sum_{j=1}^n x_{ij}\leq 1\]

Solution Techniques

There are multiple approaches to solving discrete optimization problem.

Branch and bound for solving knapsack problem

Branch and bound method solves the combinatorial optimization problems where the solution space is discrete and large. It is applied to problems such as 0/1 Knapsack, Traveling Salesman, Integer Programming, and Job Scheduling. The core idea is to explore the solution space as a tree where each node represents a partial solution. The method consists of branching into subproblems and using bounds to eliminate those subproblems that cannot yield better results than the current best solution.

The process starts with an initial bound (typically from a greedy or relaxed solution) and a root node representing an empty or initial state. The algorithm maintains a list of active nodes (candidates for expansion). At each step:

One node is selected and expanded (branching into further subproblems).
A bound (upper or lower) is computed for each new node using a relaxation or estimate.
Nodes whose bounds are worse than the current best known solution are pruned.
The best feasible solution found during the process is continuously updated.

In the 0/1 Knapsack Problem, each node corresponds to a decision at a certain item (include or exclude). The upper bound can be calculated using the fractional knapsack solution. Branching continues only if the bound is greater than the current best value. Once all nodes are either processed or pruned, the best recorded solution is returned.

Branch and Bound guarantees finding the optimal solution but can be slow for large instances unless effective bounding and pruning strategies are used.

Python code for branch and bound method for solving knapsack problem

import heapq

# Item structure
class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value / weight

# Node structure for the Branch and Bound tree
class Node:
    def __init__(self, level, value, weight, bound, selected):
        self.level = level        # index of the item we're on
        self.value = value        # total value so far
        self.weight = weight      # total weight so far
        self.bound = bound        # upper bound of max value from this node
        self.selected = selected  # list showing which items are included

    # For priority queue to work with max-heap behavior (negate bound)
    def __lt__(self, other):
        return self.bound > other.bound

# Compute upper bound on value in subtree starting at node
def bound(node, capacity, items):
    if node.weight > capacity:
        return 0

    bound_value = node.value
    total_weight = node.weight
    i = node.level + 1

    # Add full items while capacity allows
    while i < len(items) and total_weight + items[i].weight <= capacity:
        total_weight += items[i].weight
        bound_value += items[i].value
        i += 1

    # Add fractional part of next item if partially fits
    if i < len(items):
        bound_value += (capacity - total_weight) * items[i].ratio

    return bound_value

# Branch and Bound solution for 0/1 Knapsack
def knapsack_branch_and_bound(values, weights, capacity):
    n = len(values)
    items = sorted([Item(v, w) for v, w in zip(values, weights)],
                   key=lambda x: x.ratio, reverse=True)

    max_value = 0
    best_selection = []

    # Priority queue for max-heap (negate bound for max)
    queue = []

    # Start with root node
    root = Node(level=-1, value=0, weight=0, bound=0, selected=[])
    root.bound = bound(root, capacity, items)
    heapq.heappush(queue, root)

    while queue:
        node = heapq.heappop(queue)

        if node.bound <= max_value or node.level == n - 1:
            continue  # Prune node if bound not promising or at leaf

        # Consider including next item
        next_level = node.level + 1
        item = items[next_level]

        # Left child: include the item
        weight_with = node.weight + item.weight
        value_with = node.value + item.value
        selected_with = node.selected + [1]

        if weight_with <= capacity and value_with > max_value:
            max_value = value_with
            best_selection = selected_with + [0] * (n - len(selected_with))

        bound_with = bound(Node(next_level, value_with, weight_with, 0, []),
                           capacity, items)

        if bound_with > max_value:
            heapq.heappush(queue, Node(next_level, value_with,
                                       weight_with, bound_with, selected_with))

        # Right child: exclude the item
        selected_without = node.selected + [0]
        bound_without = bound(Node(next_level, node.value, node.weight, 0, []),
                              capacity, items)

        if bound_without > max_value:
            heapq.heappush(queue, Node(next_level, node.value,
                                       node.weight, bound_without, selected_without))

    return max_value, best_selection

# Example usage
values = [60, 100, 120]
weights = [10, 20, 40]
capacity = 50

max_val, selection = knapsack_branch_and_bound(values, weights, capacity)
print("Maximum value:", max_val)
print("Item selection (1=included, 0=excluded):", selection)

Output of the python code for branch and bound for solving knapsack problem

Maximum value: 180
Item selection (1=included, 0=excluded): [1, 0, 1]

Tutorial on branch and bound method for solving knapsack problem

Knapsack problem using branch and bound method

is a tutorial on solving the knapsack problem using branch and bound method.

Dynamic programming for solving knapsack problem

The dynamic programming approach for solving knapsack problem breaks the problem into smaller overlapping subproblems and builds up the solution using a table. It avoids redundant computations by storing intermediate results.

A two-dimensional table is created where each row represents items considered so far, and each column represents a possible capacity from 0 up to the maximum. The value stored in each cell represents the maximum value achievable with that number of items and that specific capacity. For each item and each capacity:

If the item's weight is more than the current capacity, it is excluded, and the value from the previous item is retained.
If the item's weight fits, the algorithm chooses the maximum between including the item (adding its value and reducing the capacity) or excluding it.

After processing all items and capacities, the bottom-right cell of the table contains the optimal total value that can be carried in the knapsack. This method guarantees an optimal solution and has a time and space complexity of O(nW), where n is the number of items and W is the capacity of the knapsack.

Python code for dynamic programming for solving knapsack problem

def knapsack_dp(values, weights, capacity):
    n = len(values)

    # Create a 2D table where dp[i][w] stores the maximum value
    # for the first i items and capacity w
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    # Fill the dp table
    for i in range(1, n + 1):  # Loop through items
        for w in range(capacity + 1):  # Loop through all capacities from 0 to W
            if weights[i - 1] > w:
                # If item i-1 can't fit in capacity w, exclude it
                dp[i][w] = dp[i - 1][w]
            else:
                # Otherwise, take the maximum of excluding or including the item
                dp[i][w] = max(
                    dp[i - 1][w],  # exclude the item
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]  # include it
                )

    return dp[n][capacity]  # The bottom-right value is the maximum total value

# Example usage
values = [60, 100, 120]
weights = [10, 20, 40]
capacity = 50

max_value = knapsack_dp(values, weights, capacity)
print("Maximum value:", max_value)

Output of python code for dynamic programming for solving knapsack problem

Maximum value: 180

Tutorial on dynamic programming for solving knapsack problem

Knapsack problem using dynamic programming

is a tutorial on solving the knapsack problem using dynamic programming.

Or-tools: Efficient Python code for knapsack problem

Or-tools supports both solver: dynamic programming (pywrapknapsack_solver.KnapsackSolver.KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER) and branch and bound method (pywrapknapsack_solver.KnapsackSolver.KNAPSACK_MULTIDIMENSION_BRANCH_AND_BOUND_SOLVER) for solving the knapsack problem. For deployment, use or-tools solver as they are highly efficient.

# Import the knapsack solver module from OR-Tools
from ortools.algorithms import pywrapknapsack_solver

# -----------------------------------------------
# Input data for the knapsack problem
# -----------------------------------------------

# List of item values (profits)
values = [360, 83, 59, 130, 431, 67, 230, 52, 93, 125]

# List of item weights; OR-Tools supports multidimensional capacity,
# so weights are given as a list of lists (1D in this case)
weights = [[7, 0, 30, 22, 80, 94, 11, 81, 70, 64]]

# Maximum capacity of the knapsack (in the same order as weights)
capacities = [850]

# -----------------------------------------------
# Create and configure the solver
# -----------------------------------------------

# Choose the solver type: Dynamic Programming in this case
solver = pywrapknapsack_solver.KnapsackSolver(
    pywrapknapsack_solver.KnapsackSolver.KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
    'KnapsackExample'
)

# Initialize the solver with values, weights, and capacities
solver.Init(values, weights, capacities)

# -----------------------------------------------
# Solve the problem
# -----------------------------------------------

# Compute the maximum total value (profit)
computed_value = solver.Solve()

# -----------------------------------------------
# Retrieve the solution details
# -----------------------------------------------

# Lists to store the selected item indices and their weights
packed_items = []
packed_weights = []
total_weight = 0

# Check each item to see if it is included in the best solution
for i in range(len(values)):
    if solver.BestSolutionContains(i):
        packed_items.append(i)
        packed_weights.append(weights[0][i])
        total_weight += weights[0][i]

# -----------------------------------------------
# Print the solution
# -----------------------------------------------

print("Total value =", computed_value)          # Maximum total value achieved
print("Total weight:", total_weight)            # Total weight used
print("Packed items:", packed_items)            # Indices of items included
print("Packed weights:", packed_weights)        # Corresponding weights

Books

George Nemhauser and Laurence Wolsey, Integer and Combinatorial Optimization

Online courses

Discrete Optimization on Coursera by Professor Pascal Van Hentenryck and Dr. Carleton Coffrin

Author

Anurag Gupta is an M.S. graduate in Electrical and Computer Engineering from Cornell University. He also holds an M.Tech degree in Systems and Control Engineering and a B.Tech degree in Electrical Engineering from the Indian Institute of Technology, Bombay.

Comment

Past Comments

No comments yet. Be the first!