*New Features:*

*Points Workshop*

*Finding
approximately feasible points*

*Ability to read
and manipulate MPS files directly*

*New method for
shrinking variable bounds*

*Better
feasibility bootstrapping*

What is
MProbe?

Summary of Tools in MProbe

What's New in the Latest Release

Take
a Web Tour of MProbe 3.0

Obtaining MProbe (student/demo and Professional
editions)

Change Log

Contact: Feedback and Email List

Other MPROBEs on the Web

Technical Papers

Author's Homepage

MProbe is the missing link in the development environment for mathematical
programs. While conventional programming systems (C++, Java, Fortran, etc.)
have a host of supporting tools to ease the process of writing code (e.g.
debuggers, code profilers), there are no analogous tools to support the
development of mathematical programs in modelling languages such as AMPL, GAMS,
etc. MProbe (*M*athematical *P*rogram *Probe*) provides a suite
of analysis tools for mathematical programs of all types (linear, nonlinear,
integer, logic) with the goal of providing insights into the model. For
example, it can estimate the effectiveness of the constraints, the shape of
nonlinear functions, and the convexity or nonconvexity of the constrained
region; it can shrink the variable bounds; it can provide profile plots of
nonlinear functions; it allows model navigation, etc. See the next section for
an overview of all of the tools.

MProbe is especially strong in the analysis of nonlinear functions to
discern their *shapes* in a region of interest (i.e. whether the function
is linear or almost linear, convex or almost convex, concave or almost concave,
or concave and convex). Knowledge of function shape is crucial when developing
nonlinear optimization models, or when selecting the nonlinear solver for a
nonlinear optimization problem. Determining function shape is difficult for
nonlinear functions having more than two variables, but MProbe is specifically
designed to operate on nonlinear functions having many variables. MProbe also
estimates the shape of a nonlinearly constrained region (convex? nonconvex?),
and the objective function effect (global optimum? local optimum only?). Tightening of variable bounds is also
extremely useful, especially when no bounds are provided initially.

MProbe works with Bell Laboratories AMPL,
a language for expressing and manipulating optimization models, and can read
and write MPS files. A student/demo version of AMPL is included on the MProbe
installation disks, so you will be able to begin using both AMPL and MProbe
right away. More information on AMPL is available via the link above, or in the
following book: Robert Fourer, David M. Gay, Brian W. Kernighan: *AMPL: A
Modeling Language for Mathematical Programming (2 ^{nd} edition)*,
Duxbury Press/Brooks-Cole Publishing Company, 2002. GAMS user’s can try translating their model to AMPL language
using the translation tool available at http://www.gamsworld.org/translate.htm.

MProbe comprises a set of tools for viewing and analyzing the components of a mathematical model. The tools are grouped into a number of "Workshops": Variables Workshop, Constraints Workshop, Objectives Workshop, and Constrained Region Workshop. The tools are summarized below, grouped by the type of mathematical program to which they apply.

- a listing of
**statistics**about the model (numbers of variables by type, number of quadratic and general nonlinear constraints, number of linear constraints, etc.) - simple
**navigation**of the model (which variables are in this function? which functions contain this variable, etc.) - analysis of
**constraint effectiveness**(fraction of the variable space that each constraint eliminates) **selective viewing of variables, constraints and objectives**(e.g. show only the constraints which contain only binary variables, or show only the variables which appear in a particular constraint)**sorting of variables, constraints and objectives**under user control (e.g. sort constraints in decreasing order by constraint effectiveness, sort variables in decreasing order by number of constraints they appear in, etc.)- analysis of
**redundancy and feasibility.****fraction of the "surface"**of the feasible region for necessary constraints. - tools for
**tightening the bounds**around the region of interest (often the feasible region). - Find
**near-feasible points**. **read in points**from an external file (e.g. generated by solver) and analyze properties of the point or the region around the point.- identification of
**best point found**for each objective while sampling. - optional generation of a
plain text
**trace**of the analysis session - a
**direct link to AMPL**. A menu choice brings up AMPL in a window so that models can be created or recalled. - a
**modern windowed interface**with a**full help**system.

**analysis of constraint and objective shape**(concavity, convexity, linearity, close-to-linearity, close-to-convexity, etc.), including a histogram which assists in judging how concave or convex a function is.**estimation of function range**(maximum value, minimum value, histogram of function values over many points)**estimation of function "slope"**(actually a multidimensional analog of slope, with a histogram of random tests over the variable space)**function plotting**between any two arbitrary points (which can assist in determining why a solver is stuck at a particular point when a feasible point giving a better function value is known to exist)- estimation of the
**shape of the constrained region**(convex? nonconvex?) - estimation of the
**objective effect**(global optimum? local optimum?)

**Variable ordering:**Sort the integer or binary variables according to the number of constraints in which they appear.

