Scribd
Upload
13 views15 pages

Understanding Integer Programming Techniques

Integer Programming is an optimization technique that requires some or all variables to be integers. The document discusses methods such as Branch and Bound (B&B) and Cutting Planes, highlighting their steps and the advantages of combining them into a Branch and Cut approach for improved efficiency. It also mentions the complexity of IP problems and the use of heuristics for practical solutions, along with Python libraries for implementation.

Uploaded by

hidegmisi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
13 views15 pages

Understanding Integer Programming Techniques

Integer Programming is an optimization technique that requires some or all variables to be integers. The document discusses methods such as Branch and Bound (B&B) and Cutting Planes, highlighting their steps and the advantages of combining them into a Branch and Cut approach for improved efficiency. It also mentions the complexity of IP problems and the use of heuristics for practical solutions, along with Python libraries for implementation.

Uploaded by

hidegmisi
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Integer Programming

Mihály Hideg, Bence Pór


What is Integer Programming
• A type of optimization where some or all variables must be integers:
Branch🌿 and Bound (B&B) method
1. Relaxation (Bounding Step): 3. Bounding (Pruning Step):
• Solve the LP relaxation of the integer • If a branch’s LP relaxation gives a worse
program solution than an already known integer
• If the solution satisfies the integer solution, discard (prune) it.
constraints, it is optimal. • If the LP relaxation is infeasible, discard the
• If not, use the obtained value a bound. branch.
2. Branching: 4. Repeating Until Optimality:
• Select a fractional variable from the LP • Continue branching and bounding until no
relaxation solution. more subproblems remain.
• Create two new subproblems by imposing • The best integer solution found is the
additional constraints optimal solution.
• Solve the new LP relaxations for these
subproblems.
B&B example

Solution not in the feasible region


B&B example

X=
Fathomed
Cutting Planes Method
Steps of the Cutting ✂️Plane Method
1. Solve the LP relaxation (ignore the integer constraints)
2. Check if the solution is integer if yes, you’re done
3. If not, add a cutting plane (a valid constraint that removes the current
fractional solution but keeps all integer ones)
4. Resolve the LP with the new constraint
5. Repeat steps 2–4 until the solution is integer
Cutting Planes example
Dual simplex
• Minumim ratio test instead of ratio
test
Combining B&B and Cutting Planes
Why Combine them?
• Branch and Bound: Systematic enumeration, can be slow due to large trees.
• Cutting Planes: Strengthens the relaxation, but can be expensive if used alone.
• Combination Advantage: Faster convergence, smaller search trees, and better LP
relaxations.

The common way to combine them is called Branch and Cut.


Branch and Cut
1. Solve the Linear Programming (LP) relaxation.
2. Apply Cutting Planes to tighten relaxation.
3. If solution is integer → done. If not, branch as in B&B.
4. Repeat at each node as needed.
Complexity
• IP problems involve a discrete, non-convex
space, which makes finding the optimal solution
computationally hard (nooooo:()
• Because of complexity, most solvers use
heuristics
• Heuristics are rules-of-thumb or smart shortcuts
• They don’t guarantee the best (optimal) solution…
• …but they often give you a “good enough” solution
quickly.
• Rounding heuristics, Local search, etc.
Python implementation
• Several good libraries
• pulp for simple problems
• Commercial solvers:
• Gurobi, CPLEX, SCIP
• Used in supply chain, scheduling, network
design, finance.
Pulp
Thank you for your kind
attention! ❤️
• Examples from: [Link]

You might also like