|
Imagine I have a bucket containing water with volume I have an indexed set of cups I have to put all water into the cups. I have to completely fill up cups with smaller indices before I can start filling cups with larger indices. Denote I would model this using some binary integer variables
The first constrant says that the total amount of water apportioned to the glasses must equal the starting volume The second constraint says that each glass can hold at most its capacity, and only if the glass is used denoted by The third constraint says that each glass must hold at least its capacity, and only if the glass is full denoted by The fourth constraint says that a glass can only be used if the previously indexed glass is full. The fifth constraint says that a glass can only be full if the previously indexed glass is also full. Now, aside from any errors I may have made in this question, this method works, and it makes perfect sense to me. But when I use a solver such as XPRESS, CPLEX, or Gurobi, I can see that the solver eliminates the integer variables and ends up with a purely linear formulation. The binary variables aren't true variables. They can only have one possible value in any feasible solution. So in a way, it makes sense that they can be eliminated, but I'm not sure how. Can someone please show me how to model this without any binary or integer variables? This problem is a small part of a larger problem, and Thank you. |
|
The fourth and fifth constraints should be \(\le\) instead of \(\ge\). Also note that the corrected fifth constraint is then redundant: \(f_{i+1} \le x_{i+1}/c_{i+1} \le u_{i+1} \le f_i\). You can also eliminate \(f_i\) by replacing the third and fourth constraints with \(x_i \ge c_i u_{i+1}\). Does the objective function naturally favor filling cups with smaller indices? Update: this portion of the problem is nonconvex. See discussion below. Rob's last point is what I was going to raise. If not, you could try adding a penalty term in the objective for the water volume in each cup, with the penalty for unit volume increasing as the cup index increases. Absent anything in the other constraints favoring higher indexed cups, this would fill the lower index cups first.
(21 Oct '16, 19:52)
Paul Rubin ♦♦
No, actually the objective function usually favours filling the largest indexed cups first in practice, but either way I need a general solution because the costs can be arbitrary.
(22 Oct '16, 21:47)
Ozzah
Paul, like I said this is a small part of a much larger problem. Actually, this is the only integer part of the larger problem. I can't change the objective function. Also, remember I said CPLEX/Gurobi/XPRESS ends up with a 100% linear model after its preprocessing, so there must be a way to model this without binaries, I just don't know how. It would be good if I could somehow see the preprocessed model to try and figure out what magic it has done.
(22 Oct '16, 21:49)
Ozzah
The feasible region is not convex in \(x\), so the presolver must be exploiting other parts of the model that you did not show us. For example, with \(n=2\), consider the line segment joining the feasible points \((x_1,x_2)=(c_1/2,0)\) and \((x_1,x_2)=(c_1,c_1/2)\).
(23 Oct '16, 09:52)
Rob Pratt
Those two points can't both be feasible since we require
(24 Oct '16, 01:15)
Ozzah
Yes, for fixed \(v\), the \(x\) solution is unique. But earlier you said that \(v\) is variable, so I projected it out to make the example simpler. If you prefer, take the two points to be \((x_1,x_2,v)=(c_1/2,0,c_1/2)\) and \((x_1,x_2,v)=(c_1,c_1/2,3c_1/2)\). Can you please share the full model and data?
(24 Oct '16, 09:17)
Rob Pratt
Yes, you're right,
(24 Oct '16, 17:58)
Ozzah
Rob, please update the answer to say that it is otherwise nonconvex and I will mark it as accepted.
(25 Oct '16, 19:11)
Ozzah
showing 5 of 8
show 3 more comments
|
