Before we examine a simple representative example illustrating the modelling aspects of this format, it is important to emphasize the following points with regard to the target problem and its parametric problem:

• The objective function of the target problem is linearized with respect to u not x.
• The decision spaces of the two problems are identical, ie. equal to X.
• C-programming is concerned with situations where each instance of the parametric problem is much easier to solve than the target problem.
• C-programming is "not concerned", so to speak, with how instances of the parametric problem are solved. This process is viewed as a "black box".

The following example illustarates these points.

Example 1
Consider the following nonlinear optimization problem:

There are two obvious ways to phrase this problem according to the c-programming format. We shall consider the one in which the composite function handles the square root, namely

Editorial Comment:
Here I use Greek letters instead of C and b simply because I already have the figures in Greek. I''ll fix this matter soon.

This formulation yields the following parametric problem:

Observe that for any given value of b this problem has a linear objective function with respect to the decision variable x. Thus, if for instance X is defined by a system of linear equations/ inequalities, the parametric problem is a standard linear programming problem.

Needless to say, the idea is to solve Problem P(b) for a value of b such that any optimal solution generated for Problem P(b) is also optimal for Problem T . We shall refer to such a b as an optimal b . The fundamental methodological question is then: under what conditions such a b exists?

The main objective of this section is to introduce the Fundamental Theorem of C-programming. This theorem is concerned with conditions under which an optimal parameter for Problem T exists and its relation to the constructs (X,u,C) involved in the formulation of Problem T :

Suffice it to say that the proof is immediate as it follows directly from the definition of differentiable pseudoconcave functions and the fact that any differentiable pseudoconcave function is also quasiconcave.

Convention :
Unless explicitly stated other-wise, properties such as differentiability and convexity of the composite function C will refer to u not x. Thus, if we say that C is differentiable, we mean that it is differentiable with respect to u and when we say that C is pseudoconcave we mean that it is pseudoconave with respect to u. Also, unless explicitly stated otherwise, any reference to optimal solutions should be construed as a reference to global optimal solutions.

Now, back to the Fundamental Theorem and the following issues that it raises.

• The theorem is a "classical" first-order necessary optimality condition.

• The theorem is completely oblivious to the structure of X. Thus, it allows X to be a discrete set. This means that although the Fundamental Theorem of C-programming is "classical" in nature, c-programming is capable of handling combinatorial optimization problems. In fact, c-programming was designed with this class of problems in mind.

• As in the case of many other classical first-order optimality conditions, eg. the revered Kuhn-Tucker Conditions, the theorem is not particularly constructive in that it does not suggest a procedure for recovering an optimal solution to ProblemT via the first-order condition that it provides. But please, don't panic yet! We shall deal with the algorithmic aspects of c-programming shortly.

• The theorem can be modified and refined in several ways.

In view of the non-constructive nature of the Fundamental Theorem , any attempt to establish c-programming as a viable optimization tool necessarily requires the development of a general framework for the formulation of c-programming algorithms. But at the same time, it must be appreciated that the parametric nature of c-programming and the extremely rich family of problems that are covered by the Fundamental Theorem do not allow us to compose a detailed blueprint for a "general purpose c-programming algorithm". There is no such beast and it can be safely said that no such thing is likely to ever be invented.
Rather, the situation can be described as follows: a typical c-programming algorithm invariably consists of three interrelated procedures to which we shall refer as the b-procedure, x-procedure and a-procedure. Here are their respective short resumes:

• b-procedure: I generate a sequence of bs in a manner that guarantees that one of these bs is optimal with respect to Problem T. This sequence is not determined in advance, but rather depends on input from the x- procedure and a-procedure.
  Furthermore, I am very much problem-oriented, meaning that the way I operate depends very much on the structure of the problem being solved and the structure of the x-procedure used. Generally speaking, I use standard Lagrangian techniques and related exclusionary rules. More details about my mode of operation can be found in the references listed below.

• x-procedure: For each value of b generated by the b-procedure, I solve Problem P(b) and report the results to my team-mates. Whenever possible I try to avoid solving these parametric problems from scratch, namely I try to use a "warm" start approach, where the solution to the last problem is used, if possible, to speed-up the recovery of a solution to the current problem.

• a-procedure: I am responsible for all sorts of administrative tasks required to ensure good coordination between the b-procedure and x-procedure. I take the liberty of saying that in some cases our team-effort is so smooth and seamless that from the outside it looks as if only one procedure is at work.

In a number of publications (see bibliography) it has been shown that c-programming provides interesting methodological and theoretical results. The best example would be the way it treats fractional programming problems. Here it would suffice to say that c-programming gives the parametric method of fractional programming (ie. Dinkelbach's Algorithm) a classical interpretation.
However, as interesting as such results might be, I cannot overemphasise my view that c-programming is meant to be a practical tool, namely a tool to be used by analysts in the design and implementation of solution procedures for difficult "real-world" problems.
Yet, it has been my experience over the past few years that there is a lot of scepticism out there about the ability of the (b,x,a)-team to cope with "practical, real-world problems". In fact, I discovered that a number of referees of leading international journals are among the sceptics.
So it is very important to emphasize that there are large classes of interesting and challenging real world problems where our (b,x,a)-team does perform extremely well.

Bibliography:

• Macalalag, E. and Sniedovich, M. (1993), On the Importance of Being a Sensitive LP Package. Preprint Series No. 3-1991, Department of Mathematics, the University of Melbourne.
• Sniedovich, M. (1985), C-programming: An Outline. Operations Research Letters 4(1), 19-21.
• Sniedovich, M. (1986), C-programming and the Minimization of Pseudolinear and Additive Concave functions. Operations Research Letters 5(4), 185-189.
• Sniedovich, M. (1988), Fractional Programming Revisited. European Journal of Operations Research 33(1988), 334-341.
• Sniedovich, M. (1989), Analysis of a Class of Fractional Programming problems. Mathematical Programming 43(3), A, 329-347.
• Sniedovich, M. (1992), Dynamic Programming. Marcel Dekker, New York.
• Sniedovich, M. (1994), Algorithmic and Computational Aspects of Composite Concave Programming. International Transactions in Operations Research, Vol.1, No.1, 75-84.
• Sniedovich, M. (1994a), Introduction to Composite Concave Programming and its Applications. CLAIO94', Santiago Chile.
• Sniedovich, M., Macalalag, E., and Findlay, S. (1994), The Simplex Method as a Global Optimizer: A C-programming perspective. Journal of Global Optimization 4, 89-109.

Refers to:
Concave, global optimization, Newton method, fractional programming, Dinkelback's algorithm, linear programming, pseudoconcave, quasiconcave, multiplicative programming

Referenced by:
Contributor: Moshe Sniedovich
Status: Work in progress.

Crawl back to front

Dynamic Programming

Fractional Programming

Multiplicative Programming

Soft Constraints

Steiner Trees

Modeling and Simulation

Crawl back to front

Crawl back to WORMS

• Do not waste time trying to find too many excuses for not starting your work on your entries immediately. One good excuse is sufficient.
• WVE is designed for the general OR/MS public, not specialists in the various fields. Thus, do not write your entry for a specialist in the subject.
• Whatever you do, keep in mind that we may end up producing hard copies and/or CD versions of WVE.
• Don't hide what you do from the public! Let us see your drafts.
• The average entry should be about 2-3 pages long. If you feel that you need more space consider splitting your entry into a number of smaller entries.
• Do your best to recruit other persons to this project. In particular, PhD students should be encouraged to take an active part in this enterprise.
• Hopefully in a year or so it will be much easier to incorporate mathematical notation in HTML files. If you do not trust us, see the latest news on HTML 3 in our Webstuff directoy. In the mean time use whatever method you prefer. We may soon have more to say about this very embarrassing issue. If you have five minutes to spare, have a look at the two articles in Iota.
• It is not known yet what subject index/indices will be used. You are welcome to have a look at the entries in the Key-words directory.
• It is extremely important that you update your "Refers to" and "Referenced by" lists as you develop your entries.
• Don't worry at this stage on such issues as: what English dialect will be used in the final edition? Would it be optimisation or optimization, modelling or modeling? We may end up using a mixture of dialects. The only thing you should know at present is that WORMS Chief Spider prefers the American dialect.
• By the same token, don't worry now on questions of style and formats, eg. references, tables, captions, etc. We shall keep you informed about such matters.
• All you have to do to join this project is send us the title(s) of the entry(ies) you want to work on and the WWW address(es) where it(they) can be found.
• If you are not HTML literate and/or cannot establish a directory of your own, we shall be delighted to help. We can create a directory for yourentry on our system and maintain it for you. We shall be willing to accept contributions in any "reasonable" format, eg. text, postscript, Tex, Word, etc. In this case we suggest that you visit our Clinic and Rehabilitation Center.
• Do not hesitate to tell us if you are interested in working on an entry that is already taken by someone else.
• We shall do all in our power to keep this international cooperative project a Lawyers Free Zone. Copyright issues will have to be addressed if and when hardcopies and/or CD versions of WVE will be considered. Remember, the average entry will be 2-3 pages long.

Crawl back to front

Crawl back to WORMS