127. LP reformulation of combinatorial optimization problems aided by combinatorial methods
Invited abstract in session WC-3: Mixed Integer Programming I, stream Discrete Optimization.
Wednesday, 10:00 - 11:30Room: C 104
Authors (first author is the speaker)
| 1. | Bogdan Zavalnij
|
| Renyi Institute of Mathematics | |
| 2. | Sandor Szabo
|
| Institute of Mathematics and Informatics, University of Pecs |
Abstract
Linear Programming (LP) is a well known technique for solving different optimization problems, including combinatorial optimization problems (COP). In this latter case we use Integer Linear Programming (ILP) or binary (0-1) LP to solve the program to optimality, or use the real (or continuous) relaxation of the discrete program to establish an upper bound for a maximization problem or a lower bound for a minimization problem. Typically a COP can be reduced to a discrete LP in more than one ways. This is also true for the Maximum Clique Problem (MCP) or k-clique problem (k-CP), which we shall use to illustrate our considerations.
The known discrete LP formulations of a COP usually model the problem in some straightforward manner. The known LP formulations of the MCP based on compiling lists of non-edges, sets non-neighbors of nodes, independent sets (or their extensions) of the underlying graph.
We would like to point out, that some more involved combinatorial procedures can aid of setting up new LP reformulations. The point is, that using some fast (usually polynomial) algorithm can discover information that can be added to the LP reformulation, and thus make the program more emanable for the modern LP solvers. The auxiliary combinatorial procedures, we will use, are legal coloring and b-fold coloring. Working with the so-called dominance relations and its generalizations; applying the struction transformation will further improve the LP reformulation.
Keywords
- Mixed integer nonlinear optimization
Status: accepted
Back to the list of papers