• Login
    View Item 
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    •   Carroll Scholars Home
    • Mathematics, Engineering and Computer Science
    • Mathematics, Engineering and Computer Science Undergraduate Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    There Are 10 Kinds of Problems in the World: Those That Are Binary and Those That Aren’t

    Thumbnail
    View/Open
    2006_GarrickS_THS_000727.pdf (4.168Mb)
    Author
    Garrick, Shane
    Advisor
    Mark Parker; Holly Zullo; Joan Stottlemyer
    Date of Issue
    2006-04-01
    Metadata
    Show full item record
    URI
    https://scholars.carroll.edu/handle/20.500.12647/3447
    Title
    There Are 10 Kinds of Problems in the World: Those That Are Binary and Those That Aren’t
    Type
    thesis
    Abstract
    Binary integer programming is a class of algorithms that are used to solve problems where we have several yes/no decisions, along with some constraints on which decisions we can make and a value associated with each decision. A classic example is the knapsack problem, where we have to choose what to carry in the knapsack. For each possible item, we can carry it or not. We are also limited by space and weight, and some objects will have a higher value than others. This paper examines binary integer programming and a simple computer implementation of a technique for solving such problems, called the Multiphase Dual Algorithm, which was developed by Dr. Fred Glover in 1965. We also test the execution time of this program compared to an implementation of a branch-and-cut algorithm developed by COIN-OR. Results show that this Multiphase Dual program executes in about the same time as the branch-and-cut algorithm on small problems, but starts to become slower on large programs. This indicates that although the Multiphase Dual algorithm may not be the fastest possible algorithm, it can solve binary integer programming problems in a reasonable time. We conclude by discussing other parts of the algorithm whose implementation would increase its efficiency.
    Degree Awarded
    Bachelor's
    Semester
    Spring
    Department
    Mathematics, Engineering & Computer Science
    Collections
    • Mathematics, Engineering and Computer Science Undergraduate Theses

    Browse

    All of Carroll ScholarsCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    DSpace software copyright © 2002-2023  DuraSpace
    DSpace Express is a service operated by 
    Atmire NV