TransWikia.com

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

Mathematica Asked by Jakub Petrůj on January 10, 2021

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```

2 Answers

(* 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.

Answered by flinty on January 10, 2021

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[]]
]

Answered by Cesareo on January 10, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP