A Probabilistic Study of 3-SATISFIABILITY

Simple item page
dc.contributor.authorAytemiz, Tevfiken
dc.contributor.committeecochairJacobson, Sheldon H.en
dc.contributor.committeecochairKoelling, C. Patricken
dc.contributor.committeememberYe, Keyingen
dc.contributor.committeememberMeller, Russell D.en
dc.contributor.committeememberBish, Ebru K.en
dc.contributor.departmentIndustrial and Systems Engineeringen
dc.date.accessioned2014-03-14T20:13:43Zen
dc.date.adate2001-07-06en
dc.date.available2014-03-14T20:13:43Zen
dc.date.issued2001-06-28en
dc.date.rdate2002-07-06en
dc.date.sdate2001-07-04en
dc.description.abstractDiscrete optimization problems are defined by a finite set of solutions together with an objective function value assigned to each solution. Local search algorithms provide useful tools for addressing a wide variety of intractable discrete optimization problems. Each such algorithm offers a distinct set of rules to intelligently exploit the solution space with the hope of finding an optimal/near optimal solution using a reasonable amount of computing time. This research studies and analyses randomly generated instances of 3-SATISFIABILITY to gain insights into the structure of the underlying solution space. Two random variables are defined and analyzed to assess the probability that a fixed solution will be assigned a particular objective function value in a randomly generated instance of 3-SATISFIABILITY. Then, a random vector is defined and analyzed to investigate how the solutions in the solution space are distributed over their objective function values. These results are then used to define a stopping criterion for local search algorithms applied to MAX 3-SATISFIABILITY. This research also analyses and compares the effectiveness of two local search algorithms, tabu search and random restart local search, on MAX 3-SATISFIABILITY. Computational results with tabu search and random restart local search on randomly generated instances of 3-SATISFIABILITY are reported. These results suggest that, given a limited computing budget, tabu search offers an effective alternative to random restart local search. On the other hand, these two algorithms yield similar results in terms of the best solution found. The computational results also suggest that for randomly generated instances of 3-SATISFIABILITY (of the same size), the globally optimal solution objective function values are typically concentrated over a narrow range.en
dc.description.degreePh. D.en
dc.identifier.otheretd-07042001-165926en
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-07042001-165926/en
dc.identifier.urihttp://hdl.handle.net/10919/28202en
dc.publisherVirginia Techen
dc.relation.haspartTA-Dissertation.pdfen
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject3-Satisfiabilityen
dc.subjectSatisfiabilityen
dc.subjectProbabilistic Analysis of Max 3-Satisfiabilityen
dc.subjectTabu Searchen
dc.subjectThreshold Conjectureen
dc.subjectMax 3-Satisfiabilityen
dc.titleA Probabilistic Study of 3-SATISFIABILITYen
dc.typeDissertationen
thesis.degree.disciplineIndustrial and Systems Engineeringen
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen
thesis.degree.leveldoctoralen
thesis.degree.namePh. D.en

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
TA-Dissertation.pdf
Size:
1019.37 KB
Format:
Adobe Portable Document Format
Download

Collections

Doctoral Dissertations