ASCEND (the language) exists to separate, when desirable, the formulation of a mathematical problem (numeric) from the solution of the that problem. ASCEND (the interface) exists to give the user as much (or as little) control over the compilation and solution of their problem as they want.
The problems expressible in the language cannot (and indeed should not) be reduced to a single formulation if the solutions are to be implemented in a robust, efficient, and user controllable manner. All but one of the solving engines attached to ASCEND must inevitably be hamstrung if we insist that they all fit in the same interface shoebox. Witness the minos/lsode implementations in the Pascal-version. The alternative is to make all engines talk through an interface defined by the intersection of the engines' individual interfaces. This alternative is unacceptable from a software engineering point of view.
This portion of the interface, then, has the task of making every engine conform to a minimum set of semantics (thus enabling the GUI/ CLUI to support the user wanting very little control over a host of powerful solving engines) while giving the power hungry user access to those parameters specific to a given engine. The minimum semantics chosen, due mostly to convenience and the biases of the developers, are those of slv0 with the provision of a set of arrays for the passing of auxillary, or 'sub', parameters to each solver.
- See also:
- slv_common.h for the data structures we desire to have common to all the solvers.
Dates: 06/90 - original version KMW
01/94 - modified tolerances, eliminated var_to_name
and rel_to_name function pointers, and
expanded status report
04/94 - expanded scope of slv0 to perform optimization
05/94 - added counting routines to count variables,
boundaries, and relations which pass some
specified filter
10/94 - added stubs for OPT and QRSlv
1/95 - moved status and parameters definitions to
slv_common.h. BAA
02/96 - added stubs for NGSlv. KTH
06/96 - split into client and server headers.
0/97 - added stubs for CONOPT. KTH
The inputs to any solver consist of a formulation of the problem to solve along with a set of parameters to allow user control of the solution process. The general formulation is given below (for non-discrete problems only):
min F(x,u,c)
s.t. h(x,u,c) = 0
r(x,u,c) = 0
g(x,u,c) >= 0
b(x,u,c) >= 0
A variable list consists of fixed (c), independent (u), dependent variables (x), and unattached variables (q). A relation list consists of unconditional (or global) equality constraints (h), conditional equality constraints (r), and inequality constraints (g), each of type struct rel_relation *. The conditional equalities are isolated from the global equalities because they are only defined for certain ranges in values of the variables, expressed through a set of inequality boundary relations (b), each of type bnd_boundary_t which may or may not be satisfied at any given point. An objective function (F) is used to provide a criteria with which to optimize the values of the independent variables.
The objective function is a relation (LHS only) struct rel_relation * and may be set (its default is NULL) using slv_set_obj_relation. The variable, boundary, and relation lists are pointer lists of struct var_variable * and struct rel_relation * and are expected to be NULL terminated. This means that for 10 variables to be placed in a list, for example, 11 elements must exist in order to reserve the last pointer to be NULL. These lists ARE REQUIRED to be set.
The additional set of inputs are the slv_parameters. These can specify stopping conditions or the amount of information displayed during solving, for example. Monitoring of the solution process is done using the status report for solvers that iterate. More details are given with the respective declarations below.
Right, so we're going to have a client-server, object-oriented, open-architecture system designed to handle multiple clients in a single-thread process. Furthermore, the clients will NOT have to know anything at all about the ASCEND IV compiler hidden out back some place -- in fact our compiler may not BE out back, it may be on another machine or swapped to disk or whatever.
That's the ideal. In most applications of ASCEND, particularly the interactive one, the compiler is never very far away. Isolating the compiler data completely (meaning no looking back at it for anything) would mean recreating all the relations (be they tokens, calls to C code, or any kind) in a separate process. This is unacceptable from a memory conservation point of view until RAM comes down to ~$1/MByte, especially if ASCEND is to run on PCs any time soon.
Haha :-) $1/MB! Jan 2006: 118 AUD = 512 MB = ~ 0.15 USD/MB -- johnpye
What we really have then is a slv_system_t made up of variables and relations and hiding all the compiler details from the clients. Clients will operate directly on the slv_system_t only through real C functions and not through macros so we can hide all the nasty details about the compiler. Variables and relations only make sense in the context of a slv_system_t, so the var_variable type and the rel_relation type in this C code sometimes require that the system pointer be provided when asking for certain properties or services.
The 'analysis' routines (see analyse.h) provide a number of lists to the solver, including real-valued solver variables, relations, WHENs, boundaries, logical relations, and some more.
There are 'master' lists, which contain the lists of entities in their 'natural' order as discovered in the Instance hierarchy.
Then there are the 'solvers' (ie solver's) lists, which are reordered in a formed defined by the solver. "the solvers var list is to be fetched by the solvers".
Eventually the solvers_varlist will only include those vars the specific solver needs to know about. For the moment, the content of the two lists is the same, but the ordering is not. The master list is in the order collected. The solvers list is reordered in some useful fashion defined elsewhere.
Parameters are problem invariant constants that the GUI user might change before solving another problem using the same MODEL.
- Note:
- Efficiency note relating to slv_count_master_*: if you are using this with a match anything filter, you would be better off just calling the slv_get_num_* function for the list in question.
where do these solver's lists get reordered?
If the system already has such a list, the old list will be freed unless the two lists are in fact the same (in which case why are you calling this?). Size is the length of the vlist (excluding the terminal NULL entry). The sindex field of each var in the list should match it's list position.
The list should be NULL terminated and the size should be the length of the list EXCLUDING the terminal NULL.
The question is ambiguous. In ASCEND we have the notion of a solver_var ATOM type that includes bounding values, a scaling value, and other properties. These are not the only real-number based items that can occur, however. For purposes of the CLIENT application programming interface (API) we collect all the real- based objects we can find and map them all to struct var_variable. See var.h for details. We sort them into lists as follows:
- vars. These are solver_var that are in an objective or relation.
- pars. These are solver_par appearing parametrically.
- unattached. These don't appear in relation or objective, and they may be solver_var or solver_par or neither. We keep 2 versions of each list: one for ourselves which is READ- ONLY for clients and allows us to do many things efficiently, and another for clients that clients may rearrange (or even delete) as suits their needs. The former version is called a master list, and the latter version is called a solvers list.
At present a relation in ASCEND is either an objective function (a one-sided relation) or a constraining equation. We have a variety of relation implementations within ASCEND, but all any client needs to know about relations can be found in the rel.h file. We keep master and client lists of relations as well. We provide a variety of interesting services with relations:
- residual and gradient calculations
- symbolic inversion (where possible)
- numeric root finding
- scaling based on symbolic arguments
- symbolic determination of linearity and we expect to add others as they occur to us or you suggest them.
It's has a host of interesting properties.
- One slv_system_t (system, hereafter) can only be used by one registered* client at a time, but if your client is an unregistered manager of several subclients (for example an NLP code and and MILP code) then you can pass it back and forth to those registered clients to solve an MINLP. (Note: we haven't done this ourselves yet.) Any number of unregistered clients may share a system, but they must take responsibility for not stepping on each other or the registered client. Registration will be explained further below.
- From any given ASCEND type definitions, the master lists in the system will be ordered identically across all invocations of ASCEND on any hardware that we are aware of. This property is derived from the way we compile instances and create systems. This is helpful in benchmarking and other applications.
- We have a number of standard clients (registered and not) you can use on a the system to precondition it in some way for your client:
- Degrees of freedom analysis.
- Problem decomposition.
- Reordering of vars and rels for good factorization.
- Solution of square nonlinear systems.
- Generation of MPS code for popular MILP solvers.
- Generation of GAMS code for an old, slow compiler of an extremely awkward modeling language that does happen to have a lot of really good optimizers connected.
Short term, we expect to construct a client that takes the partitioned problem and hands off the blocks in sequence to one or more solvers designed to handle only 1 block.
Long term, we anticipate that the structure laid out so far is capable of expansion (probably by intermediate clients which add additional semantic content) to provide standardized (mtx and harwellian) sparse matrix support and memory management for codes that don't care to think about such things directly.
- Note:
- We are going through a solver API definition restructuring. The appearance of NOTEs in the header means the code in question has, or is about to have, a change in its meaning or is code that is new and replaces some or all the functionality of an old function definition. Basically, expect to have to read NOTE sections carefully and maybe patch calls dependent on them.
Generated on Thu Jul 17 04:00:54 2008 for libascend by
1.5.1