Integer programming formulation of combinatorial optimization problems |
| |
Authors: | Toshimde Ibaraki |
| |
Institution: | Department of Applied Mathematics and Physics, Faculty of Engineering, Kyoto University, Kyoto, Japan |
| |
Abstract: | This paper considers in a somewhat general setting when a combinatorial optimization problem can be formulated as an (all-integer) integer programming (IP) problem. The main result is that any combinatorial optimization problem can be formulated as an IP problem if its feasible region S is finite but there are many rather sample problems that have no IP formulation if their S is infinite. The approach used for finite S usually gives a formulation with a relatively small number of additional variables for example, an integer polynomial of n 0?1 variables requires at most n + 1 additional variables by our approach, whereas 2n - (n + 1) additional variables at maximum are required by other existing methods. Finally, the decision problem of deciding whether an arbitrarily given combinatorial optimization problem has an IP formulation is considered and it is shown by an argument closely related to Hilbert's tenth problem (drophantine equations) that no such algorithm exists. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|