Entropy-Based Optimization of Nonlinear Separable Discrete Decision Models (2014)
Type of ContentJournal Article
PublisherUniversity of Canterbury. Management, Marketing, and Entrepreneurship
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.
CitationNakagawa, 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.
Keywordsmultidimensional nonlinear knapsack; separable discrete optimization; combinatorial optimization; surrogate constraints; problem difficulty estimation; entropy
ANZSRC Fields of Research35 - 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
Showing items related by title, author, creator and subject.
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 ...
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 ...
Takaoka, Tadao (University of Canterbury. Computer Science and Software Engineering, 1997)We present a new adaptive sorting algorithm, called minimal merge sort, which merges the ascending runs in the input list from shorter to longer, that is, merging the shortest two lists each time. We show that this algorithm ...