{"id":{"repo_id":"mit","oai_identifier":"oai:dspace.mit.edu:1721.1/32466"},"canonical_url":"https://search.dev.ndltd.org/etd/mit/oai:dspace.mit.edu:1721.1/32466","repository":{"repo_id":"mit","name":"MIT","base_url":"https://dspace.mit.edu/oai/request"},"display":{"title":"Generalized conflict learning for hybrid discrete/linear optimization","abstract":"Conflict-directed search algorithms have formed the core of practical, model-based reasoning systems for the last three decades. In many of these applications there is a series of discrete constraint optimization problems and a conflict-directed search algorithm, which uses conflicts in the forward search step to focus search away from known infeasibilities and towards the optimal solution. In the arena of model-based autonomy, discrete systems, like deep space probes, have given way to more agile systems, such as coordinated vehicle control, which must robustly control their continuous dynamics. Controlling these systems requires optimizing over continuous, as well as discrete variables, using linear and non-linear as well as logical constraints. This paper explores the development of algorithms for solving hybrid discrete/linear optimization problems that use conflicts in the forward search direction, generalizing from the conflict-directed search algorithms of model-based reasoning. We introduce a novel algorithm called Generalized Conflict-directed Branch and Bound (GCD-BB). GCD-BB extends traditional Branch and Bound (B&B), by first constructing conflicts from nodes of the search tree that are found to be infeasible or sub-optimal, and then by using these conflicts to guide the forward search away from known infeasible and sub-optimal states. We evaluate GCD-BB empirically on a range of test problems of coordinated air vehicle control. GCD-BB demonstrates a substantial improvement in performance compared to a traditional B&B algorithm, applied to either disjunctive linear programs or an equivalent binary integer program encoding.","abstract_html":"Conflict-directed search algorithms have formed the core of practical, model-based reasoning systems for the last three decades. In many of these applications there is a series of discrete constraint optimization problems and a conflict-directed search algorithm, which uses conflicts in the forward search step to focus search away from known infeasibilities and towards the optimal solution. In the arena of model-based autonomy, discrete systems, like deep space probes, have given way to more agile systems, such as coordinated vehicle control, which must robustly control their continuous dynamics. Controlling these systems requires optimizing over continuous, as well as discrete variables, using linear and non-linear as well as logical constraints. This paper explores the development of algorithms for solving hybrid discrete/linear optimization problems that use conflicts in the forward search direction, generalizing from the conflict-directed search algorithms of model-based reasoning. We introduce a novel algorithm called Generalized Conflict-directed Branch and Bound (GCD-BB). GCD-BB extends traditional Branch and Bound (B&B), by first constructing conflicts from nodes of the search tree that are found to be infeasible or sub-optimal, and then by using these conflicts to guide the forward search away from known infeasible and sub-optimal states. We evaluate GCD-BB empirically on a range of test problems of coordinated air vehicle control. GCD-BB demonstrates a substantial improvement in performance compared to a traditional B&B algorithm, applied to either disjunctive linear programs or an equivalent binary integer program encoding.","abstract_has_math":false,"creators":["Li, Hui (Hui Xylo)"],"institution":"Massachusetts Institute of Technology","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":"Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics.","school":null,"contributors":[],"advisors":["Brian C. Williams."],"committee_chairs":[],"committee_members":[],"year":2005,"date_issued":"2005","date_published":"2005","updated_at":"2026-07-22T22:21:03Z","subjects":["Aeronautics and Astronautics."],"languages":["eng"],"rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"rights_urls":["http://dspace.mit.edu/handle/1721.1/7582"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/1721.1/32466","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Brian C. Williams."]},{"key":"dc:contributor.department","label":"Department","values":["Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics."]},{"key":"dc:creator","label":"Author","values":["Li, Hui (Hui Xylo)"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2006-03-29T18:47:01Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2006-03-29T18:47:01Z"]},{"key":"dc:date.issued","label":"Date","values":["2005"]},{"key":"dc:publisher","label":"Institution","values":["Massachusetts Institute of Technology"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Aeronautics and Astronautics."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://dspace.mit.edu/handle/1721.1/7582"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/1721.1/32466"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2005.","Includes bibliographical references (p. 73-76)."]},{"key":"dc:description.abstract","label":"Abstract","values":["Conflict-directed search algorithms have formed the core of practical, model-based reasoning systems for the last three decades. In many of these applications there is a series of discrete constraint optimization problems and a conflict-directed search algorithm, which uses conflicts in the forward search step to focus search away from known infeasibilities and towards the optimal solution. In the arena of model-based autonomy, discrete systems, like deep space probes, have given way to more agile systems, such as coordinated vehicle control, which must robustly control their continuous dynamics. Controlling these systems requires optimizing over continuous, as well as discrete variables, using linear and non-linear as well as logical constraints. This paper explores the development of algorithms for solving hybrid discrete/linear optimization problems that use conflicts in the forward search direction, generalizing from the conflict-directed search algorithms of model-based reasoning. We introduce a novel algorithm called Generalized Conflict-directed Branch and Bound (GCD-BB). GCD-BB extends traditional Branch and Bound (B&B), by first constructing conflicts from nodes of the search tree that are found to be infeasible or sub-optimal, and then by using these conflicts to guide the forward search away from known infeasible and sub-optimal states. We evaluate GCD-BB empirically on a range of test problems of coordinated air vehicle control. GCD-BB demonstrates a substantial improvement in performance compared to a traditional B&B algorithm, applied to either disjunctive linear programs or an equivalent binary integer program encoding."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["S.M."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Generalized conflict learning for hybrid discrete/linear optimization"]}]}],"canonical_facts":{"dc:contributor.advisor":["Brian C. Williams."],"dc:contributor.department":["Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics."],"dc:contributor.other":["Massachusetts Institute of Technology. Dept. of Aeronautics and Astronautics."],"dc:creator":["Li, Hui (Hui Xylo)"],"dc:date.accessioned":["2006-03-29T18:47:01Z"],"dc:date.available":["2006-03-29T18:47:01Z"],"dc:date.issued":["2005"],"dc:description":["Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics, 2005.","Includes bibliographical references (p. 73-76)."],"dc:description.abstract":["Conflict-directed search algorithms have formed the core of practical, model-based reasoning systems for the last three decades. In many of these applications there is a series of discrete constraint optimization problems and a conflict-directed search algorithm, which uses conflicts in the forward search step to focus search away from known infeasibilities and towards the optimal solution. In the arena of model-based autonomy, discrete systems, like deep space probes, have given way to more agile systems, such as coordinated vehicle control, which must robustly control their continuous dynamics. Controlling these systems requires optimizing over continuous, as well as discrete variables, using linear and non-linear as well as logical constraints. This paper explores the development of algorithms for solving hybrid discrete/linear optimization problems that use conflicts in the forward search direction, generalizing from the conflict-directed search algorithms of model-based reasoning. We introduce a novel algorithm called Generalized Conflict-directed Branch and Bound (GCD-BB). GCD-BB extends traditional Branch and Bound (B&B), by first constructing conflicts from nodes of the search tree that are found to be infeasible or sub-optimal, and then by using these conflicts to guide the forward search away from known infeasible and sub-optimal states. We evaluate GCD-BB empirically on a range of test problems of coordinated air vehicle control. GCD-BB demonstrates a substantial improvement in performance compared to a traditional B&B algorithm, applied to either disjunctive linear programs or an equivalent binary integer program encoding."],"dc:description.degree":["S.M."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/1721.1/32466"],"dc:language.iso":["eng"],"dc:publisher":["Massachusetts Institute of Technology"],"dc:rights":["M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission."],"dc:rights.uri":["http://dspace.mit.edu/handle/1721.1/7582"],"dc:subject":["Aeronautics and Astronautics."],"dc:title":["Generalized conflict learning for hybrid discrete/linear optimization"],"dc:type":["Thesis"]},"updated_at":"2026-07-22T22:21:03Z"}