# Presentation: 333217

## Discovering the Characteristics of Mathematical Programs

- John W. Chinneck
- Systems and Computer Eng.
- Carleton University
- Ottawa, Canada

## Motivation

- Complex models, large scale:
- Unexpected results, bad performance, solver failure...
- Limited information returned by (e.g. NLP) solvers:
- Feasible, KKT conditions satisfied
- No improvement in many iterations: stopping.
- Unable to find feasible point.
- Too many iterations.
- Various specific failure messages...
- Questions:
- Why do I have this problem?
- How do I make the solver run better on this model?
**Needed:** tools to discover the characteristics of models

- Discovering Characteristics of Math Programs

## Model Characteristics

**Some characteristics** (e.g. for NLPs):
- Shapes of the constraints and objective (convex, concave, both, almost linear, etc.)
- Shape of the feasible region (convex, non-convex)
- Redundancy of constraints
- Location of feasible region
**Insights gained**:
- Better understanding of outcomes and behaviour
- Functions that can be approximated (e.g. linear)
- Constraints that can be ignored
- Best type of solution algorithm to apply
- Good starting point

- Discovering Characteristics of Math Programs

## Outline

**Theory**
- Sampling for Characteristic Discovery
- What you can discover
- Tightening Sampling Box for Better Accuracy
- Sampling in Convex Envelopes
- Hit and run methods
- Approximating the analytic centre
- Point-Oriented Analysis
**Practice**
- MProbe software

- Discovering Characteristics of Math Programs

## Box Sampling

- Random line segments within variable bounds:
- Uniform distrn for endpoint 1
- Uniform distrn for endpoint 2
- Interior points at fixed positions on line segment (e.g. 3 equally spaced)
- Default settings:
- 500 line segments
- 3 interior points per line segment
- Info from pts, info from lines

- Discovering Characteristics of Math Programs

## Empirical Function Shape

**Empirical Shape**: based on sampled *differences* between actual and interpolated function values
- Depends on *where* you sample
- E.g. algebraically nonlinear function may be linear in region of interest

- Discovering Characteristics of Math Programs

## Tolerances

- Difference:** **interpolated – actual value
**Equality tolerance**: if difference less than *tol**equality* then interpolated=actual at that point
**Almost tolerance**: if difference is less than *tol**almost* then interpolated *almost* equals actual at that point
- E.g.: *tol**equality*=0.00001, *tol**almost*=0.001
*Almost* identifies candidates for approximation

- Discovering Characteristics of Math Programs

## Shape Histogram

- Discovering Characteristics of Math Programs

## Function Shape Assessment

**linear**: all diffs within tolequality
**convex**: all diffs are above -tolequality and at least one above +tolalmost.
**convex, almost linear**: all diffs are above -tolequality, at least one is between +tolequality and +tolalmost, and none are above +tolalmost.
**almost convex**: at least one diff is between the -tolalmost and -tolequality, and at least one diff is above +tolalmost
**concave**: all diffs are below +tolequality, and at least one is below -tolalmost
**concave, almost linear**: all diffs are below +tolequality, at least one is between -tolequality and -tolalmost, and none are below -tolalmost.
**almost concave**: at least one diff is between +tolalmost and +tolequality, and at least one diff is below -tolalmost.
**convex and concave**: at least one diff is above +tolalmost, and at least one diff is below -tolalmost.
**convex and concave, almost linear**: at least one diff is between +tolequality and the +tolalmost, and at least one diff is between -tolequality and -tolalmost.

- Discovering Characteristics of Math Programs

## Summary of Constraint Shape Assessments

- Discovering Characteristics of Math Programs

## (Un)certainty of Empirical Assessments

*Linear* report: confidence increases with testing
*Almost linear* reports: confidence increases with testing:
- Convex, almost linear
- Concave, almost linear
- Convex and concave, almost linear
*Nonlinearity* is certain if report is:
- Convex
- Concave
- Convex and concave
- xxx, almost linear
*Convex and concave* is certain if report is:
- almost convex
- almost concave
- convex and concave

- Discovering Characteristics of Math Programs

## Constraint Effectiveness

*Inequalities*: what fraction of the sampling enclosure is eliminated?
*Equalities*: fractions of sample points above, below, on the function?

- Discovering Characteristics of Math Programs

## Simple Feasibility & Redundancy

- Simple constraint redundancy (0% effective)
- Simple feasibility test (100% effective)

- Discovering Characteristics of Math Programs

## Function “slope”

- |f(a) – f(b)| / (length a to b)
- Multidimensional idea of “steepness”
- Collect in histogram
- Especially useful for objective functions

- Discovering Characteristics of Math Programs

## Objective Optimum Effects

- Objective sense and shape interact:
- global optimum possible by descent methods
- Local optimum likely

- Discovering Characteristics of Math Programs

## Constraint Region Effect

- Effect on shape of constrained region
*Inequalities*: sense interacts with shape
*Equalities*:
- Linear: convex region effect
- Others: nonconvex region effect

- Discovering Characteristics of Math Programs

## Shape of Constrained Region

- Assessing shape of the constrained region:
- All constraints have convex region effect: *feasible region is convex* (if it exists)
- Else *constrained region is nonconvex*
***Note***: constraints sampled individually, results compiled

- Discovering Characteristics of Math Programs

## Other Info from Sampling

- Function value statistics
- histogram, max, min, etc.
- Objective function best sampled value and point (not nec. feasible)
- variables min and max sampled values
- Line segment length
- effect on conclusions

- Discovering Characteristics of Math Programs

## Tightening Sampling Box for Improved Accuracy

- Sampling box should be a close outer approximation of the feasible region

- Feasible region

- Sampling box

- Discovering Characteristics of Math Programs

## Tightening Bounds

**Methods:**
- Manual adjustment
- Linear interval analysis
- Nonlinear interval sampling
- Get a nucleus box
- Range cutting
- Constraint Consensus bound tightening
- Max/min sampled values from convex enclosure *(explanation deferred)*

- Discovering Characteristics of Math Programs

## Linear Interval Analysis

- Applies to the subset of linear constraints
- Like standard presolve: bound changes percolate
- E.g.:
- constraint 2*x*1  5*x*2  10 when -10  *x*1,*x*2  10
- Tighten *x*2 lower bound by applying the constraint when *x*1 is at it’s lower bound: 2(-10)  5*x*2  10  *x*2  -6.
- Conclusion: true bounds are -6  *x*2  10.

- Discovering Characteristics of Math Programs

## Nonlinear Interval Sampling

- inequality          		b) equality
- Apply to each constraint in turn
- overtightens
- non-overlap?  return the gap itself

- Discovering Characteristics of Math Programs

## Get a Nucleus

- For unbounded variables
- Look at constraints involving the variable that were never satisfied during interval sampling
- try gradually larger boxes centred at origin.  Stop when next box shows no feasible points

- Discovering Characteristics of Math Programs

## Nonlinear Range Cutting

- Accept cut if at least one constraint never satisfied when sampling in the zone
*equalities*: “satisfied” if find one pt  rhs and one pt  rhs

- Discovering Characteristics of Math Programs

## Constraint Consensus Heuristic

- Quickly achieves approximate feasibility
- For each violated constraint: estimate vector to achieve feasibility
- Consensus vector: Component-wise average of feasibility vectors
- Update point using consensus vector
- Repeat until close to feasible

- Feasible region

- Discovering Characteristics of Math Programs

## Constraint Consensus bound tightening

- Apply CC method from numerous random initial points in current sampling box
- Shrink bounds to encompass cloud of final points

- Initial point

- Final point

- Discovering Characteristics of Math Programs

## Sampling in Convex Enclosures

*How do you find a *_*convex*_* region that encloses the feasible region?*
- Procedure:
- analyze constraint region effects by box sampling
- select _inequalities_ that have convex region effects and all variable bounds
- Sample via hit-and-run methods

- Discovering Characteristics of Math Programs

## Hit-and-Run Sampling

- hit constraints are *necessary; *unhit constraints are *redundant *(relative to enclosure)
- estimate fraction of enclosure surface area
- non-enclosure constraints sampled as usual (shape, effectiveness, etc.)

- Discovering Characteristics of Math Programs

## Finding an Initial Feasible Point

- Need an initial feasible point to start hit-and-run
*Method 1:*
- Sample randomly until at least one constraint satisfied
- Thereafter use hit-and-run to _keep_ constraints satisfied
- Stop when all constraints satisfied.
***Note:*** bias hit-and-run sampling rays according to variable bounds (long thin boxes are a problem)
*Method 2:*
- Apply constraint consensus method

- Discovering Characteristics of Math Programs

## The Analytic Centre

