Why does my AMPL code keep giving this error?

[erik baker]

Hi I am just trying to get some insight into fixing my AMPL code to solve a generalized network flow problem. I have posted my question at https://stackoverflow.com/q/71450106/18446673 

I have been trying to get my generalized network flow problem in AMPL but I keep running into this error:

presolve: constraint flow_balance['c5'] cannot hold:

body >= 0 cannot be <= -2500; difference = 2500 

presolve: constraint flow_balance['p1'] cannot hold: 

 body <= 0 cannot be >= 4500; difference = -4500 

presolve: constraint flow_balance['c5'] cannot hold: 

 body >= 0 cannot be <= -5300; difference = 5300 

presolve: constraint flow_balance['p1'] cannot hold: 

 body <= 0 cannot be >= 4800; difference = -4800

``` reset; option solver cplex; set NODES; # nodes in the network 

set ARCS within {NODES, NODES}; # arcs in the network 

param b {NODES} default 0; # supply/demand for node I 

param c {ARCS} default 0; # cost of one of flow on arc(i,j) 

param l {ARCS} default 0; # lower bound on flow on arc(i,j) 

param u {ARCS} default Infinity; # upper bound on flow on arc(i,j) 

param mu {ARCS} default 1; # multiplier on arc(i,j) -- if one unit leaves i, mu[i,j] units arrive var x {ARCS}; # flow on arc (i,j)

data Prob3.dat 

maximize profit: sum{(i,j) in ARCS} c[i,j] * x[i,j]; #objective: maximize arc flow profit 

# Flow Out(i) - Flow In(i) = b(i) 

subject to flow_balance {i in NODES}: sum{j in NODES: (i,j) in ARCS} x[i,j] - sum{j in NODES: (j,i) in ARCS} mu[j,i] * x[j,i] = b[i]; 

subject to capacity {(i,j) in ARCS}: l[i,j] <= x[i,j] <= u[i,j]; 

#subject to demand {i in NODES}: sum{j in NODES: (j,i) in ARCS} mu[j,i] * x[j,i] - sum{j in NODES: (i,j) in ARCS} x[i,j] = b[i]; 

solve; 

display profit; 

display NODES; 

display ARCS; 

display x; 

#note: default arc costs and lower bounds are 0 

# default arc upper bounds are infinity 

# default node requirements are 0 

# default multiplier is 1 

set NODES := p1 p2 p3 p4 #product time period nodes 

 r1 r2 r3 r4 #raw material time period nodes c1 c2 c3 c4 c5 c5p; #cash flow time period nodes set ARCS := (p1,p2) (p2,p3) (p3,p4) #inventory arcs (r1,r2) (r2,r3) (r3,r4) #raw inventory arcs (c1,c2) (c2,c3) (c3,c4) (c4,c5) #cash flow arcs (c5,c5p) #virtual arc (p1,c2) (p2,c3) (p3,c4) (p4,c5) #buy arcs final (r1,c2) (r2,c3) (r3,c4) (r4,c5) #buy arcs raw (c1,p2) (c2,p3) (c3,p4) #sell arcs final (c1,r2) (c2,r3) (c3,r4); #sell arcs raw param b:= p1 2000 #ending final product on-hand p4 2000; #initial final product on-hand #specify costs, upper bound, and multipliers for each arc param: c u mu l:= [p1, p2] 1.30 3000 0.94 . #holding cost, capacity, 1-spoilage rate [p2, p3] 1.30 3000 0.94 . [p3, p4] 1.30 3000 0.94 . [c1, c2] . . . . #final product period carry over cost [c2, c3] . . . . [c3, c4] . . . . [c4, c5] . . . . [r1, r2] 11 7500 0.45 . #raw material conversion [r2, r3] 11 9000 0.45 . [r3, r4] 11 8500 0.45 . [p1, c2] . 3000 38 2000 #final price [p2, c3] . 3000 40 2500 [p3, c4] . 5000 42 2800 [p4, c5] . 5000 42 2500 [c1, p2] . . -0.02631579 . #1/final price [c2, p3] . . -0.025 . [c3, p4] . . -0.02380952 . [r1, c2] . 7500 0.4 . #raw price [r2, c3] . 9000 0.4 . [r3, c4] . 8500 0.333 . [r4, c5] . 9200 0.286 . [c1, r2] . . -2.5 . #1/raw price [c2, r3] . . -2.5 . [c3, r4] . . -3.0 . [c5, c5p] -1 . 0 .; #virtual arc has negative cost to incentavize flow

I have posted my dat and mod files for reference. I know that the error is due somehow to the balance constraint but I am unsure why. I have tried to add min demand constraints but that seemed to make everything worse, I have tired redesigning the network flow chart multiple times and I've had no success. If anyone could provide some insight into why I can't figure this error out I would be extremely grateful.

[AMPL Google Group]

When I copy your model and data (from StackOverflow) into AMPL and try to solve, I see the same kinds of messages, but the details are different:

presolve: constraint flow_balance['p3'] cannot hold:
	body <= 0 cannot be >= 511.915; difference = -511.915
presolve: constraint flow_balance['p1'] cannot hold:
	body <= 2000 cannot be >= 4659.57; difference = -2659.57
presolve: constraint flow_balance['p3'] cannot hold:
	body <= 0 cannot be >= 3031.11; difference = -3031.11

The explanation is basically the same, however. With these messages, AMPL's presolve phase is telling you that your problem has no feasible solution: there is no way to assign values to the variables that are within the variables' bounds and that also satisfy all of the constraints. As an example, consider the second message, concerning constraint flow_balance['p1']. AMPL thinks of this constraint as having the "body" on the left and the constant term on the right, as shown in the "expand" output:

ampl: expand flow_balance['p1'];
subject to flow_balance['p1']:
	x['p1','p2'] + x['p1','c2'] = 2000;

In a feasible solution, the constraint body (on the left of the =) obviously has to be <= 2000. But the message also says that, based on an analysis of the constraints where the variables appear, AMPL has also proved that the body must be >= 4659.57 in any feasible solution. Since the constraint body cannot be <= 2000 and also >= 4659.57, this proves that no feasible solution is possible.

This proof of infeasibility occurs in AMPL's "presolve" phase, while the problem is being generated for the solver. Thus the problem is never actually sent to the solver. The infeasibility might be caused by an error in your model, or it may be that your data simply doesn't permit a feasible solution. Unfortunately, there is no simple and general way to deal with an error like this; you will need to study your model until you can understand the cause of the infeasibility. It is possible to suggest how to get started, however.

To see why the lower bound on the body of the constraint is so high, ask AMPL to show the bounds on the variables in that constraint. The tightest bounds found by presolve are given by the lb2 and ub2 suffixes on the variables:

ampl: display x['p1','p2'].lb2, x['p1','p2'].ub2;
x['p1','p2'].lb2 = 2659.57
x['p1','p2'].ub2 = 3000

ampl: display x['p1','c2'].lb2, x['p1','c2'].ub2;
x['p1','c2'].lb2 = 2000
x['p1','c2'].ub2 = 3000

Here it is clear that the large lower bounds on x['p1','p2'] and x['p1','c2'] are making the constraint flow_balance['p1'] impossible to satisfy. Then you can look for other constraints that are forcing those variables' lower bounds to be so high. (The "expand" output is often helpful for this.)

You can do the same for the other constraint mentioned in the presolve messages, though it is a little more complicated:

ampl: expand flow_balance['p3'];
subject to flow_balance['p3']:
	-0.94*x['p2','p3'] + x['p3','p4'] + x['p3','c4'] + 0.025*x['c2','p3'] = 0;

One thing I notice here is that there's a mu[j,i] value that is negative. In your model file, you say that "if one unit leaves i, mu[i,j] units arrive" but negative mu values would need to have a somewhat different interpretation.

--
Robert Fourer
am...@googlegroups.com

{#HS:1813835865-109071#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/5db05876-1baa-4391-a9a1-30004604e2a1n%40googlegroups.com.