2 Variations

There are useful practical variations in notation that can be reduced to a standard model type.

  1. The objective function can be a maximizing function:

    max   f (x)

    To translate it into a standard form, one only needs to write it as :

    min   - f(x )
  2. A maximin (or a minimax) objective has the form:

    max   (mini  f(xi))  ,  min   (maxi   f(xi))  with i ∈ {1, ...,n},n > 0

    It can be translated into (while z is an additional variable):

    max  z  subject to f(xi) ≤ z   forall i ∈ {1, ...,n},n > 0

    min  z  subject to f(xi) ≥ z   forall i ∈ {1, ...,n},n > 0

    This notation is useful for example in zero-sum games, in regression models and others (see model regression).

  3. An arbitrary (non-linear) objective function f(x) can be replaced by a linear function by introducing an additional variable z. Then the general model is replaced by:

    min        z
subject to  gi(x) ≤ 0   forall i = 1,...,m
           x ∈ X

           f (x ) ≤ z
  4. A fractional linear objective can be replaced by a linear one. The method is explained in model bill046

  5. The variables x in a standard model are free. If they must be positive only, then one can easily add the constraints: (x 0).

  6. If the constraints are gi(x) 0, they can be replaced by -gi(x) 0.

  7. If the constraints are equalities, as in gi(x) = 0, then they can be replaced by gi(x) 0 and gi(x) 0 constraints.

  8. Inequality constraints can be substituted by equality constraints containing an additional variable as follows: gi(x) 0 can be substituted by gi(x) + p = 0, where p is an additional variable p 0. gi(x) 0 can be substituted by gi(x) - n = 0, where n is an additional variable n 0.

  9. A model with k multiple objectives, say f1(x),,fk(x) can be formulated by forming a new combined objective f as follows:

    f(x) = w1f1 (x) + ...+ wkfk (x )

    where w1,,wk are numbers (weights) that reflect the importance of the single objectives (the higher the number, the more important the objective). An illustrative example is give in the model multi1.

  10. A useful variant is goal programming by the means of soft constraints. In many situation, we do not mind if a particular constraint is slightly violated. For instance, with a given budget of $1’000’000, it would certainly be acceptable to over- or undershoot it by, say, $100. On the other hand, a constraint that defines Expenses = Budget, enforces exactly the amount. To resolve (and relax) this problem, the constraint can be made “soft”, that is, two positive variables p and n are added to absorb a positive or negative deviation (slacks) from the budget goal, and the constraint is modified to

    Expenses   + n - p = Budget    (n,p ≥ 0)

    In the objective function, a weighted sum of these slack variables can be minimized (as seen in the previous item about multiple objectives, or the maximal deviation can be minimized. Hence, the goal, namely “attaining the budget exactly” is substituted by the goal “attaining the budget approximately”. Several positive and negative slacks could be added to a goal constraint, that can be penalized with an increasing weight parameters in the objective function. This method is closely related with the problem of multiple objectives: The objectives are – between others – to minimize the deviations of the different goals. A example to illustrate this technique is given in the models goalpr and in goalpr1.

  11. Preemptive goal programming is another technique to handle soft constraints. Finding the right weights for the different goals in an multiple objective function is sometimes difficult. Hence, in this method the user orders the goals in a list of decreasing importance. The first optimization minimizes/maximizes the most important goal. Then the corresponding slack variables are fixed and the next goal is optimized, and so on, until all goals has been optimized. Formally, solve the model first with f1(x) (supposing f1 is the most important goal). Let the optimal value be f1o, then add the constraint g m+1(x) = f1(x) - f1o = 0. Now continue in the same way with the second most important objective, an so on until the least important objective. This method is illustrated by the model goalpr2. A real model where this method is used can be found in the Casebook II.

In an application, the objective function may have various meaning. We may maximize profit, utility, turnover, return on investment, net present value, number of employees, customer satisfaction, probability of survival, robustness; or we may minimize cost, number of employees, redundancy, deviations, use of resources, etc.

The constraints reflect a large variation of requirements in a concrete application. In a production context there may be capacity, material availability marketing limitation, material balance constraints; in a resource scheduling we may have due date, job sequencing, space limitation constraints, etc.

In the following sections various model types are presented and most of them implemented:

  1. Linear programs (LP) consist of linear constraints and a linear objective function and real variables.

  2. Integer (linear) programs (IP) consist of linear constraints and a linear objective function and integer variables.

  3. 0-1 (linear) programs consist of linear constraints and a linear objective function and binary variables (integer variables with only values of 0 and 1). This type is a special case of the previous one, where variables are integer but can only take the values 0 or 1. From the formulation point of view, the difference between the three types is very small. However – as we shall see – the difficulty to solve integer problems is much higher. Linear programs (LP) can be solved in polynomial time, while IP and 0-1 IP problems are mostly NP-complete. The application field of these three model types is very large. We shall point to examples.

  4. Quadratic problems (QP) which consist of linear constraints and a quadratic convex objective function.

  5. 0-1 quadratic problems (0-1-QP) which consist of linear constraints and a quadratic convex objective function and contain 0-1 variables. Both types have interesting applications in portfolio theory.

  6. Quadratic constraint problems (QCP) which consist of linear and quadratic convex constraints and a quadratic convex objective function.

  7. Second order cone problems (SOCP), which have many applications in physics. All of these previous model classes are convex problems – a much easier to solve.

  8. Non-convex quadratic problems (NCQP), an interesting application is given below. All of these previous model classes can today be solved by linear programming commercial solvers like Gurobi or Cplex.

  9. A large class of models is the non-linear optimization model class (NLP). Many solver exist for specific subclasses of this class. Also some general commercial solvers exist such as Knitro or LocalSolver.

  10. Many application in physics, biology, or economy use dynamic models which are basically discrete dynamic system or systems of differential equations.

  11. A particular class is the permutation class. Many routing, scheduling, or assignment problems can be formulated in this way, a concrete example is given, more of them can be found in the paper [9].

For most of the model types, a concrete application and an implementation in LPL is given. We shall show the gap in difficulty to solve integer problems compared to non-integer linear problems.

Of course, one can also build combined models: LP model part mixed with IP model leads to mixed integer programs (MIP) containing real and integer variables, etc.