Skip to main content

Optimization Problem Guidelines

This document provides instructions on accepted formats for optimization problems in the Optimization use case. Assigning proper feature groups is crucial for obtaining optimal solutions.

Overview​

The Optimization use case solves integer programming problems for:

  • Scheduling
  • Resource allocation
  • Finding shortest paths
  • And more

The two most important feature groups are:

  1. Assignment Feature Group (FG)
  2. Constraint Feature Group (FG)

Assignment Feature Group​

Every optimization problem has an Assignment FG that describes all possible assignments in a schedule.

Feature Mappings​

1. ASSIGNMENT (Required)​

  • Represents variables that are assigned values when the optimization problem is solved
  • Can take integer, boolean, or float entries
  • Every Assignment FG must have an assignment feature mapping

2. BOUNDS​

  • Specifies bounds and nature of assignments
  • Format: STRUCT with entries:
    • lowerBound (int)
    • upperBound (int)
    • isInteger (bool)

3. OBJECTIVE​

  • Represents the cost of an assignment in the objective to be minimized
  • In planning problems, typically represents costs related to a schedule or plan

4. SELECTOR​

  • Identifier for columns used in the Prediction Dashboard
  • Allows assigning specific values to query assignments
  • Not used in model training
  • Can be used for multiple columns

5. HINT​

  • Represents an approximate value of the predicted assignment
  • Serves as initial values for assignments in the planning solution
  • Actual solution may differ from hints
  • Can be used for multiple columns

6. FIX​

  • Represents values of predicted assignments that are fixed
  • These values will not change in the solution
  • Can be used for multiple columns

7. METRICS​

  • Columns marked as metrics appear on the metrics page after model training
  • Shows the values they take
  • Can be used for multiple columns

Constraint Feature Group​

Each dataset represents a constraint family that can be configured.

Feature Mappings​

1. ASSIGNMENT​

  • References an assignment from the Assignment Feature Group
  • Contains the unique identifier of the assignment

2. GROUP​

  • Identifier for a single group of variables to be constrained
  • Groups together assignments that share a common constraint equation
  • All assignments in a GROUP must collectively satisfy the given constraint

3. COEFFICIENT​

  • Represents the coefficient of the assignment term in the constraint group
  • In linear constraints, each term is a product of a variable (ASSIGNMENT) and a COEFFICIENT
  • Indicates the weight that variable has in the constraint equation

Adding Constraints​

Every constraint table requires specification of:

  • Inequality type
  • Constants
  • Penalty for breaking the constraint (in case of infeasibility)
  • Enforcement type (hard/soft)

Think of this as the right-hand side (RHS) of the inequality formed by the constraint FG.

Custom Table​

Describes all forced assignments in a schedule. The model learns to incorporate these forced assignments into generated solutions.

Use cases: Hard constraints or specific requirements that must be satisfied, such as:

  • Resource availability
  • Task dependencies

Feature Mappings​

  1. ASSIGNMENT: The assignment to specify a value for
  2. ASSIGNMENT_VALUE: The value to assign

Example: Stigler Diet Problem​

The goal of the diet problem is to select a set of foods that will satisfy a set of daily nutritional requirement at minimum cost. The problem is formulated as a linear program where the objective is to minimize cost and the constraints are to satisfy the specified nutritional requirements. Here we are solving it for float assignments.

Input Dataset

  1. Food: 77 food items and the cost wise normalised amount of all 9 nutrients in each of them.
  2. Nutritional Requirement: 9 nutrients and their daily required amounts.

Assignment FG The 'Food' dataset is used to create the assignment FG. The feature mappings are:

  1. ASSIGNMENT : The column with names of food. The goal is to attach values to each food item to signify the daily amount required.
  2. OBJECTIVE : Cost column is Objective. In this problem cost is 1 for each food because nutrition content is normalised wrt cost.
  3. BOUNDS : Created a seperate counds column with lowerBound 0, upperBound 100, isInteger False to support float assignments.
  4. All other columns can be either SELECTOR or METRICS.

Constraint FG The idea to express the constraints as linear expressions of type: {sum for i=1 to n (a_i x b_i)} < inequality > < constant >.

We create a table with 78 x 9 rows. Each food item and nutrient pair has a seperate entry in this table. The columns are Commodity, Nutrient and Value. For each nutrient we added a row with Commodity as null, Nutrient is the name of the nutrient and Vlue is the negative of Dialy Nutritional Requirement

  1. ASSIGNMENT : Commodity
  2. GROUP : Nutrients. Each constraint equation is grouped by the common nutrient.
  3. COEFFICIENT : Value ie, the nutrient for each assignment
  4. Constraint inequality: Here we have used >= inequality and constant as 0.