Optimization

New help documentation

See also https://www.heurekaslu.se/help/en/index.html?optimering.htm , under construction.

About the optimization tool

Assignment problem

The optimization problem solved in Heureka can be categorized as an assignment problem: Each treatment unit should be assigned a treatment schedule. The problem types handled are linear programming (LP) and 0/1 mixed-integer linear programming (MIP or MILP). The difference between the two is how treatment schedules are assigned. If a treatment unit can be assigned one and only one alternative, then the associated decision variables are set to binary (by the user). If the management of a treatment unit can be "split" and spatial integrity is not an issue, then these variables can be treated as continuous variables (default). In this case the value of the decision variables refers to the proportion of treatment unit area that should be managed with a certain schedule. More information on decision variables is given below.

ZIMPL

For PlanWise a very flexible optimization tool is built-in for formulating and solving LP and MIP problems. The optimization tool is basically a graphical user interface to the ZIMPL optimization modelling language. For solving a problem, external third-party solvers are used and directly linked to the optimization tool. Currently, the solvers available are listed below:

Solvers

For solving a problem, external third-party solvers are used and directly linked to the optimization tool. Currently, the solvers available are

• CoinOR CLP/CBC, which is freely available under the Eclipse public license v 2.0 and included in the Heureka installation.
• SoPlex, which is freely available for academic use. You will need the SCIP Windows binary (exe) file ("SCIP version 3.0 (Windows/PC 64 bit)" has been tested with Heureka), and specify the path under Settings.
• Gurobi^®, versions 9.0 - 10.0
• IBM CPLEX^®, version 22.1.0
• MOSEK^®, version 7-8.1
• FICO Xpress^®, version 7.9

CPLEX, Gurobi, Xpress and MOSEK are very efficient, state-of-the-art solvers. They require a license, which can be obtained for free for academic use. These solvers must be obtained and installed by the user, they are not distributed with the Heureka install package.

CoinOR CLP/CBC is an efficient free alternative and performs well in benchmarks.

LpSolve is no longer supported (from version 2.20).

Integration with prognosis data

The optimization model is linked to a Heureka-formatted SQL Server database used for storing input data, simulation data, and result data. This enables a seamless integration with the input data required by the optimization model, as well as direct presentation of optimization results in the form of tables, graphs, and maps. This simplifies the analysis and visualization of scenarios or plans of forest development and outputs.

Settings

Applying a LP-optimization model in forest management planning, integer solutions are sometimes of interest. A stand is usually regarded as a treatment unit to be completely treated according to a certain treatment in a certain period. This might be of special interest when it comes to short term-planning, i.e. what to do now and in the next year - couple of years.

The most straightforward way to obtain integer solutions is to allow only integer values of the decision variable, i.e. constrain the range type of x_{i, j} to "Binary". However, this might lead to infeasible solutions. Another way is to round off to closest integer value (0 or 1), hence forcing the results to be a set of complete treatment programmes for each stand in the analysis area. In menu "Optimization" > "Settings...":

• The General-tab allows the user to, e.g., selecting "Round to integer solution". Do observe that this is done after solving the optimization problem. Any results shown in the output window will not be rounded off (except the decision variable, with its actual value within parentheses). Results derived from the result database will however be of integer solutions, if this was selected. Optimization results are saved to the database by pressing the "Save"-button in the optimization model builder-window. As an alternative to rounding off, the "Mip Gap" gives an opportunity to accept a solution not certainly optimal. A relative gap of 1% imply that the solution might be one percentage from the optimum. An absolute gap is defined in the same unit as the objective function. The "Time Limit" defines the time, in seconds, for the optimization model to search for a feasible solution.
  • Relative mip gap: Relative optimization tolerance. The optimization algorithm stops when an integer solution is quaranteed to be within this percentage of the true optimal solution.
  • Absolute mip gap: Absolute optimization tolerance (not available in Lp_Solve). The optimization algorithm stops when an integer solution is proven to be within this absolute difference of the optimal solution.
  • Time limit: The maximum time for the solving a problem. If the time limit has been passed but an optimal solutions has not been found, the best solution found is returned. For difficult problems it is possible that no feasible solution is found.
  • Round to integer: If check, decision variables are rounded to the nearest 0/1 integer value.
• The SCIP/SoPlex Settings-tab: Here you select the SCIp/SoPlex binary file (.exe) that you must have on your disk, see Optimization.

Managing models

A standard optimization model is distributed with the program. There is also the opportunity to create a new model from scratch, or to use a wizard guide to taylor an optimization model with some of the most common objective functions and restrictions. All these models can then be further modified and saved by the user.

To create and save models, used the buttons at the top of Optimization Model window, or the Model Wizard button in the Models section further down in the same window.

For more info on the Model Wizard, please confer the Heureka Help