**Analytic centre**: ***P*** is point that maximizes *W*=***[ln(distance to constraint)* over all constraints.
- Best place to launch rays for estimating surface frac.
**Heuristic for finding analytic centre:**
- Initial feasible pt is first estimate of*** P***.  *W* always calculated over necessary constraints found _so far_.
- Launch hitting rays from*** P***.
- Get new hit-and-run launch point ***x***.
- If *W*(***x***)*>W(****P****) *then ***P***=***x***.
**Advantages:**
- Pushes ***P*** away from discovered necessary constraints towards undiscovered necessary constraints
- Quick convergence to analytic centre.

- Discovering Characteristics of Math Programs

## “replace current bounds with max/min sampled values”

- After convex enclosure sampling: tighten bounds
- Use hit points to (over)tighten the variable bounds

- sampling enclosure

- Discovering Characteristics of Math Programs

## Point-Oriented Analysis

- Finding (near) feasible points
*What is a good starting point?*
- Finding (near) optimal points
- Analyzing features of points
*Why did my solver stop here?*

- Discovering Characteristics of Math Programs

## Finding (Near) Feasible and Optimum Points

***Finding a near-feasible point***:
- constraint consensus method
***Finding a near-optimal point***:
- keep track of feasibility status and objective function value of all sampled points.
- Note *best found point* and *best found feasible point*

- Discovering Characteristics of Math Programs

## Analyzing Point Features

- Create a small box around a point:
- E.g. shrink bounds to 1% of each current edge dimension, centred around point
- Look at objective “flatness” in the box
- Histogram of objective “slope” in the box.

- Flat (1-D)

- Discovering Characteristics of Math Programs

## MProbe

- Software tool embodying these and other analytic methods
- Reads AMPL, GAMS, MPS files
- Essential part of an *integrated development environment* for math programming

- Discovering Characteristics of Math Programs

## MProbe Workshops

**Variables Workshop**
- Shift, tighten variable bounds
**Constraints and Objectives Workshops**
- Analyze shape, effectiveness, redundancy, set up convex enclosures for tighter sampling
**Constrained Region Workshop**
- Analyze shape of feasible region
**Points Workshop**
- Exchange points with solvers, look for near-feasible points, etc.

- Discovering Characteristics of Math Programs

## Additional Features

- Model statistics
- “Snapping” of integer/binary variables
- Spreadsheet-like displays of constraints, objectives, variables
- View subsets by category (e.g. only nonlinear constraints, only binary variables)
- Sort on any column
- Navigate (e.g. see all constraints that contain variable *x*)
- User adjustment of tolerances, histogram cells
- Text file trace of session
- Help system

- Discovering Characteristics of Math Programs

## Constraints Workshop

- Discovering Characteristics of Math Programs

## Visualizing Shape: Function Profile

- 2 dimensional plot between 2 endpoints in n-space
- End-points selectable and configurable in multiple ways

- Discovering Characteristics of Math Programs

## Constrained Region Workshop

- Discovering Characteristics of Math Programs

## Points Workshop

- Discovering Characteristics of Math Programs

## Conclusions

- Model probing and analysis tools a vital part of IDE for math programming
- Shape analysis tools are heuristic and based on random sampling
- Tools don’t *always* work, but *often* do.
- Can be slow for very large or very complex models
- Performance depends on characteristics of the model
- Download: _[www.sce.carleton.ca/faculty/_x000b_chinneck/mprobe.html](http://www.sce.carleton.ca/faculty/%0Bchinneck/mprobe.html)_

- Discovering Characteristics of Math Programs

## Research Directions

- Better Sampling
- Interior pts on line segments means more samples towards centre of sampling box
- Better bound tightening
- Better interaction among the component methods
- Determining best approximations of functions (e.g. best piecewise linear approximation)
- Connection to computer algebra system (Matlab?)
- Tool for identifying implied equalities
- Etc..........

- Discovering Characteristics of Math Programs

## References

- Chinneck, J.W. (2003), “The Constraint Consensus Method for Finding Approximately Feasible Points in Nonlinear Programs”, *INFORMS Journal on Computing*, to appear.
- Chinneck, J.W. (2002), “Discovering the Characteristics of Mathematical Programs via Sampling”, *Optimization Methods and Software,* vol. 17, no. 2, pp. 319-352.
- Chinneck, J.W. (2001), “Analyzing Mathematical Programs using MProbe”, *Annals of Operations Research*, vol. 104, pp. 33-48.

- Discovering Characteristics of Math Programs