Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
Filter
  • 1995-1999  (6)
  • 1995  (6)
  • Englisch  (6)
Datenquelle
Erscheinungszeitraum
  • 1995-1999  (6)
Jahr
Schlagwörter
Sprache
  • Englisch  (6)
  • 1
    facet.materialart.
    Unbekannt
    0/1-Integer Programming: Optimization and Augmentation are Equivalent (1995)
    Details
    Publikationsdatum: 2014-02-26
    Beschreibung: {\def\xnew{x^{\mbox{\tiny new}}}\def\Z{{{\rm Z}\!\! Z}}For every fixed set ${\cal F}\subseteq\{0,1\}^n$ the following problems are strongly polynomial time equivalent: given a feasible point $x\in\cal F$ and a linear objective function $c\in\Z^n$, \begin{itemize} \item find a feasible point $x^*\in\cal F$ that maximizes $cx$ (Optimization), \item find a feasible point $\xnew\in\cal F$ with $c\xnew〉cx$ (Augmentation), and \item find a feasible point $\xnew\in\cal F$ with $c\xnew〉cx$ such that $\xnew-x$ is ``irreducible''\\(Irreducible Augmentation). \end{itemize} This generalizes results and techniques that are well known for $0/1$--integer programming problems that arise from various classes of combinatorial optimization problems.}
    Schlagwort(e): ddc:000
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 2
    facet.materialart.
    Unbekannt
    Test sets and inequalities for integer programs: extended abstract (1995)
    Details
    Publikationsdatum: 2014-02-26
    Beschreibung: This paper presents some connections between test sets and valid inequalities of integer programs. The reason for establishing such relationships is the hope that information (even partial) on one of these objects can be used to get information on the other and vice versa. We approach this study from two directions: On the one hand we examine the geometric process by which the secondary polytope associated with a matrix $A$ transforms to the state polytope as we pass from linear programs that have $A$ as coefficient matrix to the associated integer programs. The second direction establishes the notion of classes of augmentation vectors parallel to the well known concept of classes of facet defining inequalities for integer programs. We show how certain inequalities for integer programs can be derived from test sets for these programs.
    Schlagwort(e): ddc:000
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 3
    facet.materialart.
    Unbekannt
    Routing in Grid Graphs by Cutting Planes (1995)
    Details
    Publikationsdatum: 2020-08-05
    Sprache: Englisch
    Materialart: article , doc-type:article
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 4
    facet.materialart.
    Unbekannt
    Truncated Gröbner Bases for Integer Programming (1995)
    Details
    Publikationsdatum: 2014-02-26
    Beschreibung: {\def\N{{\mbox{{\rm I\kern-0.22emN}}}}In this paper we introduce a multivariate grading of the toric ideal associated with the integer program $min \{ cx : Ax = b, x \in \N^n \}$, and a truncated Buchberger algorithm to solve the program. In the case of $max \{ cx : Ax \leq b, x \leq u, x \in \N^n \}$ in which all data are non-negative, this algebraic method gives rise to a combinatorial algorithm presented in UWZ94}.
    Schlagwort(e): ddc:000
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 5
    facet.materialart.
    Unbekannt
    Quadratic Knapsack Relaxations Using Cutting Planes and Semidefinite Programming: extended abstract (1995)
    Details
    Publikationsdatum: 2014-02-26
    Beschreibung: We investigate dominance relations between basic semidefinite relaxations and classes of cuts. We show that simple semidefinite relaxations are tighter than corresponding linear relaxations even in case of linear cost functions. Numerical results are presented illustrating the quality of these relaxations.
    Schlagwort(e): ddc:000
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
  • 6
    facet.materialart.
    Unbekannt
    Optimum Path Packing on Wheels: The Consecutive Case (1995)
    Details
    Publikationsdatum: 2014-02-26
    Beschreibung: We show that, given a wheel with nonnegative edge lengths and pairs of terminals located on the wheel's outer cycle such that the terminal pairs are in consecutive order, then a path packing, i.~e., a collection of edge disjoint paths connecting the given terminal pairs, of minimum length can be found in strongly polynomial time. Moreover, we exhibit for this case a system of linear inequalities that provides a complete and nonredundant description of the path packing polytope, which is the convex hull of all incidence vectors of path packings and their supersets.
    Schlagwort(e): ddc:000
    Sprache: Englisch
    Materialart: reportzib , doc-type:preprint
    Format: application/postscript
    Format: application/pdf
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    OPUS
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...