How to construct an LP to achieve roundup in objective function?

Question

Objective: Minimize 500 * Roundup(x/1200) + 1000 * Roundup(y/3200)

Variables: x,y

Constraints: x + y = 8000

Is there a way to construct an LP without breaking the linearity conditions for the problem above?

Answer 1

Using integer variables you can do:

$$\begin{align} \min\> & 500 b_1 + 1000 b_2\\ & b_1 \ge x/1200 \\ & b_2 \ge y/3200 \\ & \text{other constraints}\\ &b_1, b_2 \text{ integer} \\ &x, y \ge 0 \end{align}$$

This is no longer an LP but now a (linear) MIP (Mixed Integer Programming) problem.

Answer 2

Without taking away from the formulation given by Erwin, I'd actually formulate it as follows:

$$\begin{align} \min\> & 500 b_1 + 1000 b_2\\ & 1200 \,b_1 \ge x\\ & 3200 \,b_2 \ge y\\ & x + y = 8000\\ &b_1, b_2 \text{ integer} \\ &x, y \ge 0. \end{align}$$

This formulation can be simplified as follows:

$$\begin{align} \min\> & 500 b_1 + 1000 b_2\\ & 1200 \,b_1 \ge x\\ & 3200 \,b_2 \ge 8000 - x\\ &b_1, b_2 \text{ integer} \\ &0 \le x \le 8000, \end{align}$$

where we remove $y$ from the model by substituting $y=8000-x$. You can now try to find the convex hull of the above MILP to obtain the corresponding Linear Program (LP).