Imagine I have a bucket containing water with volume v. (The water volume is v, not the size of the bucket)

I have an indexed set of cups 1,...,n with capacities c1,...,cn where c1+...+cn>v

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 xi to be the volume of water contained in cup i, where x1+...+xn=v

I would model this using some binary integer variables ui which denotes the use of cup i, and fi which denotes cup i being full:

  • x1+...+xn=v
  • xi<=uici for i=1,...,n
  • xi>=fici for i=1,...,n
  • ui+1>=fi for i=1,...,n-1
  • fi+1>=fi for i=1,...,n-1

The first constrant says that the total amount of water apportioned to the glasses must equal the starting volume v.

The second constraint says that each glass can hold at most its capacity, and only if the glass is used denoted by ui, otherwise none at all.

The third constraint says that each glass must hold at least its capacity, and only if the glass is full denoted by fi. This constraint together with the previous ensures the glass is exactly full if ui=fi=1.

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 v is actually also a variable involved elsewhere.

Thank you.

asked 20 Oct '16, 20:36

Ozzah's gravatar image

Ozzah
3929
accept rate: 0%


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.

link

answered 21 Oct '16, 10:08

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
accept rate: 28%

edited 25 Oct '16, 19:20

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 \sum_i x_i = v. The two points you mentioned simultaneously requires v = 1/2 * c_1 and v = 3/2 * c_1 which is a contradiction. Actually, there is only one feasible point in the solution space with respect to this subproblem. The binaries and constraints are just an awkward way of representing this within a LP/IP framework.

(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, v is also a variable. I can't share the rest of the model because of IP issues, unfortunately; besides it would be much too large and complex to put here. That's ok. If this subproblem is nonconvex then the simplification is probably quite convoluted and not worth the effort - like I said the preprocessor optimises away the binary variables entirely so solution times are still very reasonable for the resultant LP. Thank you Rob.

(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
Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

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

Tags:

×231
×22

Asked: 20 Oct '16, 20:36

Seen: 800 times

Last updated: 25 Oct '16, 19:20

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