3
$\begingroup$

I am trying to model a MIP for a Capacitated Facility Location problem in a way that a number of selected candidate locations will always be there. How can I model it?

My approach:

Add a cost parameter which will be 0 for the selected candidate locations and it will take some values (depending on the problem) for all the other candidate locations. This will gravitate the model towards having the desired candidate locations in the solutions but it might not scale properly.

Improve this question
$\endgroup$
5
  • 7
    $\begingroup$ Why not add constraints $x_i = 1, \forall i \in \{candidates~that~should~be~opened\}$. $\endgroup$
    – Penghui Guo
    Nov 4, 2022 at 12:19
  • $\begingroup$ Yes, I think the other solutions are overthinking it... As long as there are big M constraints and no other constraints that would make the problem infeasible $\endgroup$
    – Ralph Asher
    Nov 5, 2022 at 3:21
  • $\begingroup$ @PenghuiGuo the solution provided by Sutanu is the same as yours, no? $\endgroup$
    – Shibaprasadb
    Nov 7, 2022 at 4:37
  • $\begingroup$ @Shibaprasadb If you want certain number of facility to be opened, use Shibaprasadb's; If you want certain set of facilities to be opened, use mine. $\endgroup$
    – Penghui Guo
    Nov 7, 2022 at 9:30
  • $\begingroup$ @PenghuiGuo Thanks. I used your solution but in some instances, it is not giving me the proper answer. Like one or more desired facilities are not getting selected. Any idea why that may happen? I am coding in R with the ompr package. $\endgroup$
    – Shibaprasadb
    Nov 14, 2022 at 9:04

2 Answers 2

Reset to default
5
$\begingroup$

I assume that you have some sort of "solver" for solving a capacitated facility location problem, which you want to utilize.

If you need a specific facility, say facility $\tilde{i}$, to be open, it may not be enough to set the opening cost for that facility to zero, as you may still have $x_{\tilde{i}}=0$ in an optimal solution. What you can do is to add a dummy customer $j'$ with an assignment cost of $c_{\tilde{i}j'}=0$ and a demand of $d_{j'}=0$. The remaining assignment costs should be $c_{ij'}=\infty$ for all other facilities. Given assignment constraints requiring to assign all customers, this will force the facility $\tilde{i}$ to be open in any optimal solution.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. Yes, I am using symphony in R. One doubt about this approach: The infinity and the 0 conditions, wouldn't that force the model to have only those set of facility locations? $\endgroup$
    – Shibaprasadb
    Nov 14, 2022 at 10:29
  • 1
    $\begingroup$ @Shibaprasadb No, it might still be cheaper to open another facility and and service all customers from that, than from the set of facilities you want to open. But if you want to solve a "facility location" problem, where you have decided on the facilities beforehand, you are not really solving a facility location problem. Then you are solving some kind of allocation/assignment/transportation problem instead $\endgroup$
    – Sune
    Nov 14, 2022 at 12:39
3
$\begingroup$

$\sum{x_i} = N$
where N is desired number of locations and x is binary, i is index of candidates

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ I suspect $\sum_i x_i \ge N$ would be more appropriate. $\endgroup$
    – prubin ♦
    Nov 4, 2022 at 15:45
  • 1
    $\begingroup$ @prubin depends on the context of the problem, i guess $\endgroup$
    – overboxed
    Nov 5, 2022 at 3:23
  • $\begingroup$ A bit confused here, how will the >= and = differ? @overboxed $\endgroup$
    – Shibaprasadb
    Nov 8, 2022 at 6:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.