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?

$\endgroup$
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.

$\endgroup$
2
  • $\begingroup$ thanks @NikosKazazakis. So I sould add that the coefficients in my model are not integers. $\endgroup$ – Mostafa May 26 '20 at 12:25
  • $\begingroup$ @Mostafa You can always transform the constraint to have integer coeffs by applying a GCD rounding. $\endgroup$ – Nikos Kazazakis May 26 '20 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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