Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models

Yuji Nakagawa (), Ross J. W. James (), César Rego () and Chanaka Edirisinghe ()
Additional contact information
Yuji Nakagawa: Faculty of Informatics, Kansai University, Ryozenjicho, Takatsuki-shi 569, Japan
Ross J. W. James: Department of Management, University of Canterbury, Christchurch 8140, New Zealand
César Rego: School of Business Administration, University of Mississippi, University, Mississippi 38677
Chanaka Edirisinghe: College of Business Administration, University of Tennessee, Knoxville, Tennessee 37996

Management Science, 2014, vol. 60, issue 3, 695-707

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. This paper was accepted by Dimitris Bertsimas, optimization.

Keywords: multidimensional nonlinear knapsack; separable discrete optimization; combinatorial optimization; surrogate constraints; problem difficulty estimation; entropy (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.2013.1772 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:60:y:2014:i:3:p:695-707

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().