Show simple item record

dc.contributor.authorAytemiz, Tevfiken_US
dc.date.accessioned2014-03-14T20:13:43Z
dc.date.available2014-03-14T20:13:43Z
dc.date.issued2001-06-28en_US
dc.identifier.otheretd-07042001-165926en_US
dc.identifier.urihttp://hdl.handle.net/10919/28202
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_US
dc.publisherVirginia Techen_US
dc.relation.haspartTA-Dissertation.pdfen_US
dc.rightsI hereby certify that, if appropriate, I have obtained and attached hereto a written permission statement from the owner(s) of each third party copyrighted matter to be included in my thesis, dissertation, or project report, allowing distribution as specified below. I certify that the version I submitted is the same as that approved by my advisory committee. I hereby grant to Virginia Tech or its agents the non-exclusive license to archive and make accessible, under the conditions specified below, my thesis, dissertation, or project report in whole or in part in all forms of media, now or hereafter known. I retain all other ownership rights to the copyright of the thesis, dissertation or project report. I also retain the right to use in future works (such as articles or books) all or part of this thesis, dissertation, or project report.en_US
dc.subject3-Satisfiabilityen_US
dc.subjectSatisfiabilityen_US
dc.subjectProbabilistic Analysis of Max 3-Satisfiabilityen_US
dc.subjectTabu Searchen_US
dc.subjectThreshold Conjectureen_US
dc.subjectMax 3-Satisfiabilityen_US
dc.titleA Probabilistic Study of 3-SATISFIABILITYen_US
dc.typeDissertationen_US
dc.contributor.departmentIndustrial and Systems Engineeringen_US
dc.description.degreePh. D.en_US
thesis.degree.namePh. D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.grantorVirginia Polytechnic Institute and State Universityen_US
thesis.degree.disciplineIndustrial and Systems Engineeringen_US
dc.contributor.committeememberYe, Keyingen_US
dc.contributor.committeememberMeller, Russell D.en_US
dc.contributor.committeememberBish, Ebru K.en_US
dc.identifier.sourceurlhttp://scholar.lib.vt.edu/theses/available/etd-07042001-165926/en_US
dc.contributor.committeecochairJacobson, Sheldon H.en_US
dc.contributor.committeecochairKoelling, Charles Patricken_US
dc.date.sdate2001-07-04en_US
dc.date.rdate2002-07-06
dc.date.adate2001-07-06en_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record