University of Canterbury Home
    • Admin
    UC Research Repository
    UC Library
    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    1. UC Home
    2. Library
    3. UC Research Repository
    4. UC Business School | Te Kura Umanga
    5. Business: Journal Articles
    6. View Item
    1. UC Home
    2.  > 
    3. Library
    4.  > 
    5. UC Research Repository
    6.  > 
    7. UC Business School | Te Kura Umanga
    8.  > 
    9. Business: Journal Articles
    10.  > 
    11. View Item

    Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models (2014)

    Thumbnail
    View/Open
    12652220_ManagementScience2014.pdf (303.5Kb)
    Type of Content
    Journal Article
    UC Permalink
    http://hdl.handle.net/10092/10009
    
    Publisher's DOI/URI
    https://doi.org/10.1287/mnsc.2013.1772
    
    Publisher
    University of Canterbury. Management, Marketing, and Entrepreneurship
    ISSN
    0025-190
    Collections
    • Business: Journal Articles [311]
    Authors
    Nakagawa, Y.
    James, R.J.W.
    Rego, C.
    Edirisinghe, C.
    show all
    Abstract

    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.

    Citation
    Nakagawa, Y., James, R.J.W., Rego, C., Edirisinghe, C. (2014) Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models. Management Science, 30(3), pp. 695-707.
    This citation is automatically generated and may be unreliable. Use as a guide only.
    Keywords
    multidimensional nonlinear knapsack; separable discrete optimization; combinatorial optimization; surrogate constraints; problem difficulty estimation; entropy
    ANZSRC Fields of Research
    35 - Commerce, management, tourism and services::3507 - Strategy, management and organisational behaviour::350709 - Organisation and management theory
    49 - Mathematical sciences::4903 - Numerical and computational mathematics::490304 - Optimisation
    08 - Information and Computing Sciences::0802 - Computation Theory and Mathematics::080201 - Analysis of Algorithms and Complexity
    Rights
    https://hdl.handle.net/10092/17651

    Related items

    Showing items related by title, author, creator and subject.

    • Grover's quantum algorithm applied to global optimisation 

      Baritompa, W. P.; Bulger, D. W.; Wood, G. R. (University of Canterbury. Dept. of Mathematics and Statistics, 2004)
      Grover's quantum computational search procedure can provide the basis for implementing adaptive global optimisation algorithms. A brief overview of the procedure is given and a framework called Grover Adaptive Search is ...
    • The CARToptimizer package version 1.0 user's guide 

      Robertson, B.L.; Price, C. J.; Reale, M. (University of Canterbury. Dept. of Mathematics and Statistics, 2012)
      The CARToptimizer package is a suite of MATLAB functions for solving numerical optimization problems. The suite has algorithms for local, global and constrained optimization problems, where the objective function can be ...
    • Efficient Coding of the Danzig-Wolfe Decomposition (Linear Programming) Algorithm 

      Oo, C. H. (University of Canterbury. Computer Science, 1978)
      The Dantzig-Wolfe decomposition (linear programming) principle published in 1960 involves the solving of large-scale mathematical programming problems of particular structure. Large practical problems of this type typically ...
    Advanced Search

    Browse

    All of the RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThesis DisciplineThis CollectionBy Issue DateAuthorsTitlesSubjectsThesis Discipline

    Statistics

    View Usage Statistics
    • SUBMISSIONS
    • Research Outputs
    • UC Theses
    • CONTACTS
    • Send Feedback
    • +64 3 369 3853
    • ucresearchrepository@canterbury.ac.nz
    • ABOUT
    • UC Research Repository Guide
    • Copyright and Disclaimer
    • SUBMISSIONS
    • Research Outputs
    • UC Theses
    • CONTACTS
    • Send Feedback
    • +64 3 369 3853
    • ucresearchrepository@canterbury.ac.nz
    • ABOUT
    • UC Research Repository Guide
    • Copyright and Disclaimer