Editing an optimization model

Sets

When you create a new model, the following set are added automatically:

• treatmentUnits: Set of all treatment units. Index = i.
• alternatives: Set of all management schedule numbers. Index = j. Note: Alternative j for one treatment unit has nothing to with alternative j for another unit. The number of available j:s varies between treatment units.
• periods: Time periods. Index = p. The length of a period is five years in strategic planning, and one year in tactical planning.
• rowNo: Index for the treatment number in a time period that a treatment unit alternative refers to.

When adding opening size constraints (from the menu Optimization > Add Opening Size Constraint), additional sets are added.

You can also add arbitrary sets manually, for e.g. organizational units, road ID columns, and so on.

Decision variables

When you create a new model, some basic problem elements are added automatically (the sets and some constraints), including the most important decision variables. The decision variable x[i,j] is always added:

x[i,j] = proportion of the area of treatment unit i that is managed with management schedule j.

By default, the x[i,j] variables are continuous (non-integer) and bounded between 0 and 1. You can change the variable to binary (0/1-integer) by changing its RangeType to Binary, thus changing the problem type from LP to MIP.

A constraint called maxArea is also added automatically. It ensures that the area managed for each treatment unit is correct, so that the whole area (no more and no less) is assigned a schedule. Each treatment unit must be fully assigned a management. "No management" may be counted as an alternative, depending on what control categories are used when generating the alternative with the Treatment Program Generator.

Adding an accounting variable

Accounting variables are preferrably added to the optimization model to improve readability and simplify the writing of constraints. An accounting variable is defined - it is a function of other decision variables in the model. The definition is actually an equality constraint in the the optimization model.

One example of a useful accounting variable is total harvested volume in a period. This variable can then be used in other constraints.

To add an accounting variable:

1. In the Optimization Model window, right-click in the "Variables" section and Select "Add new variable"
2. Right-click on the variable and change its name from "DefaultName..." to something more proper, in the example below volTot.
3. To define an indexed variable, for example to have one variable for each time period, click on Data binding > Sets, and add the index set, for example "periods". After that the variable name should have a suffix ([p]).
4. In the syntax window, type the definition with the the expression on the left side and the name of the variable on the right-hand side of an equality-symbol marked as "==". Example: An ccounting variable for total stand volume is defined, with an index p for time period. Note that before adding the variable, the parameter volume[i,j,p] (which is linked to the Heureka result variable Forest Data.Volume Before) must have been added. Syntax:

   FORALL <p> IN periods DO

   SUM <i,j> IN treatmentunits * alternatives WITH altIncluded[i,j] == 1:

   volume[i,j,p] * area[i] * x[i,j] == volTot[p];

Important! By default, a variable (decision or accounting) has the property RangeType set to non-negative. This means that negative values are considered infeasible. For example, a volume cannot be negative. However, some accounting variables should be allowed to take negative values, for example the net revenue in a period can be negative if costs are larger than revenues. In this case you must change its RangeType to "All".

Adding a parameter which is linked to a prognosis variable

The coefficients in the LP-models (the coefficient matrix is usually denoted as A) are constant values in the optimization model. In Heureka, these coefficients are generated by the Treatment Program Generator and referred to as Heureka result variables. A coefficient may represent for example stand volume for a given treatment unit, management schedule alternative, and time period. Hence, stand volume is a variable in a prognosis, but a constant/parameter in the optimization model.

1. In the Optimization Model window, right-click in the "Parameters"-section and Select "Add new parameter"
2. Type a name, for example "pulpWood" (without apostrophes)
3. Let "Heureka result variable" be selected
4. Click Next
5. Select Financial Value > PulpWood Volume Total (if this is the variable you are interested in)
6. Click Finish

To check what Heureka variable a certain parameter is linked to:

1. Select the parameter
2. In the Properties window for the parameter (under the syntax window), under Databinding > ResultProperty, you can see what Heureka variable the parameter is bounded to. If you click on it you can change the binding.

Adding a parameter that has a definition

1. In the Optimization Model window, right-click in "Parameters" section and Select "Add new parameter"
2. Type a name, for example "totalArea" (without apostrophes)
3. Select "Formula" as parameter type
4. Click Next
5. In the syntax window, type the defiintion, for example

   sum <i> in treatmentunits: area[i];

   (This can be edited later)

6. Click Finish

Note 1

When defining an accounting variable (see above), you would also add a definition to the variable itself, such as == VariableName. For a defined parameter, you only type the expression.

Note 2

A shortcoming of a parameter with a formula is that you cannot preview its value.

Adding a constraint

