Hello, Now I have a question about a formulation and want to seek for help.

For a facility location problem, I have come up with several constraints. The decision variable \(y\) is binary. But it cannot be automatically guaranteed to take on binary values, if relaxed.

The problem is described as: a network has \(n\) customers and \(m\) facilities. Due to uncertain supply, each customer has to be assigned to these facilities level by level in increasing distance. For example, customer \(i\) may be assigned to facility \(j\) on level \(r\), assigned to facility \(k\) on level \(r+1\), in this way, \(y_{ijr} = y_{ik,r+1}=1\), and the distance \(d_{ij} < d_{ik}\). Or we can set parameter \(a_{ijk}=1\).

Without capacity component, some constraints are as follows:

\(\sum\limits_{j}{y_{ijr}}=1 \forall i,r\) each customer has to be served in each level.

\(\sum\limits_{r}{y_{ijr}} \leq 1 \forall i,j\) a facility cannot be assigned more than one level

\(y_{ijr} + y_{ik,r+1} \leq 1 + a_{ijk} \forall i,j,k,r\) the closer facility should be assigned on the lower level.

But with these constraints, in the solver output, fractional solutions of \(y\) can often be obtained. For example, \(y_{010} = y_{011} = y_{020} = y_{021} = 0.5\), which is not I want. If define \(y\) to be binary in CPLEX or GUROBI, binary values can be always guaranteed using B&C, but it is really time consuming.

Without introduce a penalty into the objective function (since it will affect my original objective function), how can we reformulate these constraints to guarantee the integrity of variables \(y\)? Not introduce other binary variables and big \(M\), if possible.

Thank you for your help.

asked 02 May '15, 17:13

linyuan198996's gravatar image

accept rate: 0%

edited 04 May '15, 09:13

I am also faced up with this issue in my research. Hope that I can be inspired by the help and suggestions here. Thanks.

(02 May '15, 17:23) LinYuan

Is there a capacity component to the problem?

(03 May '15, 07:44) Leo

@Leo, No, there is no capacity component. Another constraint is that, if facility \(j\) is open, then \(x_j = 1\), so we should have \(y_{ijr} \leq x_j\) and \(\sum\limits_j{x_j} = p\). So any thing we can do to ensure the binary values of \(y\)? Thank you.

(03 May '15, 09:16) linyuan198996

If you use a solver for Mixed Integer Programming and define the variables as binary, the result will be 0 or 1 always.

Gurobi and CPLEX have this ability and also some open source solvers.

If you want to solve your problem by only handling LPs in the solver, you have to use or implement your own Branch-And-Bound scheme (which will probably be much slower).


answered 04 May '15, 04:37

JF%20Meier's gravatar image

JF Meier
accept rate: 11%

edited 04 May '15, 07:56

@JF Meier, Thanks for your comments. Yes, if I use CPLEX or Gurobi, and define the variables \(y\) as binary, the solver will use B&B or B&C and gives me an integer solution. But since my problem is big, I want to relax \(y\) to be continuous, but the integrity can be always guranteed by the solver. How can I achive this, by adding some redundancy constraints or something? Thank you.

(04 May '15, 08:55) linyuan198996

In my opinion, this rarely makes sense. Of course, you can try to strengthen the formulation by additional inequalities or fix variables that can be preprocessed, but in general, it is no advantage in facility location to relax variables if you cannot guarantee them to be integral. I think you look at the wrong place for performance improvement.

(04 May '15, 10:37) JF Meier

@JF Meier, I mean, can we add some other constraints to gurantee the integrity of \(y\)? Or charge a penalty in the objective to pull it down or up? So that we donnot need to branch on \(y\). So in your oppinon, if we cannot do this, we should leave \(y\) as binary, and use B&C technique? Thank you.

(04 May '15, 11:13) linyuan198996

That is exactly what I think. It may be useful to think about strengthening inequalities but I doubt that they are strong enough to avoid B&C completely.

(05 May '15, 07:42) JF Meier

Linear relaxations may always give non-integer solutions, unless the constraint matrix is totally unimodular and you use the simplex method. By using branch&bound techniques or cutting plane methods, which require you to solve a series of linear programs, you end up with an optimal integer solution.


answered 04 May '15, 07:48

optimizer's gravatar image

accept rate: 6%

@optimizer, Thanks for your help. The first two constraints matrix with respect to \(y\) is totally unimodular, then the fracation may due to the third constraint. This is a set-packing type. Can we strength or reformulate this constraint, adding maximal clique inequality? Thank you and I really appreciate your help. I want to fix this.

(04 May '15, 09:00) linyuan198996
Your answer
toggle preview

Follow this question

By Email:

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



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



Asked: 02 May '15, 17:13

Seen: 610 times

Last updated: 05 May '15, 07:42

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