How do I approach this optimization problem?

Question

I'm a software dev that's pretty new to OR and want to solve a specific problem I came across at my job. From what I've researched it is a variation of resource-constrained assignment problem, but with variety of those problems it's quite hard for me to confirm.

I have n jobs that need to be assigned to m production facilities:

1. only some of those facilities are viable locations for producing
2. some (but not all) products are stock constrained
3. cost of producing those is variable and depends on number of jobs assigned to that location (edit: for 1-10 items unit cost would \$10, for 10-100 \$9 etc. and it would differ between production houses)
4. number of jobs assigned should be between min-max for that location (but might be exceeded either way if no feasible solution found).

There are multiple objectives depending on other factors, but I should be able to get it down to a single number by using weights.

I've found different papers that deal with RCAP, but what I struggle to understand is how to incorporate constraint 3 into any LP model or any other of those solutions. Additionally in "Model Building in Mathematical Programming" I've read that LP is not that good for those kinds of problems as it multiplies variables very fast and specialized algorithms work better, but I struggle to find one that fits my needs.

Is local search options a better solution for real-world application? I've looked into OptaPlanner, but it seems like a too-good-to-be-true solution and I'd rather explore all different options before committing to one. What approaches/problems/tools would you suggest I read up on?

In my case, I'd need to deal with up to 100 production houses and up to 10000 orders.

Answer 1

Your cost structure is known as an "economy of scale", and would convert your linear program into an integer linear program as follows. Let's say your cost breakpoints are $a_1 < a_2 < \dots < a_n$ with $a_{n+1}$ the upper limit on production. For instance, in your example you would have $a_1=1,$ $a_2=10,$ $a_3=100$ and so on. Let $c_i$ be the unit cost if production volume $x$ is between $a_i$ and $a_{i+1}.$ You can introduce binary variables $y_1,\dots,y_n$ with the constraint $$y_1 + \dots + y_n=1,$$ where $y_i=1$ if $a_i \le x \le a_{i+1}.$ We enforce that definition with the constraints $$x\ge a_1 y_1 + \dots + a_n y_n$$ and $$x \le a_2 y_1 + \dots + a_{n_1} y_n.$$ Your total production cost $z$ is then defined by $$z \ge c_i x - M(1-y_i) \quad i=1,\dots,n$$ where $M=c_1 a_{n+1}$ is an upper bound on production cost. (We could tighten that a bit if solver performance was a problem.) Note that this relies on the assumption that lower cost is better (i.e., you do not work for the federal government).

Quality IP solvers are routinely used with success for these types of problems. An alternative might be constraint programming (CP). Some CP solvers are designed specifically to handle machine scheduling (and perhaps lot-sizing) problems.

Answer 2

For constraint #3, assuming cost of production should have some basis like unit cost per order/job/facility and if you want to use a constraint around it, then it's like
$C = \sum_f \sum _{j} c_j \cdot O_{j,f}$ where $c_{j,f}$ is unit cost per job, j per facility, f and $O_{j,f}$ is volume of orders.

If multiple price points like p1=10 (1-10), p2=9 (11-100)..pN depending upon volume of orders and N is largest index of price points then

$9 - O_{j,f} \le U \cdot x_{0,f}$
$O_{j,f} - 10 \le U \cdot x_{1,j} \quad \forall \ j \in\ $jobs and $\forall \ f \in\ $Facilities where $x_1 \in\ \{0,1\}$ and $U \gt O$: upper bound of order volume
Similarly, $O_{j,f} - 100 \le U \cdot x_{2,j}$

Also, $\sum_i x_{i,j} = 1$ where $0 \le i \le N \quad \forall j \in\ $jobs.

$c_{j,f} = \sum_i x_{i,j} \cdot p_i \quad \forall \ j,f \in\ $job, facilities

Depending upon linearity of other constraints and objectives, LP or NLP solver will be able to solve it without worrying about algorithms but some solvers do provide option to choose algorithms like branch-cut/branch-bound-price or interior points etc. and parameters like tolerances/optimality gap etc.
Local search is advisable if global optimum is taking longer than allowed and is generally the case for multi-variate non-convex objectives.