Local branching - Revision history

Fall2024 Team12: /* Step 1: Initialization */

2024-12-16T00:13:00Z

Step 1: Initialization

← Older revision		Revision as of 20:13, 15 December 2024
Line 19:		Line 19:

	==== Step 1: Initialization ====		==== Step 1: Initialization ====
	* Obtain an '''initial feasible solution''' x* using any MILP solver or heuristic method.		* Obtain an '''initial feasible solution''' <math>\mathbf{x}^*</math>using any MILP solver or heuristic method.
	* Define the '''local neighborhood''' using a Hamming distance constraint:		* Define the '''local neighborhood''' using a Hamming distance constraint:

Line 26:		Line 26:
	</math>		</math>

	Here, k is a predefined parameter that controls the size of the neighborhood.		Here, <math>\mathbf{k}</math> is a predefined parameter that controls the size of the neighborhood.

	==== Step 2: Local Optimization ====		==== Step 2: Local Optimization ====
	* Solve the MILP problem restricted by the local neighborhood constraint.		* Solve the MILP problem restricted by the local neighborhood constraint.
	* Use the objective function z to find a better solution x' within the neighborhood.		* Use the objective function <math>\mathbf{z}</math> to find a better solution <math>\mathbf{x}^'</math> within the neighborhood.

	==== Step 3: Update Solution ====		==== Step 3: Update Solution ====
Line 39:		Line 39:
	==== Step 4: Termination ====		==== Step 4: Termination ====
	* Stop the algorithm when:		* Stop the algorithm when:
	**No further improvement in z is achieved after a set number of iterations.		**No further improvement in <math>\mathbf{z}</math> is achieved after a set number of iterations.
	**Computational time exceeds a predefined limit.		**Computational time exceeds a predefined limit.
	**The solution meets predefined quality criteria (e.g., a threshold objective value).		**The solution meets predefined quality criteria (e.g., a threshold objective value).
Line 45:		Line 45:
	=== Assumptions and Conditions ===		=== Assumptions and Conditions ===

	# '''Feasibility''': An initial feasible solution x* must exist before local branching can be applied.		# '''Feasibility''': An initial feasible solution <math>\mathbf{x}^*</math>must exist before local branching can be applied.
	# '''Neighborhood Size''': The parameter k significantly influences performance; a smaller k focuses on local improvements, while a larger k allows broader exploration.		# '''Neighborhood Size''': The parameter k significantly influences performance; a smaller k focuses on local improvements, while a larger k allows broader exploration.
	# '''MILP Solver''': Requires a reliable MILP solver to handle the subproblems.		# '''MILP Solver''': Requires a reliable MILP solver to handle the subproblems.
Line 204:		Line 204:

	==== Step 5: Analyze Results ====		==== Step 5: Analyze Results ====
	Refined Solution (with k=1):		Refined Solution (with <math>\mathbf{k}</math>=1):

	· Neighborhood restricted to solutions with at most one item added or removed.		· Neighborhood restricted to solutions with at most one item added or removed.
Line 234:		Line 234:
	Effect of Changing k		Effect of Changing k

	* Smaller k (e.g., k=1):		* Smaller <math>\mathbf{k}</math> (e.g., <math>\mathbf{k}</math>=1):
	** Only solutions that are very similar to the initial solution are explored.		** 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.		** The optimization focuses on fine-tuning the solution by making small adjustments, such as adding or removing a single item.
Line 240:		Line 240:
	** However, the chance of finding significant improvements is lower, as the search is restricted.		** However, the chance of finding significant improvements is lower, as the search is restricted.

	* Larger k (e.g., k=2,3):		* Larger <math>\mathbf{k}</math> (e.g., <math>\mathbf{k}</math>=2,3):
	** The search neighborhood becomes broader, allowing more variables (items in this case) to change.		** 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.		** 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.		** Larger neighborhoods resemble the global search space, reducing the speed advantage of local branching.

	* Very Large k:		* Very Large <math>\mathbf{k}</math>:
	** If k is too large, the local branching constraint becomes irrelevant, and the method effectively turns into a global search.		** If <math>\mathbf{k}</math> 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.		** This negates the benefits of local branching, as the entire feasible region is explored.

Fall2024 Team 12: /* Step 4: Termination */

2024-12-16T00:08:42Z

Step 4: Termination

← Older revision		Revision as of 20:08, 15 December 2024
Line 39:		Line 39:
	==== Step 4: Termination ====		==== Step 4: Termination ====
	* Stop the algorithm when:		* Stop the algorithm when:
	1. No further improvement in z is achieved after a set number of iterations.		**No further improvement in z is achieved after a set number of iterations.
	2. Computational time exceeds a predefined limit.		**Computational time exceeds a predefined limit.
	3. The solution meets predefined quality criteria (e.g., a threshold objective value).		**The solution meets predefined quality criteria (e.g., a threshold objective value).

	=== Assumptions and Conditions ===		=== Assumptions and Conditions ===

Fall2024 Team 12: /* Step 4: Termination */

2024-12-16T00:08:21Z

Step 4: Termination

← Older revision		Revision as of 20:08, 15 December 2024
Line 39:		Line 39:
	==== Step 4: Termination ====		==== Step 4: Termination ====
	* Stop the algorithm when:		* Stop the algorithm when:
	No further improvement in z is achieved after a set number of iterations.		1. No further improvement in z is achieved after a set number of iterations.
	Computational time exceeds a predefined limit.		2. Computational time exceeds a predefined limit.
	The solution meets predefined quality criteria (e.g., a threshold objective value).		3. The solution meets predefined quality criteria (e.g., a threshold objective value).

	=== Assumptions and Conditions ===		=== Assumptions and Conditions ===

Fall2024 Team 12: /* Step 4: Termination */

2024-12-16T00:08:05Z

Step 4: Termination

← Older revision		Revision as of 20:08, 15 December 2024
Line 38:		Line 38:

	==== Step 4: Termination ====		==== Step 4: Termination ====
	* Stop the algorithm when		* Stop the algorithm when:
	* No further improvement in z is achieved after a set number of iterations.		No further improvement in z is achieved after a set number of iterations.
	* Computational time exceeds a predefined limit.		Computational time exceeds a predefined limit.
	* The solution meets predefined quality criteria (e.g., a threshold objective value).		The solution meets predefined quality criteria (e.g., a threshold objective value).

	=== Assumptions and Conditions ===		=== Assumptions and Conditions ===

Fall2024 Team 12: /* Step 4: Termination */

2024-12-16T00:07:38Z

Step 4: Termination

← Older revision		Revision as of 20:07, 15 December 2024
Line 38:		Line 38:

	==== Step 4: Termination ====		==== Step 4: Termination ====
	* Stop the algorithm when:		* Stop the algorithm when
	* No further improvement in z is achieved after a set number of iterations.		* No further improvement in z is achieved after a set number of iterations.
	* Computational time exceeds a predefined limit.		* Computational time exceeds a predefined limit.

Fall2024 Team 12: /* Step 3: Update Solution */

2024-12-16T00:07:05Z

Step 3: Update Solution

← Older revision		Revision as of 20:07, 15 December 2024
Line 33:		Line 33:

	==== Step 3: Update Solution ====		==== Step 3: Update Solution ====
	* If the local optimization improves the objective function <math>Z(\mathbf{x}') > Z(\mathbf{x}^*)</math>, update the best-known solution:		* If the local optimization improves the objective function <math>Z(\mathbf{x}') > Z(\mathbf{x}^)</math>, update the best-known solution: <math>\mathbf{x}^ = \mathbf{x}'</math>

	<math>\mathbf{x}^* = \mathbf{x}'</math>

	* If no improvement is found, relax or adjust the neighborhood size <math>k</math> and repeat the process.		* If no improvement is found, relax or adjust the neighborhood size <math>k</math> and repeat the process.

Fall2024 Team 12: /* Step 3: Update Solution */

2024-12-16T00:06:47Z

Step 3: Update Solution

← Older revision		Revision as of 20:06, 15 December 2024
Line 33:		Line 33:

	==== Step 3: Update Solution ====		==== Step 3: Update Solution ====
	* If the local optimization improves the objective function \( Z(\mathbf{x}') > Z(\mathbf{x}^*) \), update the best-known solution:		* If the local optimization improves the objective function <math>Z(\mathbf{x}') > Z(\mathbf{x}^*)</math>, update the best-known solution:
	~~<math>~~
	~~\mathbf{x}^* = \mathbf{x}'~~
	~~</math>~~

	* If no improvement is found, relax or adjust the neighborhood size \( k \) and repeat the process.		<math>\mathbf{x}^* = \mathbf{x}'</math>

			* If no improvement is found, relax or adjust the neighborhood size <math>k</math> and repeat the process.

	==== Step 4: Termination ====		==== Step 4: Termination ====

Fall2024 Team 12: /* Step 3: Update Solution */

2024-12-16T00:05:47Z

Step 3: Update Solution

← Older revision		Revision as of 20:05, 15 December 2024
Line 33:		Line 33:

	==== Step 3: Update Solution ====		==== Step 3: Update Solution ====
	* If the local optimization improves the objective function ~~'''~~Z(x') > Z(x)~~'''~~, update the best-known solution x = x'.		* If the local optimization improves the objective function \( Z(\mathbf{x}') > Z(\mathbf{x}^*) \), update the best-known solution:
	* If no improvement is found, relax or adjust the neighborhood size k and repeat the process.		<math>
			\mathbf{x}^* = \mathbf{x}'
			</math>

			* If no improvement is found, relax or adjust the neighborhood size \( k \) and repeat the process.

	==== Step 4: Termination ====		==== Step 4: Termination ====

Fall2024 Team 12: /* Introduction */

2024-12-15T21:32:25Z

Introduction

← Older revision		Revision as of 17:32, 15 December 2024
Line 6:		Line 6:
	https://link.springer.com/article/10.1007/BF00132504</ref>. 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.		https://link.springer.com/article/10.1007/BF00132504</ref>. 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.		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<ref name="ref10">Liu, D., Fischetti, M., & Lodi, A. (2022). Learning to Search in Local Branching. Proceedings of the AAAI Conference on Artificial Intelligence, 36(4), 2224–2232.
			https://doi.org/10.1609/aaai.v36i4.20294</ref>. 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 ==		== Algorithm Discussion ==

Fall2024 Team 12: /* Formal Description */

2024-12-15T21:26:02Z

Formal Description

← Older revision		Revision as of 17:26, 15 December 2024
Line 13:		Line 13:
	=== Formal Description ===		=== 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.		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<ref name="ref9"> Stidsen, T. (n.d.). Local Branching – A Brand New Method. Informatics and Mathematical Modelling / Operations Research, Technical University of Denmark. Retrieved from DTU website. https://www2.imm.dtu.dk/courses/02719/lbr/lbr.pdf</ref>.

	=== Steps of the Algorithm ===		=== Steps of the Algorithm ===