| Austin Schuh | 405fa6c | 2015-09-06 18:13:55 -0700 | [diff] [blame] | 1 | * This input file is an example for generating |
| 2 | * integral solutions to the following system of linear inequalities: |
| 3 | * 10 x1 + 7 x2 <= 70 |
| 4 | * 11 x1 + 5 x2 >= 55 |
| 5 | * x1 >= 0, x2 >= 0 |
| 6 | * By using the fact that 0<=x1<=7 and 0<=x2<=10, we apply |
| 7 | * the (binary representation) substitution: |
| 8 | x1 = 4 x13 + 2 x12 + x11 (all binary variables) |
| 9 | x2 = 8 x24 + 4 x23 + 2 x22 + x21 (all binary variables) |
| 10 | * The reduced system of linear inequalities is the input data. |
| 11 | * Since all integral (i.e. 0-1) solutions are extreme points, |
| 12 | * the integral extreme points are in one-to-one correspondence |
| 13 | * with the integral solutions to the original system. In this |
| 14 | * example, there are 194 extreme points among which 10 are |
| 15 | * integral (0-1) solutions. |
| 16 | |
| 17 | H-representation |
| 18 | begin |
| 19 | 16 8 integer |
| 20 | 0 1 0 0 0 0 0 0 |
| 21 | 0 0 1 0 0 0 0 0 |
| 22 | 0 0 0 1 0 0 0 0 |
| 23 | 0 0 0 0 1 0 0 0 |
| 24 | 0 0 0 0 0 1 0 0 |
| 25 | 0 0 0 0 0 0 1 0 |
| 26 | 0 0 0 0 0 0 0 1 |
| 27 | 1 -1 0 0 0 0 0 0 |
| 28 | 1 0 -1 0 0 0 0 0 |
| 29 | 1 0 0 -1 0 0 0 0 |
| 30 | 1 0 0 0 -1 0 0 0 |
| 31 | 1 0 0 0 0 -1 0 0 |
| 32 | 1 0 0 0 0 0 -1 0 |
| 33 | 1 0 0 0 0 0 0 -1 |
| 34 | 70 -40 -20 -10 -56 -28 -14 -7 |
| 35 | -55 44 22 11 40 20 10 5 |
| 36 | end |