Mixed-integer problems with simple constraints solved efficiently
Mixed-integer dual network problems are solvable in strongly polynomial time
Data Structures and Algorithms
Summary
Some optimization problems where decisions can be both whole numbers and fractions are usually hard to solve. The authors found that if the problem’s constraints are very simple, with only two numbers per condition and a special matrix kind, these problems can be solved quickly using a particular mathematical technique. They did this by converting the problem into one about minimizing a special kind of function called an L-convex function. This finding gives a new efficient way to solve some mixed problems that were previously difficult.
What this means in practice
- •For network schedulers: Solve mixed-integer flow problems with constraints involving at most two variables per condition more efficiently, aiding network resource allocation tasks.
- •For logistics planners: Improve routing and scheduling decisions that can be modeled with simple mixed-integer constraints enabled by this efficient solving approach.
A theory result. No direct application yet.
Authors
Giacomo Zambelli
Abstract
In this paper we show that mixed-integer linear programming is solvable in strongly polynomial time if the constraint matrix is totally unimodular with at most two nonzero entries in every row. This is done by reducing the problem to an instance of minimization of an $L$-convex function.