1. In the Optimization Model window, right-click in "Constraints" and select "Add new constraint"
2. Type a name, for example "MinOldForestArea" (without apostrophes)
3. Click OK
4. Select the constraint in the model tree and type the definition in the syntax window. For example, to add a constraint to ensure a non-declining harvest over time, you would type:

   forall <p> in periods with p >= 1 : TotalHarvestVolume[p] >= TotalHarvestVolume*[p-1];

   (If you have defined an accounting variable for total harvest volume)

5. Click Finish

Note

For constraints, you do not add indices explicitly as you do with variables. In the example, we do not add "p" for periods, but the "forall"-statement will take care of generating one constraint for each time period.

Tip

Use accounting variables in constraints to simplify reading and formulating the model, as well as to minimize problem size (considerably fewer coefficients and only a few additional variables).

Adding opening size constraints

The generation of an EARM-model (see Goycoolea et al 2005) is automated. The original model have been adapted to suit the way management alternatives are handled in Heureka (decision variables are defined for complete treatment schedules instead of single treatment activities). To formulate and EARM-model, select Add Opening Size Constraints from menu Optimization.

To use this functionality, you must have provided a forest map. There is a built-in function to compute adjacency pairs, and enumeration of harvest blocks (combinations of polygons) that meet a given maximum opening size tolerance. (The computed adjacency pairs and their common border lengths can also be used in user-defined spatial constraints such as a URM (Unit Restriction Model)). The program can then calculate all feasible combinations of treatment units (that form harvest clusters), compute all so called cliques, and all constraints necessary. For more info, see .

A very fast algorithm has been developed in Heureka to compute what Goycoolea et al (2005) refer to as cliques and clusters.

Linking management in partial set-asides to parent stands

• Partial set-asides (hänsynsytor) within stands can be handled as separate treatment units, in which no harvest activities are carried out. The development in such set-asides is in reality affected by the surroundings in the way that the risk of mortality increases in the set-aside after clear-cutting the main stand. In PlanWise, you can let the program generate alternatives for the set-aside area for each management program generated for the main stand, let the mortality be affected by when and if clear-cutting takes place in the main stand, and also choose to link nature conservation management activities to coincide with management activities in the parent stand. This is non-default, by default only one alternative is generated for the set-aside. If choosing the non-default optiona link between the set-aside and the main stand is added automatically to the optimization model. Read more here: http://heurekaslu.se/help/index.html?naturvardsatgarder.htm, section "Lämnande av hänsynsytor" (only in Swedish).

Using neighborhood relations for habitat analyses

Neighborhood areas can be calculated for each stand. This means that for a user-specified radius originating from the centroid of each stand, the area for every other stand that is overlapped by the circle is computed. This information can then be used in optimization models that take habitat area requirements into account (see Öhman et. al 2011). The necessary variables can be added to any optimization model, for modification of the habitat conditions to reflect the species of interest.

The needed model parameters, variables, and constraints for including a habitat demands are pre-formulated in Heureka and can automatically be included in the model formulation of an optimization problem. This is done by adding neighbourhood constraints available in the optimization tab (Optimization / Add Neighborhood Constraints). After this is done the user must specify three parameters in the optimization model:

• the stand specific conditions that should be fulfilled before a stand qualifies as a habitat (the habitat condition parameter, habitatCondition[i,j,p),
• the amount of suitable habitat required within a stand's neighbourhood for the stand to be qualified as habitat (minHabitatAreaInNeighbourhood)
• the minimum proportion of the entire forest that should meet the habitat conditions in each period (minTotalHabitatAreaProportion)

Before solving the optimization problem, the user must also run the tool ”compute stand neighbourhood” to calculate the area of each other stand that is within the neighboring area of a stand. When this tool is executed the parameter standNeighbourhood is filled out.

Solving problems and saving optimization results

When a problem has been formulated and is ready to be solved, and you have run the Treatment Program Generator (TPG), the problem is ready to be solved:

1. Right-click in the optimization model tree view, and select "Compile and Solve"
2. Select the TPG result that the optimization model will be solved for and click OK
3. Wait until the solver has finished

After solving, you will see the problem status in the output window (at the bottom). If you have obtained a feasible solution the solution status will be reported as "Optimal". To be able to view the optimization results in reports, you must first save the optimization result. You do this by clicking on the button "Save Optimization Result", at the top of the Optimization Model window.

Infeasible solution?

If the problem status is Infeasible, no solution has been found. There are two main reason why this may occur:

• There is some error in the optimization model.
• No solution exists. The constraints are too severe.

To identify the cause of the problem, include constraints, one by one, in a systematic order. Try to solve the problem after including each constraint.

Note

Do not exclude the constraint "maxArea".

Importing optimization solutions from external sources

You can use an external analytics software to solve your optimization problem outside the interface of PlanWise, for example AIMMS, AMPL, Python or R. It is then possible to import that solution to PlanWise, for example to use the report tool to build charts. See the Help for further instructions.