• Admin
    UC Research Repository
    View Item 
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Business and Law
    • Business and Law: Journal Articles
    • View Item
       
    • UC Home
    • Library
    • UC Research Repository
    • College of Business and Law
    • Business and Law: Journal Articles
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    Statistics

    View Usage Statistics

    Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models

    Thumbnail
    View/Open
    12652220_ManagementScience2014.pdf (303.5Kb)
    Author
    Nakagawa, Y.
    James, R.J.W.
    Rego, C.
    Edirisinghe, C.
    Date
    2014
    Permanent Link
    http://hdl.handle.net/10092/10009

    This paper develops a new way to help solve difficult linear and nonlinear discrete-optimization decision models more efficiently by introducing a problem-difficulty metric that uses the concept of entropy from information theory. Our entropy metric is employed to devise rules for problem partitioning within an implicit enumeration method, where branching is accomplished based on the subproblem complexity. The only requirement for applying our metric is the availability of (upper) bounds on branching subproblems, which are often computed within most implicit enumeration methods such as branch-and-bound (or cutting-plane-based) methods. Focusing on problems with a relatively small number of constraints, but with a large number of variables, we develop a hybrid partitioning and enumeration solution scheme by combining the entropic approach with the recently developed improved surrogate constraint (ISC) method to produce the new method we call ISCENT. Our computational results indicate that ISCENT can be an order of magnitude more efficient than commercial solvers, such as CPLEX, for convex instances with no more than eight constraints. Furthermore, for nonconvex instances, ISCENT is shown to be significantly more efficient than other standard global solvers.

    Subjects
    multidimensional nonlinear knapsack
     
    separable discrete optimization
     
    combinatorial optimization
     
    surrogate constraints
     
    problem difficulty estimation
     
    entropy
     
    Field of Research::15 - Commerce, Management, Tourism and Services::1503 - Business and Management::150310 - Organisation and Management Theory
     
    Field of Research::01 - Mathematical Sciences::0103 - Numerical and Computational Mathematics::010303 - Optimisation
     
    Field of Research::08 - Information and Computing Sciences::0802 - Computation Theory and Mathematics::080201 - Analysis of Algorithms and Complexity
    Collections
    • Business and Law: Journal Articles [184]
    Rights
    http://library.canterbury.ac.nz/ir/rights.shtml

    UC Research Repository
    University Library
    University of Canterbury
    Private Bag 4800
    Christchurch 8140

    Phone
    364 2987 ext 8718

    Email
    ucresearchrepository@canterbury.ac.nz

    Follow us
    FacebookTwitterYoutube

    © University of Canterbury Library
    Send Feedback | Contact Us