Open Collections

Description

Mixed-integer programming is a mathematical framework for modeling and solving both theoretical and real-world optimization problems. In essence, a mixed-integer program (MIP) represents an optimization problem by a polyhedron P and a set of coordinates I. The goal is to find a point in P whose coordinates in I are integers and that maximizes a given linear objective function. This approach combines combinatorial aspects (mixed-integer points) with a geometric framework (polyhedra). The primary method for solving MIPs is a backtracking search that recursively divides the original problem into a sequence of more manageable subproblems until an optimal solution is found. This method, known as the branch-and-bound algorithm, accounts for the combinatorial nature of the problem. It can be strengthened by adding linear inequalities that eliminate regions of the polyhedron P which do not contain mixed-integer points. These additional constraints, called cutting planes, exploit the geometric structure of MIPs. Although the fundamental paradigms of branch-and-bound and cutting planes are conceptually simple, their implementation involves many degrees of freedom. Despite more than 75 years of research, numerous open questions remain, such as: - How should subproblems be split in branch-and-bound to minimize the number of generated subproblems? - How can strong cutting planes be identified efficiently, and when should they be added to a MIP? - Is it possible to discard certain subproblems in branch-and-bound without losing all optimal solutions? In this presentation, I will provide an accessible overview of branch-and-bound and cutting planes. Afterwards, I will highlight recent research trends that aim to shed light on these questions.