Research Topic

Mixed Integer Nonlinear Programming

Mixed Integer Nonlinear Programming (MINLP) generalizes classical Mixed Integer Programming (MIP) by allowing nonlinearities in the objective function and constraints. The aim of the project is to integrate a nonlinear nearly active set SQP algorithm into SCIP as a drop-in replacement for the simplex algorithm. The main advantage of those algorithms over classical Interior Point methods are the fast resolve capabilities. Further they do not require local convexity of the problem which is important for the use in MINLP heuristics during the Branch & Bound Process. Classical primal-dual implementations of active set SQP algorithms like SNOPT fail to handle problems with high degrees of freedom which is crucial in global optimization.

Further developments concentrate on the handling of nonconvex restrictions due to underestimation and DC-Programming. The central idea is to keep the power of SCIP as a well engineerd MIP solver and combine it with a reliable NLP solver and techniques from global optimization.

Overview of the Components

NLP Solver

  • Sparse Nearly Active Set SQP-Solver based on DONLP2
  • Modifications
    • Sparse Rank Revealing QR Decomposition for the Jacobian
    • Use of Hessian Matrices instead of Pantya-Main-BFGS Updates

The Solver Interface

The solver Interface was defined together with Matheon Project B20 to cope with different NLP-Solvers

NLP Data Structures

Common data structures which can be used in outer approximation as well as in Nonlinear Branch & Cut including data structures are developed together with Matheon B19/B20 supporting symbolic expressions and NLP-Management within SCIP.

Nonlinear Branch & Cut

  • A relaxator for SCIP based on the NLP-Solver replacing the Linear Programming Solver.
  • Branching Rules for nonlinear programms.

Underestimation and Disciplined Convex Programming

  • Rigorous Underestimation (currently alpha-Underestimator)
  • Constraint specific underestimation (see Cooperations)

Global Function Evaluation

  • Evaluation and Automatic Differentiation using Stack Machines
  • Interval Methods to determine global parameters
    • convexity,
    • smoothness,
    • interval gradients,
    • interval hessians.

Corporations

  • Matheon B19/B20, Ambros Gleixner, Thorsten Koch (ZIB), Stefan Viegerske (HU Berlin). Development of an Outer Approximation Project. Contribution of Heuristics and Bound Reductions from their solver to our solver is planned.
  • Marc Pfetsch, TU Braunschweig, SCIP Plugins for Nonlinear Constraints (LP-based).
  • Peter Spellucci, TU Darmstadt
  • Robert Bixby, Rice University
  • Robert Weismantel, Uni Magdeburg

Financial Support

Siemens AG (CT ME 10)

Contact

Thorsten Gellermann (gellermann [ a t ] opt [ d o t ] tu-darmstadt [ d o t ] de)

Key Research Area

Optimization

Supervisors

Alexander Martin

Contact

Thorsten Gellermann
Dipl.-Inform.

Address:

Dolivostraße 15

D-64293 Darmstadt

Germany

Phone:

+49 6151 16 - 24401 or 24402

Fax:

+49 6151 16 - 24404

Office:

S4|10-312

Email:

duly (at) gsc.tu...

 Print |  Impressum |  Sitemap |  Search |  Contact |  Privacy Policy
zum Seitenanfangzum Seitenanfang