Szabó, Sándor and Zaválnij, Bogdán (2022) Clique relaxations of zero-one linear programs. In: Middle-European Conference on Applied Theoretical Computer Science (MATCOS-22), 2022.10.13-2022.10.14, Koper.
|
Text
abc10-1.pdf Download (167kB) | Preview |
Abstract
In an earlier work a so-called conflict graph was associated to a given zero-one linear program basically to accumulate information to construct cuts to speed up the solution of the program. Later it was noticed that the conflict graph can be used in fixing values of variables and fathoming partial solutions in enumerative type solvers. In this paper we will show that the conflict graph helps in dividing dividing a zero-one linear program into independent smaller instances and so it opens a way for a parallel solution. Further the conflict graph suggests certain possibilities for preprocessing and simplifying the given zero-one linear program.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Uncontrolled Keywords: | discrete optimization, clique, independent set, weighted clique, zero-one program, parallel computing, preprocessing |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 21 Mar 2023 08:41 |
| Last Modified: | 21 Mar 2023 08:41 |
| URI: | http://real.mtak.hu/id/eprint/162449 |
Actions (login required)
 |
Edit Item |
