Wir präsentieren und evaluieren eine neuartige Methode, die gute Start-Lösungen für die lokale Suche generiert. Die Start-Lösung wird von einem bestimmten linearen Programm (LP) bestimmt, das eine Modifikation des zugrunden liegenden Problems ist. Wir betrachten eine nicht-lineare Formulierung des Problems und wenden kleine Änderungen an, um die nicht-linearen Bestandteile der Formulierung in lineare Bestandteile umzuwandeln. Damit die Technik angewendet werden kann, ist es notwendig, dass die optimalen Basis-Lösungen des LPs zulässig für das primäre Optimierungsproblem sind. Wir untersuchen vier Optimierungsprobleme: das gerichtete Max-Cut Problem mit einem Start- und einem Endknoten, und drei Variationen des Max-k-SAT Problems mit k=2, k=3 und k=4. In jedem Fall definieren wir die Modifikation so, dass die Eckpunkte des resultierenden LP ganzzahlig sind, und dass die Simplex-Methode nicht im Unendlichen endet. Zum Vergleich mit unserer Technik benutzen wir eine wiederholte lokale Suche mit zufälligen Start-Lösungen. Unsere Technik produziert konsequent Lösungen, deren Ziel-Werte nicht allzu weit von den besten Lösungen aus wiederholten zufälligen Starts sind. Das überraschende Maß an Stabilität und der Einheitlichkeit der Ergebnisse in allen unseren Experimenten mit verschiedenen Klassen lassen den Schluss zu, dass wir konsequent nahezu optimale Lösungen erzielen. Darüber hinaus bestätigt eine Umsetzung unserer Technik auf das längste Pfad Problem zwischen zwei angegebenen Knoten (in denen wir das LP durch den Einbau der Fluss-Konsistenz-Ungleichungen herstellen) unsere empirische Befunde. Auf der anderen Seite ist die Laufzeit unserer Technik sehr klein, so dass diese sehr effizient ist.