Emerald Login
   

Welcome guest

Article Request:
Concurrent processing of mixed-integer non-linear programming problems

Article Information:

Title:

Concurrent processing of mixed-integer non-linear programming problems

Author(s):

Ralf Ostermark

Journal:

Kybernetes

Year:

2009

Volume:

38

Issue:

6

Page:

966 - 989


ISSN:

0368-492X


DOI:

10.1108/03684920910973180

Publisher:

Emerald Group Publishing Limited


Acknowledgements:

The author thanks the experts at the CSC in Helsinki for their guidance and is particularly indebted to MSc (tech) Raimo Uusvuori at CSC for his invaluable and untiring advice and support in code optimization over a period of almost two decades. Also thanked are Juha Haataja for his early comments on mathematical programming and Jussi Heikonen for his expertise in computer programming issues. All this support has been crucial to realizing the current long-term project, often involving desperate error search in dead lock situations or core dump problems through the night.

Document Access:

Existing customers:

Please login above.

Purchase this document:
Price payable: GBP £13.00
plus handling charge of GBP £1.50 and VAT where applicable.
Purchase

Request this document:
Print or e-mail a document request to your librarian.
Request

Reprints & permissions:
Image: Rightslink Request

Abstract:

Purpose – To discuss a new parallel algorithmic platform (minlp_machine) for complex mixed-integer non-linear programming (MINLP) problems.

Design/methodology/approach – The platform combines features from classical non-linear optimization methodology with novel innovations in computational techniques. The system constructs discrete search zones around noninteger discrete-valued variables at local solutions, which simplifies the local optimization problems and reduces the search process significantly. In complicated problems fast feasibility restoration may be achieved through concentrated Hessians. The system is programmed in strict ANSI C and can be run either stand alone or as a support library for other programs. File I/O is designed to recognize possible usage in both single and parallel processor environments. The system has been tested on Alpha, Sun and Linux mainframes and parallel IBM and Cray XT4 supercomputer environments. The constrained problem can, for example, be solved through a sequence of first order Taylor approximations of the non-linear constraints and feasibility restoration utilizing Hessian information of the Lagrangian of the MINLP problem, or by invoking a nonlinear solver like SQP directly in the branch and bound tree. minlp_machine( ) has been tested as a support library to genetic hybrid algorithm (GHA). The GHA(minlp_machine) platform can be used to accelerate the performance of any linear or non-linear node solver. The paper introduces a novel multicomputer partitioning of the discrete search space of genuine MINLP-problems.

Findings – The system is successfully tested on a small sample of representative MINLP problems. The paper demonstrates that – through concurrent nonlinear branch and bound search – minlp_machine( ) outperforms some recent competing approaches with respect to the number of nodes in the branch and bound tree. Through parallel processing, the computational complexity of the local optimization problems is reduced considerably, an important aspect for practical applications.

Originality/value – This paper shows that binary-valued MINLP-problems will reduce to a vector of ordinary non-linear programming on a suitably sized mesh. Correspondingly, INLP- and ILP-problems will require no quasi-Newton steps or simplex iterations on a compatible mesh.

Keywords:

Cybernetics, Gradient methods, Optimization techniques, Parallel programming


Article Type:

Research paper


Article URL:

http://www.emeraldinsight.com/10.1108/03684920910973180

Top