 |
|
||||||||||
A Continuous Relaxation Based Heuristic for a Class of Constrained Semi-Assignment Problems
IFOR Events
Seminar:
'Optimization & Applications' (see information & program)
Sep 23 - Dec 16, 2013
| Author | Michael Burkard |
| Abstract |
The constrained semi-assignment problem (C-SAP) is a generalization of the Pseudo-Boolean Optimization problem, where the Boolean variables are replaced by discrete decision variables. Additionally, constraints are given by a set of clauses (similar to those of the Satisfiability problem) which prohibit certain assignments. The C-SAP occurs frequently in real-world applications, but also many combinatorial optimization problems can be formulated in this setting. Since the C-SAP is an NP-hard problem, it cannot be expected that the global optimum can be determined efficiently. For this reason one goal of this work was the development of a heuristic which can be used efficiently for some of those C-SAP instances, for which local search methods are doomed to failure due to their myopia. The newly developed fixed point heuristic (FPH) of this thesis generalizes a method of Cochand for the Generalized Maximum Satisfiability problem such that it can also be applied to constrained maximization problems such as the C-SAP. We will show with the example of the point feature label placement problem that FPH determines also for real-world problems fast good approximate solutions. Essentially FPH is based on a discrete dynamical system which results from iterating an appropriately defined operator. For any fixed starting point a sequence of points is generated in this way. The operator should be chosen such that this sequence converges for a large portion of starting points to a good local maximum of the problem. By an appropriate choice of the operator in FPH, global information can be included in the solution process. Thus FPH has for certain C-SAP instances a big advantage over local search methods, which would fail in such situations due to their local vision and lack of orientation. |
| Download | PDF, PS, PS.gz |
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
