Adding a new problem

Before adding a MILP formulation, you must create the optimization problem. This consists of writing a description, defining the necessary input data, and generating/solving a concrete instance of the problem. Afterward, you can add MILP formulations for the problem (see Adding a new formulation).

First, pick the next free identifier pN (e.g. p21) and create the directory problems/p21/. Next, populate this directory with all the files required by the dataset schema (see Problem Directory). The sections below walk through creating every necessary file. Lastly, append the problem identifier to the problems field in dataset.json.

Description

The description.md file contains a natural-language description of the optimization problem. This description populates problem_description when rendering a formulation in Markdown (see Formulation.render_markdown()). Problem descriptions vary in size.

problems/p1/description.md

An amusement park is installing cash-based machines and card-only machines. A cash-based machine can process CashMachineProcessingRate people per hour, while a card-only machine can process CardMachineProcessingRate people per hour. The cash-based machine needs CashMachinePaperRolls rolls of paper per hour, while the card-only machine requires CardMachinePaperRolls rolls of paper per hour. The amusement park needs to be able to process at least MinPeopleProcessed people per hour but can use at most MaxPaperRolls paper rolls per hour. Additionally, the number of card-only machines must not exceed the number of cash-based machines. The objective is to minimize the total number of machines in the park.

problems/p12/description.md

The Traveling Salesman Problem (TSP) aims to find the shortest cycle in a graph that visits every node exactly once.

Find other problem descriptions in Problems.

JSON File

The problem.json file defines the problem name, data parameters, and additional metadata. See Parameter for the parameters schema. The metadata field is freeform and typically includes source and notes fields which populate the source and notes blocks on the Problems pages.

problems/p1/problem.json

{
    "name": "Amusement Park Ticket Machines",
    "parameters": {
        "CashMachineProcessingRate": {
            "description": "Processing rate of a cash-based machine in people per hour",
            "type": "continuous",
            "shape": []
        },
        "CardMachineProcessingRate": {
            "description": "Processing rate of a card-only machine in people per hour",
            "type": "continuous",
            "shape": []
        },
        "CashMachinePaperRolls": {
            "description": "Number of paper rolls used per hour by a cash-based machine",
            "type": "continuous",
            "shape": []
        },
        "CardMachinePaperRolls": {
            "description": "Number of paper rolls used per hour by a card-only machine",
            "type": "continuous",
            "shape": []
        },
        "MinPeopleProcessed": {
            "description": "Minimum number of people that must be processed per hour",
            "type": "continuous",
            "shape": []
        },
        "MaxPaperRolls": {
            "description": "Maximum number of paper rolls that can be used per hour",
            "type": "continuous",
            "shape": []
        }
    },
    "metadata": {
        "source": {
            "dataset": "EquivaFormulation",
            "instance_id": 47
        },
        "notes": [
            "The source variable type is continuous; we correct the variable type to integer.",
            "The cutting plane (source variation `47_e`) is excluded because it is instance-specific.",
            "Implicit non-negativity assumptions are added for every parameter."
        ]
    }
}

problems/p12/problem.json

{
    "name": "Traveling Salesman Problem (TSP)",
    "parameters": {
        "n": {
            "description": "Number of cities",
            "type": "integer",
            "shape": []
        },
        "c": {
            "description": "Travel cost from city i to city j",
            "type": "continuous",
            "shape": [
                "n",
                "n"
            ]
        }
    },
    "metadata": {
        "source": {
            "dataset": "EvoCut"
        },
        "notes": [
            "EvoCut arXiv submission `v1` proposes three inequalities used to generate formulations `p12.b-d`.",
            "EvoCut arXiv submission `v2` proposes five inequalities used to generate formulations `p12.e-i`."
        ]
    }
}

Data & Solution

A single concrete instance must be defined in data.json. Its keys should match the parameter keys defined in problem.json.

Provide its optimal solution in solution.json. This dictionary has variables and objective keys. Note that variable values are specific to a formulation, not a problem. By convention, use the variable names of formulation a for the problem.

problems/p1/data.json

{
    "CashMachineProcessingRate": 20,
    "CardMachineProcessingRate": 30,
    "CashMachinePaperRolls": 4,
    "CardMachinePaperRolls": 5,
    "MinPeopleProcessed": 500,
    "MaxPaperRolls": 90
}

problems/p1/solution.json

{
    "variables": {
        "NumCashMachines": 10.0,
        "NumCardMachines": 10.0
    },
    "objective": 20.0
}