**Constraint ordering:**sort the constraints in order of estimated effectiveness. This helps to promote early failure of search tree branches.

The most important new features are:

· The Constraint Consensus method is a variant of a projection algorithm for seeking feasibility. Tests show that it can be a very effective method for achieving near-feasibility from starting points that are very far away from feasibility, even in the face of nonconvex constraints. The constraint consensus method is new used in 3 places in MProbe, as described below.

· Points Workshop: allows import and export of points (e.g. from a solver), analyzes the properties of points (e.g. how close to feasibility) and the properties of the region around the point (e.g. how flat is the objective function in this region?). Can find an approximate feasible point (or even a feasible point under certain conditions) using the Constraint Consensus method.

· Ability to read in and edit MPS files directly. Can display constraints and objectives read from MPS files in a natural equation format.

· An improved method for shrinking the variable bounds, using the Constraint Consensus method. This method is especially useful when many of the variables are initially unconstrained.

· An improved bootstrapping method for finding an initial feasible point for sampling inside a convex enclosure, based on the Constraint Consensus method.

· Numerous minor bug fixes.

A student/demo edition of MProbe is available for free, and can be downloaded as described below. An unlimited professional edition is available for purchase (see below).

A freely distributable student/demo edition of MProbe is available for download as described below. Limits are as follows: maximum of 100 variables in the model, maximum of 100 constraints in the model, maximum of 6 variables in any function. The student/demo edition is fully functional, aside from these limits, and includes a student version of AMPL.

The student/demo edition runs under the Microsoft Windows 32-bit operating systems. It is packaged as single WinZip file.

**Installation:**

- After downloading the files,
unzip them in a directory (e.g. C:\temp\MProbeInstall), and then issue the
command
*setup*in that directory. The setup procedure will ask you where you wish to install MProbe: choose a directory different than the installation directory (e.g. C:\MProbe). - For installation on Windows NT, version 3.51 with service pack 5 or greater is required (Windows NT 4.0 is recommended). Thanks to David Gay for this pointer.
- New users are advised to
look at the tutorial material in the MProbe help system, particularly the
*Introduction and Orientation*and the*Brief Tour*, before beginning to use MProbe.

A Professional Edition of MProbe is available by contacting the author . A student/demo edition of AMPL for Microsoft Windows 32-bit operating systems is included as part of the MProbe installation, but you may wish to contact an AMPL vendor to upgrade to a professional edition of AMPL. New versions of the student edition are also released regularly and are available at no charge from the AMPL web site.

The maximum number of variables, constraints, and objectives in the Professional Edition is limited only by available memory on your system.

Prototypes of MProbe date to 1994. The first publicly-available, web-distributed version, (MProbe 1.01) dates to October 1996. See the change log for a list of changes introduced by each version since 1.01.

MProbe development is ongoing. What do you like/dislike? What would you like to see in the next version? Have you found a bug? Please email me with your thoughts and suggestions.

Email also if you would like to receive occasional email updates on new releases, bug fixes, etc. The volume of email will be low (a few messages per year at most).

There are several other MPROBEs on the web. Here are some of the more popular:

- an MPEG file analyzer
- a Fortran timing routine
- telescope monitoring program
- a computer memory probing program

MProbe is also used as a short version of "market probe", "molecular probe", "medical probe", "memory probe" etc. on some web pages or web page names.

*If you need to reference MProbe in
your publications, you can use the following: *

John W. Chinneck (2002), “The Constraint Consensus Method for Finding Approximately Feasible Points in Nonlinear Programs, technical report, Systems and Computer Engineering, Carleton University, Canada. Pdf (130 kbytes). Describes the Constraint Consensus method used in several places in MProbe 4.0.

John W. Chinneck (2002), “Discovering the Characteristics of
Mathematical Programs via Sampling”*, Optimization Methods and Software*,
vol. 17, no.2, pp. 319-352. PDF
of draft version. Describes the sampling algorithms used in MProbe version 3.2, and the
kinds of information that can be extracted via sampling.

John W. Chinneck (2001), “Analyzing Mathematical Programs using MProbe”, *Annals
of Operations Research*, vol. 104, pp. 33-48. PDF
of draft version. Describes
an older version of MProbe, but does provide an overview of capabilities.

*MProbe user’s guide in French:*

Nathalie Perrier (2002), “Analyse de
fonctions non linéaires avec MProbe”, École Polytechnique de Montréal. MS-Word
(188 kbyte), PDF
(1.6 Mbytes).

*For those interested in
participating in MProbe-related research:*

John W. Chinneck (2001), *MProbe Research Plans 2001*. This brief article describes some possible
directions for future MProbe-related research, and invites participation by
other researchers. PDF
source (21k).

last modified: March 12, 2003.