'Optimization & Applications' (see information & program)
Sep 23 - Dec 16, 2013
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|
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
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.