Using Mixed Integer Linear Programming to Solve Optimization Problems

Linear programming is used to obtain the optimal solution for a problem by representing a real life scenario as a mathematical model with defined constraints.

Typical linear problems consist in finding the optimal values for a set of attributes (inputs) in order to minimize costs or maximize performance levels.

Rulex provides mixed integer linear programming, which means that:

  • the model and the constraints must be expressed as linear combinations of the inputs

  • the optimal values for the inputs can either be expressed as a rounded-up integer or as a continuous value.

Prerequisites

  • a Rulex process has been created

  • the required datasets have been imported into the process

  • the input dataset must have the following structure:

    • a column with a label describing the contents of the row (objective function, constraints etc.)

    • a column for every variable included in the problem

    • a column containing the right hand side (constant term) of constraints

    • a row labeled with the objective function (valid strings are objective or cost)

    • a row for each constraint

    • optional rows with the minimum and/or maximum for each variable (by default 0 and infinite).

Additional tabs

The following additional tabs are provided:


Procedure

  1. Drag and drop the Mixed Integer Linear Programming task onto the stage.

  2. Connect the Mixed Integer Linear Programming task to the task which contains the data for the optimization model.

  3. Double click the Mixed Integer Linear Programming task. The left-hand pane displays a list of all the available attributes in the dataset, which can be ordered and searched as required.

  4. Configure the options as described in the table below.

  5. Save and compute the task.

Mixed Integer Linear Programming options

Parameter Name

PO

Description

Overwrite data with solution coefficients

overwrite

If selected, the outcome data will be passed on to successive tasks. Otherwise the results will be saved within the task itself only, and the input dataset will be passed on as output.

Optimization mode

linprogsense

Select whether you want your solution to Maximize or Minimize the outcome.

Attribute for constraint (and cost) types

linprogtypenames

Select the attribute (column) which contains the row type, which can be:

  • cost, objective, c, o (for the row that contains the cost function coefficients)

  • == (for equalities, constraints)

  • >=, >, etc. (for comparative constraints, such as greater than, equal to etc.)

  • min, max (for minimum and maximum values respectively)

Attribute for right hand side values

linprogrhsnames

Select the attribute (column) that contains the constants for the constraint rows.

Maximum execution time

linprogmaxtime

Specify for how many seconds the task can run. If not specified, no time limits are set.

Maximum number of iterations

linprogmaxiter

Specify how many times the task can be run. If not specified, no limits on the number of iterations are set.

Coefficients for integer solution

linprogintnames

Drag and drop from the Available attributes list the coefficient attributes that will be used in the calculation, if the results must be provided as an integer. Instead of manually dragging and dropping attributes, they can be defined via a filtered list.

Note that the type of the associated coefficient attribute is independent from the type of the result you want to obtain.

Coefficients for continuous solutions

linprogcontnames

Drag and drop from the Available attributes list the coefficient attributes that will be used in the calculation, if results can be provided as a continuous value. Instead of manually dragging and dropping attributes, they can be defined via a filtered list.

Note that the type of the associated coefficient attribute is independent from the type of the result you want to obtain.

Results

The results of the task can be viewed in two separate tabs:

  • The Solution tab displays the generated solutions. The tab will display the results only if you have not selected the Overwrite data with solution coefficients option.

  • The Results tab, where information on the task execution is displayed, such as the elapsed time.

Example

In the following example a factory wants to maximize its profits by understanding the optimal amount of final product to make from its currently available material.

Scenario data can be found in the Datasets folder in your Rulex installation.

The following steps were performed:

  1. First we import the yogurt dataset with an Import from Excel File task.

  2. We add a Mixed Integer Linear Programming task and define the mathematical problem.

  3. Finally we add a Data Manager task to view the resulting solution.

Scenario

The basic scenario used in this example involves a small family-run farm factory where two types of yogurt are produced:

  • deluxe strawberry yogurt, which contains two units of yogurt and two units of strawberries, and produces a profit of 3 euros per unit of finished yogurt.

  • super saver yogurt, which contains three units of yogurt and one unit of strawberries, and produces a profit of 2 euros per unit of finished yogurt.

There are currently 15 units of yogurt and 10 units of strawberries in stock, and at least two units of each type of yogurt must be produced to meet current orders.

Objective: The factory wants to maximize its profits by finding out the optimal amount of deluxe and super saver yogurt to make with its currently available stock.

The information in the scenario can be mathematically expressed as follows

  • The amount of deluxe yogurt to produce = x

  • The amount of saver yogurt to produce = y

  • The maximum profit = z

  • Consequently z = 3x (profit multiplied by the amount produced) + 2y

Our constraints are as follows:

  • Strawberry stock constraint: 2x + y <= 10

  • Yogurt stock constraint: 2x + 3y <= 15

  • Minimum values:

    • x >=2

    • y >=2

This information can be expressed in an Excel file as follows:

Procedure

Screenshot

After importing the yogurt excel file, add a Mixed Integer Linear Programming task and select the following options:

  • Select Overwrite data with solution coefficients to view the solution results in the successive Data Manager task.

  • Optimize mode > Maximize, as we want to maximize our profits.

  • Attribute for constraint (and cost) types > specify the Type column, which contains the functions.

  • Attribute for right hand side values > specify the RHS column, which contains the constants.

  • Maximum execution time > specify a maximum of 10 seconds.

  • Maximum number of iterations > do not provide a maximum number of iterations.

Drag and drop the attributes for the two types of yogurt into the Coefficients for integer solutions target list, as we want the solution to be expressed as whole units, and not continuous values.

After saving and clicking Compute process to start the analysis, the solution to our problem can be viewed in the Data Manager task.

The maximum profit is 16 euros (objective), if we produce (and obviously manage to sell):

  • 4 units of deluxe strawberry yogurt

  • 2 units of super saver strawberry yogurt.

The same information can be viewed directly in the Solutions tab of the Mixed Integer Linear Programming task if we do not select Overwrite data with solution coefficients.



Search