| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Mixed-integer linear representability, disjunctions, and Chvatal functions --- modeling implications | Amitabh Basu
; Kipp Martin
; Christopher Thomas Ryan
; Guanyi Wang
; | Date: |
19 Nov 2017 | Abstract: | Jeroslow and Lowe gave an exact geometric characterization of subsets of
$mathbb{R}^n$ that are projections of mixed-integer linear sets, also known as
MILP-representable or MILP-R sets. We give an alternate algebraic
characterization by showing that a set is MILP-R {em if and only if} the set
can be described as the intersection of finitely many {em affine Chvatal
inequalities} in continuous variables (termed AC sets). These inequalities are
a modification of a concept introduced by Blair and Jeroslow. Unlike the case
for linear inequalities, allowing for integer variables in Chvatal inequalities
and projection does not enhance modeling power. We show that the MILP-R sets
are still precisely those sets that are modeled as affine Chvatal inequalites
with integer variables. Furthermore, the projection of a set defined by affine
Chvatal inequalites with integer variables is still an MILP-R set.
We give a sequential variable elimination scheme that, when applied to a
MILP-R set yields the AC set characterization. This is related to the
elimination scheme of Williams and Williams-Hooker, who describe projections of
integer sets using emph{disjunctions} of affine Chvatal systems. We show that
disjunctions are unnecessary by showing how to find the affine Chvatal
inequalities that cannot be discovered by the Williams-Hooker scheme. This
allows us to answer a long-standing open question due to Ryan (1991) on
designing an elimination scheme to represent finitely-generated integral
monoids as a system of Chvatal inequalities emph{without} disjunctions.
Finally, our work can be seen as a generalization of the approach of Blair and
Jeroslow, and Schrijver for constructing consistency testers for integer
programs to general AC sets. | Source: | arXiv, 1711.7028 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |