6
$\begingroup$

I have seen some papers claiming that their proposed model is integer-friendly. I would like to get more information about what type of constraints we can call integer-friendly.

Probably, it can be better understood if I have some examples. Here is part of a model in the context of location covering:

\begin{align}&z= \max\sum_i v_i \\\text{s.t}\quad&v_i \geq c_{ij}x_{ij},\quad \forall i \in N, j \in M\tag1\\\quad&v_i \geq 0\\\quad&x_{ij} \in \{0,1\}.\end{align}

where $c_{ij}$ are some positive non-integer constants. My question is:

  • Why constraint set (1) is NOT integer-friendly, and how can I improve this constraint?

  • If I define the $x_{ij}$ variables to be continuous in $[0, 1]$, they will be always 0 or 1. Does it help to some extent?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Don't know if there's a definition per se, but for any constraint that consists of solely integer variables, it is highly beneficial for all the coefficients to be integral as well, because that allows us to easily apply integer cuts.

If the coefficients are not naturally integral, we can impose that by applying GCD rounding.

In this example, you have a mixed-binary constraint, which is not very good. Assuming all your coefficients and constants are integral, you can use an integer variable instead, or, more commonly, an integer cut.

Improve this answer
$\endgroup$
2
  • $\begingroup$ thanks @NikosKazazakis. So I sould add that the coefficients in my model are not integers. $\endgroup$
    – Mostafa
    Commented May 26, 2020 at 12:25
  • $\begingroup$ @Mostafa You can always transform the constraint to have integer coeffs by applying a GCD rounding. $\endgroup$
    – Nikos Kazazakis
    Commented May 26, 2020 at 12:28
2
$\begingroup$

In (1): "The SPLP formulation of Balinski(2) has been characterized as integer friendly because of the frequency of direct 0,1 solutions, and because the amount of branching and bounding to resolve fractional solutions is often minimal (see ReVelle, 1993(3))". Unfortunately, I don't have access to the paper that is mentioned in the above paragraph but I give the references below.

(1) Brimberg, Jack, and Charles ReVelle. "Solving the plant location problem on a line by linear programming." Top 6.2 (1998): 277-286.

(2) Balinski, M. (1965). Integer programming: methods, uses, computation. Management Science, 12, 254-313

(3) ReVelle, Charles. "Facility siting and integer-friendly programming." European Journal of Operational Research 65.2 (1993): 147-158.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.