Practical Solution Approaches to Optimization and Engineering:
Case Studies in Mine Planning and Electrical Power
Daniel Bienstock, Columbia U. and Gurobi
RMIC, November 2022

Practical Optimization at a Crossroads•

Current and past areas of interest: logistics, transportation, supply chain•

These areas will remain relevant, but …

•

The future: heavy engineering and hard science•

Very complex models that embody hard, inflexible rules•

Very large scale, high level of modeling detail, myriad details in complex systems•

Demanding performance requirements: must get good solutions fast•

Are our algorithms up to the task?

The open pit mining production scheduling problem

••
•
•

Material to be removed in “blocks” – a lot of them.
Each block has known physical properties.
The blocks must be removed following a carefully planned order dictated by structural stability.
Before a block can be extracted, blocks ”above it” must have been extracted first.

Taking a step back …

Precedence, nonnegativity
Structured
General/messy, badLagrangian relaxation/column generation?

Idea used in multicommodity flows (~2002)•••••

Subgradient optimization can tail-off or diverge badly.
Why?
The solution to the Lagrangian is very bad.
What to do?
Force structure of the Lagrangian solution into a “restricted primal”.

• Column generation on roids.

Theorem:
At termination we have solved the LP.

Many extensions/developments!
•Underground mining.

•Cutoff grades.
Cutoff grade is the minimum ratio of ore to rock in a block to be extracted.
Low cutoff = longer operation for the mine, but more processing
High cutoff = extraction focuses on more valuable blocks, but lifetime of mine may be too short
Heuristics can be used to decompose a mine into a set of separate operations (using different cutoffs)(Newman et al)•Commercialization.

NY system:1814 buses
500+ generators

complex power injected into km at k

LHS = complex power injected into grid at k

Real power demand at k
Total real power generated at k

But there is an equivalent formulation as aQCQP(Quadratically Constrained Quadratic Program)

Admittance matrix for line km

Use rectangular coordinates for voltages

• QCQPs are hard!
••

Numerically challenging.

•It is difficult to certify nearness to feasibility of a nearly feasible solution.

•

It is difficult to certify infeasibility of a model.

•

How do we explain infeasibility of a model? IISs, anyone?

•

Real-world cases can be at the boundary of infeasibility.

•

Nonlinear != linear• McCormick relaxation - an important workhorse

Convex hull provided by under/over estimators

Works well in tandem with spatial branching(source: Wikipedia)• Issues with McCormick relaxation and spatial b&b?
•

On hard instances, e.g., hard and large ACOPF, bounds can be very weak and we will grow animmense tree•

Numerical issues! SOC and rotated cone constraints approximated with many outer envelopecuts•

Numerical issues! Nodes can be very iffy, in particular:Infeasibility fathoming! Mr. Solver, are you sure that node is infeasible?

•And what does infeasibility actually mean, in light of our prior slides?

•Upper bounds: Mr. Solver, are you sure that solution is feasible?

Upper bounds: log-barrier methods•

A must-have tool!

•

Knitro, IPOPT, LOQO, others?

•Knitro and IPOPT are excellent•

Also, very elegant theory!

•But, also, excellent implementations!

•Theory only guarantees convergence to (?) a critical point for the barrier function•

Works extremely well for standard ACOPF•

A (minor?) issue: solutions can exhibit small infeasibilities

And much, much more•
•
•
•
•
•

Contingencies (security-constrained ACOPF)
Penalties for infeasibilities
Migration from existing solution
Tight timeframe available for computation
MPI required: 4 boxes with 16 cores each…

Joint work with Gonzalo Muñoz (2015)
Arbitrarily close approximations of QCQPs using pure-binary integer programs
Approximate continuous variables using binary variables. Why?
Givenset(quantity to approximate) and(the tolerance)

Is this a crazy approach to QCQP?
•We start with a bad, large QCQP and we end up with a much, much larger andprobably badder but linear binary IP•

But it is linear …

•Numerics should be less of an issue …

•And it has a lot of structure …

•This is ongoing work with Matίas Villagra and Yuri Faenza