I am building a CPLEX model (VRP-like). In one of the model constraints I am forcing an initial flow from the depot to the each one of the different sets of customers I have, at least, sufficient to cope with the demands of the customers of the sets.

As such, say I have n different I[i] sets, with i = 1..n. And then, for each I[i] the sum of the arcs leaving the depot to each one of the elements in I[i] shall count as the capacity of a truck, say Q, if the arc is traversed. Hence, the aforementioned sum shall be greater or equal to the sum of the demands, say d[I[i][j]] for each one of the customers j in I[i] to ensure enough trucks will enter the set I[i].

In other "words": \sum_{j\in I_i} {Q*x_{0, j}}\geq\sum_j\in I_i{d_j}. If I export the CPLEX model I have those constraints, e.g.

V.1.FlowCreation_a(1)#1484:     600000 ArcRouting(2)(1)(1)(44)#17223
                              + 600000 ArcRouting(2)(1)(1)(45)#17225
                              + 600000 ArcRouting(2)(2)(1)(44)#17229
                              + 600000 ArcRouting(2)(2)(1)(45)#17231
                              + 600000 ArcRouting(2)(3)(1)(44)#17235
                              + 600000 ArcRouting(2)(3)(1)(45)#17237
                              + 600000 ArcRouting(2)(4)(1)(44)#17241
                              + 600000 ArcRouting(2)(4)(1)(45)#17243
                              + 600000 ArcRouting(2)(5)(1)(44)#17247
                              + 600000 ArcRouting(2)(5)(1)(45)#17249
                              + 600000 ArcRouting(2)(6)(1)(44)#17253
                              + 600000 ArcRouting(2)(6)(1)(45)#17255
                              + 600000 ArcRouting(2)(7)(1)(44)#17259
                              + 600000 ArcRouting(2)(7)(1)(45)#17261
                              + 600000 ArcRouting(2)(8)(1)(44)#17265
                              + 600000 ArcRouting(2)(8)(1)(45)#17267
                              + 600000 ArcRouting(2)(9)(1)(44)#17271
                              + 600000 ArcRouting(2)(9)(1)(45)#17273
                              + 600000 ArcRouting(2)(10)(1)(44)#17277
                              + 600000 ArcRouting(2)(10)(1)(45)#17279
                              >= 12000

The first dimension on the ArcRouting(..)(..)(..)(..) variables describes the number of the set of elements, 2 in that case, the second one the vehicle number, ranging from 1 to 10, while the third describes the departure node, and the fourth one the arrival node. That is why the third one is always 1, since node 0 is renamed as 1 during the LP exportation, and the fourth one only contains 44 and 45 since that specific set only contains a couple of elements.

As you can notice, it suffices that an arc be set to one (regardless of the vehicle used or customer from I[2] to visit) to meet the constraint, since, one truck could deliver up to 600.000 units while customers' joint demand is only 12.000 units.

The problem is that when I try to solve the model I get the following error:

Warning: Control callbacks may disable some MIP features.
Lazy constraint(s) or lazy constraint callback is present.
Disabling dual reductions (CPX_PARAM_REDUCE) in presolve.
Disabling non-linear reductions (CPX_PARAM_PRELINEAR) in presolve.
Infeasibility row 'V.1.FlowCreation_a[1]':  0 >= 12000.
Presolve time = 0.08 sec. (20.62 ticks)

Root node processing (before b&c):
Real time             =    0.09 sec. (21.15 ticks)
Sequential b&c:
Real time             =    0.00 sec. (0.00 ticks)
Total (root+branch&cut) =    0.09 sec. (21.15 ticks)

What is the Infeasibility row 'V.1.FlowCreation_a[1]': 0 >= 12000. letting me know of my model that I don't fully understand?

asked 14 Oct '16, 13:44

Jackobian's gravatar image

accept rate: 0%

It's a bit hard to be certain, giving the naming convention of your variables and constraints (which I think is why you see those # symbols and sequence numbers following the names), but I suspect that the presolver decided, presumably based on some other constraints, that all the "ArcRouting" variables in the first flow creation constraint had to be zero, which then makes that constraint zero.

To track down the precise problem, I suggest that you come up with what you think is a feasible solution (without regard to objective values), fix the variables to those values (by setting lower bound = upper bound = value), and try to solve the model. If CPLEX reports it is infeasible, run the conflict refiner and find out which constraints and variable bounds form a minimal infeasible set; then look for a formulation error within them.


answered 15 Oct '16, 15:19

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 14 Oct '16, 13:44

Seen: 902 times

Last updated: 15 Oct '16, 15:19

OR-Exchange! Your site for questions, answers, and announcements about operations research.