Table of Contents
Describes the input file format for robust problems.
Static Robust Optimization
Classic Robust Optimization
A (classic) static robust optimization considers problems of the form
\[\begin{align*} \min_{x\in X} \quad & c^\top x \\ \text{s.t.} \quad & \sum_{j=1}^n (\bar{a}_j + \hat{a}_ju_j)x_j \ge b, \quad\text{for all } u\in U. \end{align*} \]
Here \(U\) models the uncertainty set which contains a (possibly infinite) set of possible scenarios for the parameters \(u\).
Example
We consider the robust problem
\[\begin{align*} \min_{x,y} \quad & -x - 2y \\ \text{s.t.} \quad & (1 + u_1) x + (1 + u_2) y \le 2, \quad\text{for all } u\in U, \\ & x,y \in\{ 0,1 \}, \end{align*} \]
where \(U := \left\{ u\in\{0;1\}^2 : u_1 + u_2 \le 1 \right\}\).
The .mps file for the deterministic problem is given by
The .mps file for the uncertainty set is given by
Finally, an additional file, with extension .par, is used to indicate the uncertainty parameterization in the deterministic model
Here, the uncertain parameters enter the constraint matrix. For instance, in the constraint with name "c", the variable with name "x" has an uncertain coefficient of one associated to the parameter "u_1".
Detailed Description
In idol a static robust instance is made of three files:
- A first .mps/.lp stores the model for the deterministic problem, i.e., here,
\[ \begin{align*} \min_{x\in X} \quad & c^\top x \\ \text{s.t.} \quad & \sum_{j=1}^n \bar{a}_jx_j \ge b. \end{align*} \]
- A second .mps/.lp stores the uncertainty set \( U \).
- A .par file indicates where the uncertain parameters enter in the deterministic problem. Here, it should indicate that each variable \(x_j\) has an uncertain coefficient \( \hat{a}_ju_j \) in the respective constraint.
In case multiple uncertainty sets must be used, they are all represented in a single .mps/.lp.
For more details on the .mps and .lp file formats, see the page Input Format for MILPs.
The .par file is composed of tagged sections, each identified by a keyword starting with @. The following table lists all supported tags and their meaning.
| Tag | Meaning |
|---|---|
| @RHS | This section contains the uncertain parameterization of the constraints right-hand side |
| @OBJ | This section contains the uncertain parameterization of the objective function coefficients |
| @MAT | This section contains the uncertain parameterization of the constraint matrix |
Sections may be empty if no uncertainty of that type exists in the problem.
Right-hand Side Uncertainty
The @RHS section is composed by a list of entries with the format <CTR> <UNC_VAR> <COEFF>, where <CTR> is a constraint name, <UNC_VAR> is an uncertainty parameter name (which must be defined in the uncertainty set), and <COEFF> is a number. Each entry specifies that the right-hand side of the constraint <CTR> has an uncertain contribution equal to <COEFF> times <UNC_VAR>.
Objective Uncertainty
The @OBJ section is composed of a list of entries with the format <VAR> <UNC_VAR> <COEFF>, where <VAR> is a variable name, <UNC_VAR> is an uncertainty parameter name (which must be defined in the uncertainty set), and <COEFF> is a number. Each entry specifies that the objective coefficient of the variable <VAR> has an uncertain contribution equal to <COEFF> times <UNC_VAR>.
Constraint Matrix Uncertainty
The @MAT section is composed of a list of entries with the format <CTR> <VAR> <UNC_VAR> <COEFF>, where <CTR> is a constraint name, <VAR> is a variable name, <UNC_VAR> is an uncertainty parameter name (which must be defined in the uncertainty set), and <COEFF> is a number. Each entry specifies that the coefficient of the variable <VAR> in the constraint <CTR> has an uncertain contribution equal to <COEFF> times <UNC_VAR>.
Decision-Dependent Robust Optimization
Two-Stage Robust Optimization
Two-stage robust optimization problems are problems of the form
\[ \begin{align*} \min_{x\in X} \ c_x^\top x + \max_{u\in U} \ \min_{y\in Y(x,u) } \ c_y^\top y, \end{align*} \]
where \( U \) denotes the uncertainty set, \( X \) denotes the first-stage decision feasible region and \( Y(x,u) \) denotes the second-stage decision feasible region.
Example
We consider the two-stage robust problem
\[ \begin{align*} \min_{x\in \mathbb{Z}\cap[0,5]} \ 3x + \max_{u\in [0,3]} \ \min_{y} \ 10y \quad \text{s.t.} \quad x + y \ge 5 + u, \ y\ge 0. \end{align*} \]
The .mps file for the deterministic model reads
The .mps file for the uncertainty set reads
The .par file for the uncertainty parameterization reads
The aux file for indicating the second-stage variables and constraints reads
Detailed Description
The format used to describe two-stage robust problems is based on how static robust problems are described but with an additional file indicating which variable and constraint belong to the second stage.
Thus, four files are necessary to define a two-stage robust problem.
- A first .mps/.lp stores the model for the deterministic problem, i.e., here,
\[ \min_{x\in X, y\in Y(x,0) } \quad c^\top x \]
- A second .mps/.lp stores the uncertainty set \( U \).
- A .par file indicates where the uncertain parameters enter in the deterministic problem.
- A .aux file indicates which variable and constraint belong to the second-stage problem.
For more details on the .mps and .lp file formats, see the page Input Format for MILPs.
For more details on the .par file format, see the section on Static Robust Optimization.
For more details on the .aux file format, see the page Input Format for Bilevel Problems.
If lower-level coefficients are given in the .aux file, say \(d\), then the problem will be considered as a robust bilevel optimization problem with a wait-and-see follower, i.e., problems of the form
\[ \begin{align*} \min_{x\in X} \ c_x^\top x + \max_{u\in U} \ \min_{y\in S(x,u) } \ c_y^\top y, \end{align*} \]
where \( S(x,u) \) denotes the set of solutions to the \((x,u)\)-parameterized problem\[ \min_{y'} \ d^\top y \quad\text{s.t.}\quad y'\in Y(x,u). \]
Generated by
1.16.1