# How to know, which constraint is being violated in linear programming problem?

my task is to minimize costs of dispatching various power plants in order to meet demand in a transmission grid. I solve the task as a linear programming problem with the help of Minimize[] function for total costs. It all works fine for reasonable inputs. If I input unreasonable value (high electrictity demand) the error message occurs and the programme crushes. Is there a way, how to get to know, which constraint is being violated? Down below are just written definition of variables and an example of one set of constraints. They represent capacities on different lines. I need to know, which one is congested - which of these constraints is being violated. Is there a way?

 Promenne = Table [Subscript[x, i, j], {i, 3}, {j, 4}]

   Subscript[x, 1, 4] <= 50 &&
0.2 Subscript[x, 1, 2] + 0.8 Subscript[x, 1, 3] +
0.7 Subscript[x, 1, 4] + 0.3 Subscript[x, 2, 1] +
0.3 Subscript[x, 2, 3] + 0.2 Subscript[x, 2, 4] +
0.5 Subscript[x, 3, 1] + 0.1 Subscript[x, 3, 3] <= 50 &&
0.8 Subscript[x, 1, 2] + 0.2 Subscript[x, 1, 3] +
0.3 Subscript[x, 1, 4] + 0.8 Subscript[x, 2, 1] +
0.3 Subscript[x, 2, 3] + 0.2 Subscript[x, 2, 4] +
0.5 Subscript[x, 3, 1] + 0.1 Subscript[x, 3, 3] <= 50 &&
Subscript[x, 2, 1] + Subscript[x, 2, 2] + Subscript[x, 2, 3] +
Subscript[x, 2, 4] <= 50


• (1) By crash, do you mean a Mathematica kernel crash? If so, that would be a bug and we would want an example to investigate. – Daniel Lichtblau Nov 29 '20 at 17:01
• (2) A way to deduce violators, less efficient but perhaps still "good enough", would be to use NMinimize after changing constraints into penalty terms. Then you get a solution and can check explicitly for violators. Depending on how the penalty terms are constructed, there could be multiple violators. – Daniel Lichtblau Nov 29 '20 at 17:03

## 2 Answers

With this set of constraints there is a solution which is the trivial solution. My procedure

vars = Flatten[Table[Subscript[x, i, j], {i, 3}, {j, 4}]];
restrs1 = Thread[vars >= 0];
restrs2 = {Subscript[x, 1, 4] <= 50 &&
0.2 Subscript[x, 1, 2] + 0.8 Subscript[x, 1, 3] +
0.7 Subscript[x, 1, 4] + 0.3 Subscript[x, 2, 1] +
0.3 Subscript[x, 2, 3] + 0.2 Subscript[x, 2, 4] +
0.5 Subscript[x, 3, 1] + 0.1 Subscript[x, 3, 3] <= 50 &&
0.8 Subscript[x, 1, 2] + 0.2 Subscript[x, 1, 3] +
0.3 Subscript[x, 1, 4] + 0.8 Subscript[x, 2, 1] +
0.3 Subscript[x, 2, 3] + 0.2 Subscript[x, 2, 4] +
0.5 Subscript[x, 3, 1] + 0.1 Subscript[x, 3, 3] <= 50 &&
Subscript[x, 2, 1] + Subscript[x, 2, 2] + Subscript[x, 2, 3] +
Subscript[x, 2, 4] <= 50};

restrs = Join[restrs1, restrs2];

sol = FindInstance[restrs, vars]


Perhaps with more constraints the result changes...

NOTE

This can be used as follows

restrs1 =
{Subscript[x, 1, 4] <= 50,
0.2 Subscript[x, 1, 2] + 0.8 Subscript[x, 1, 3] +
0.7 Subscript[x, 1, 4] + 0.3 Subscript[x, 2, 1] +
0.3 Subscript[x, 2, 3] + 0.2 Subscript[x, 2, 4] +
0.5 Subscript[x, 3, 1] + 0.1 Subscript[x, 3, 3] <= 50,
0.8 Subscript[x, 1, 2] + 0.2 Subscript[x, 1, 3] +
0.3 Subscript[x, 1, 4] + 0.8 Subscript[x, 2, 1] +
0.3 Subscript[x, 2, 3] + 0.2 Subscript[x, 2, 4] +
0.5 Subscript[x, 3, 1] + 0.1 Subscript[x, 3, 3] <= 50,
Subscript[x, 2, 1] + Subscript[x, 2, 2] + Subscript[x, 2, 3] +
Subscript[x, 2, 4] <= 50}
restrs2 = Thread[vars >= 0]
restrs = Join[restrs1, restrs2]

For[k = 1, k <= Length[restrs], k++,
sol = FindInstance[Take[restrs, {1, k}], vars];
If[sol == {}, Print[k]; Break[]]
]

• It is not about this example. It is about minimizing criterial function by some conditions. I do not know, how to get to know, which condition is being violated, when the function minimize crashes, cause it cannot find a solution – Jakub Petrůj Oct 30 '20 at 13:28
• You can submit all your restriction set to know where the problem begins as in the attached note. – Cesareo Oct 30 '20 at 14:18
(* convert the constraints from && form to list form *)
constraintsList = constraints /. And -> List;

(* make some fake setting of the xij *)
SeedRandom[12345];
someSettingOfTheX = Flatten[
Table[Subscript[x, i, j] -> RandomReal[30], {i, 3}, {j, 4}],
1];

(* check which constraints it satisfies and violates *)
constraintsList /. someSettingOfTheX

(* result: {True, False, True, False} *)


A simpler example might be helpful:
objective = x^2;
constraints = {x > 0, x < 1, 3 x < 24};
{min, result} = Minimize[{objective, constraints}, x];

(** Minimize::wksol: Warning: there is no minimum in the region
in which the objective function is defined and the constraints
are satisfied; returning a result on the boundary. **)

constraints /. result
(* result: {False, True, True} *)


As you can tell, the result {x -> 0} does not satisfy the first constraint.

• It is not a problem, when I define the variables manually like this. Problem is, that these variables will be determined by Minimize function. And I would need to know, which of these constraints will be violated. Think like this, the programme will just crash again – Jakub Petrůj Oct 30 '20 at 13:23
• @JakubPetrůj someSettingOfTheX contains the resulting rules from Minimize. In my answer I used random data because you didn't provide an example assignment. Replace someSettingOfTheX = Last[Minimize[......]] then you'll see which constraints passed and which failed. If Minimize` is crashing, it should tell you which inputs crashed it. – flinty Oct 30 '20 at 14:16