Local branching

Author: Bruce Wang (bw549), Ashley Yang (yy2333), Pufan You (py234), Sandro Xu (sx289), Yihan Wang (yw2744) (ChemE 6800 Fall 2020)

Introduction

Mixed-Integer Linear Programming (MILP) is a sophisticated optimization model aimed at solving problems that involve both discrete decision and continuous variables, where the discrete variables are often constrained to take on integer values. Local Branching is a heuristic that has been explicitly developed to enhance the effectiveness of solving MILP problems by focusing the optimization search in a defined neighborhood around the current incumbent solution. This approach has special advantages for large-scale, computationally intensive MILP instances because it allows one to explore the solution space in a more focused manner, improving the solution quality while still keeping the computations tractable.

Furthermore, local branching was introduced as a refinement heuristic for dealing with the computational tractability issues that global optimization methods, such as branch-and-bound, became widely resource-consuming for large instances of a problem. One of the main motivations to study Local Branching is its ability to do iterative solution improvement, thereby making it possible to get good solutions fast with MILP solvers. Thus, local branching becomes extremely important when applied to domains demanding quick and reliable decision-making, more precisely within logistics optimization, production scheduling, and resource planning.

Algorithm Discussion

Formal Description

Local Branching is an optimization strategy designed for MILP problems. It iteratively refines solutions by restricting the search space to a local neighborhood around the current best solution. This approach aims to improve computational efficiency while achieving better-quality solutions.

Steps of the Algorithm

Step 1: Initialization

• Obtain an initial feasible solution x* using any MILP solver or heuristic method.
• Define the local neighborhood using a Hamming distance constraint:

$\sum _{i\in I:x_{i}^{*}=1}(1-x_{i})+\sum _{i\in I:x_{i}^{*}=0}x_{i}\leq k$

Here, k is a predefined parameter that controls the size of the neighborhood.

Step 2: Local Optimization

• Solve the MILP problem restricted by the local neighborhood constraint.
• Use the objective function z to find a better solution x' within the neighborhood.

Step 3: Update Solution

• If the local optimization improves the objective function Z(x') > Z(x*), update the best-known solution x* = x'.
• If no improvement is found, relax or adjust the neighborhood size k and repeat the process.

Step 4: Termination

• Stop the algorithm when:

 * No further improvement in z is achieved after a set number of iterations.
 * Computational time exceeds a predefined limit.
 * The solution meets predefined quality criteria (e.g., a threshold objective value).

Assumptions and Conditions

1. Feasibility: An initial feasible solution x* must exist before local branching can be applied.
2. Neighborhood Size: The parameter k significantly influences performance; a smaller k focuses on local improvements, while a larger k allows broader exploration.
3. MILP Solver: Requires a reliable MILP solver to handle the subproblems.
4. Problem Structure: Works best for problems where solutions are sparse and where local improvements can significantly impact the objective.

Numerical Examples

Example: Knapsack Refinement

A thief wants to steal items from a shop but is limited by a maximum weight capacity. There are 5 items available, each with a specific weight and value. The objective is to maximize the value of items stolen while staying within the weight limit.

Item Details:

• Weights: [2,3,1,4,5]
• Values: [10,15,7,25,30]
• Weight Capacity: 8

Tasks:

1. Solve the knapsack problem using a binary MIP formulation:

    ${\text{Maximize: }}\sum _{i=1}^{5}v_{i}x_{i}$     ${\text{Subject to: }}\sum _{i=1}^{5}w_{i}x_{i}\leq 8,\,x_{i}\in \{0,1\}$

1. Define a local branching constraint for a neighborhood where at most 1 item can be swapped:

    $\sum _{i\in S}(1-x_{i})+\sum _{i\notin S}x_{i}\leq 1$ Solve to refine the solution.

References

Stewards: Nathan Preuss, Wei-Han Chen, Tianqi Xiao, Guoqing Hu