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 $\mathbf {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, $\mathbf {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 $\mathbf {z}$ to find a better solution $\mathbf {x} ^{'}$ within the neighborhood.

Step 3: Update Solution

• If the local optimization improves the objective function $Z(\mathbf {x} ')>Z(\mathbf {x} ^{*})$, update the best-known solution: $\mathbf {x} ^{*}=\mathbf {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 $\mathbf {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 $\mathbf {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.

Problem Resolution

Step 1: Formulate the Problem

Let:

$\ x_{i}\in \{0,1\}$: Decision variable, where $\ x_{i}=1$ if item $\ i$ is stolen, and $\ x_{i}=0$ otherwise.

$\ w_{i}$: Weight of item $\ i$

$\ v_{i}$: Value of item $\ i$

$\ W$: Maximum weight capacity of the knapsack.

Objective Function:

Maximize: $\sum _{i=1}^{n}v_{i}x_{i}$

Constraints:

Total weight: $\sum _{i=1}^{n}w_{i}x_{i}\leq W$

Binary decision variables: $x_{i}\in \{0,1\},\ \forall i$

Step 2: Problem Data

Items data:

Weights: $\ w$ = [2,3,1,4,5]

Values: $\ v$ = [10,15,7,25,30]

Knapsack capacity: $\ W$ = 8

Step 3: Code Implementation

from pyomo.environ import *

# Data

weights = [2, 3, 1, 4, 5] # Weights of items

values = [10, 15, 7, 25, 30] # Values of items

capacity = 8 # Maximum capacity of the knapsack

num_items = len(weights)

# Step 1: Initial Problem Setup

model = ConcreteModel()

# Decision variables: x[i] = 1 if item i is stolen, 0 otherwise

model.x = Var(range(num_items), domain=Binary)

# Objective: Maximize total value

model.profit = Objective(expr=sum(values[i] * model.x[i] for i in range(num_items)), sense=maximize)

# Knapsack capacity constraint

model.capacity = Constraint(expr=sum(weights[i] * model.x[i] for i in range(num_items)) <= capacity)

# Solve the initial problem

solver = SolverFactory('glpk')

solver.solve(model)

# Extract the initial solution

initial_solution = [int(model.x[i]()) for i in range(num_items)]

initial_value = sum(values[i] * initial_solution[i] for i in range(num_items))

print("Initial Solution:", initial_solution)

print("Initial Value:", initial_value)

# Step 2: Add Local Branching Constraint

# Auxiliary variables for absolute value linearization

model.z = Var(range(num_items), domain=NonNegativeReals)

# Linearize absolute value constraints

model.abs_constraints = ConstraintList()

for i in range(num_items):

model.abs_constraints.add(model.z[i] >= model.x[i] - initial_solution[i])

model.abs_constraints.add(model.z[i] >= initial_solution[i] - model.x[i])

# Local branching constraint: At most k changes allowed

k = 1

model.local_branching = Constraint(expr=sum(model.z[i] for i in range(num_items)) <= k)

# Solve the problem with the local branching constraint

solver.solve(model)

# Extract the refined solution

refined_solution = [int(model.x[i]()) for i in range(num_items)]

refined_value = sum(values[i] * refined_solution[i] for i in range(num_items))

print("Refined Solution:", refined_solution)

print("Refined Value:", refined_value)

Step 4: Add Local Branching Constraint

After obtaining the initial solution, the thief refines it by exploring a neighborhood around the initial solution. The local branching constraint is:

$\sum _{i\in S}(1-x_{i})+\sum _{i\notin S}x_{i}\leq k$

For linearization: Add auxiliary variables z_i to represent the absolute difference between the initial solution and the current solution:

$z_{i}\geq x_{i}-x_{i}^{\text{initial}}$

$z_{i}\geq x_{i}^{\text{initial}}-x_{i}$

Step 5: Analyze Results

Refined Solution (with $\mathbf {k}$=1):

· Neighborhood restricted to solutions with at most one item added or removed.

· If a better solution exists in this neighborhood, it will be found.

· If no better solution exists within the local branching neighborhood, the initial solution is already optimal within the restricted region.

Metric	Initial Solution	Refined Solution (k=1)
Selected Items	[1, 0, 1, 0, 1]	[1, 0, 1, 0, 1]
Total Value	47	47
Computation Time	0.065 seconds	0.012 seconds

This indicates local branch method is more efficient in time.

Effect of Changing k

• Smaller $\mathbf {k}$ (e.g., $\mathbf {k}$=1):
  • Only solutions that are very similar to the initial solution are explored.
  • The optimization focuses on fine-tuning the solution by making small adjustments, such as adding or removing a single item.
  • This is faster since fewer nodes in the search tree are explored.
  • However, the chance of finding significant improvements is lower, as the search is restricted.

• Larger $\mathbf {k}$ (e.g., $\mathbf {k}$=2,3):
  • The search neighborhood becomes broader, allowing more variables (items in this case) to change.
  • This increases the chance of finding better solutions but also increases the computational time.
  • Larger neighborhoods resemble the global search space, reducing the speed advantage of local branching.

• Very Large $\mathbf {k}$:
  • If $\mathbf {k}$ is too large, the local branching constraint becomes irrelevant, and the method effectively turns into a global search.
  • This negates the benefits of local branching, as the entire feasible region is explored.

Trade-Offs in This Problem

• Speed vs. Solution Quality:
  • Smaller k results in faster optimization because the solver only explores a small subset of the feasible region.
  • Larger k allows for broader exploration, increasing the chance of finding better solutions but also increasing computational effort.
• Knapsack-Specific Considerations:
  • The knapsack problem often has multiple near-optimal solutions with small differences in total value.
  • Local branching works well here because it fine-tunes the solution by exploring close variations (e.g., swapping high-value, low-weight items).
• When Local Branching is Effective:
  • A good initial solution is available.
  • The feasible region is large, making global search slow.
• Small changes in the solution can yield significant improvements.

Application

Local Branching is a powerful optimization strategy for to solving MILP optimization problems, with applications spanning industries like logistics, manufacturing, energy, data science, and engineering. In particular, for challenges such as scheduling, production planning, nesting and transportation logistics where decision-makers look for high-quality solutions within reasonable computational times. Focusing on local improvements, organizations are able to achieve better performance with low costs.

Railway Crew Scheduling: Local branching has advantages compared to traditional optimization methods that often use branch-and-bound or cutting-plane approaches. In the railway crew scheduling traditional methods struggle with the sheer size and complexity of these problems due to the large number of binary decision variables. Local branching introduces constraints to find solutions in a smaller and more manageable sample space without sacrificing the quality of the solution. This approach enables the solver to find solutions with fewer scheduling conflicts and better adherence to operational constraints compared to standard methods.

Inventory Routing Problems: A study was conducted on how local branching could lead to better solution for Inventort routing problems, which often involve constant changes. Results showed that local branching helped to reach alternative solutions fast and effectively with small changes to the current solution since it searched within a small range of solution space. It found routes and schedules that better balanced inventory costs and routing efficiency, leading to substantial savings in operational costs.

Some of the most well-known software and platforms include ILOG CPLEX, which has been used in the Railwat Crew Scheduling. Another one is Gurobi—a leading MIP solver that has been used in adaptations of Local Branching for modern applications.

Conclusion

Local Branching is a major advance in the area of mixed-integer linear programming, providing a strong method for solving large and complex optimization problems. By constraining the search space to a region around the current solution, it increases computational efficiency while retaining or even improving the solution quality. For these reasons, the approach is particularly useful in practical applications where fast convergence is vital. Local Branching is also effective when applied to other areas such as logistics, manufacturing, and energy management in solving real-world optimization problems involving scheduling, resource allocation, and operational efficiency.

Local Branching can also help the optimization process in reducing the search space for faster convergence and often to better solutions than classical global approaches. Future research on Local Branching could benefit from incorporating advanced machine-learning methods that dynamically adjust neighborhood sizes in order to increase its adaptability, efficiency, and scalability for different optimization problems.

References

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