4
$\begingroup$

I am trying to solve this ILP with all binary variables:

$$\min \sum_{1\leq i<j\leq n-1-h} t_{i,j}$$ $$\sum_{i=1}^{n-1-h} a_{k,i} = \lfloor (n-1)/2\rfloor \qquad \text{for }k\in[h];$$ $$a_{k,i} + a_{k,j} \leq 2 d_{k,i,j}\qquad \text{for }1\leq i<j\leq n-1-h,\ k\in[h];$$ $$\sum_{k=1}^h d_{k,i,j} \leq h - 1 + t_{i,j}\quad \text{for }1\leq i<j\leq n-1-h$$

thanks to an answer to my problem here, for $n=53$ and $h=13$. If I compute the minimum in the original problem by means of many random cases I have a minimum value of $113$, therefore the actual minimum will be less or equal than that.

I am using the free program LPSolve IDE 5.5.2.11 and the full problem for my $n=53$ and $h=13$ case is here (too long to copy within the question). I have encoded multiple variable indexes in one unique integer index for the software model.

There are 10387 constraints and 10881 variables.

The partial result after a couple of minutes was this:

Model name:  'LPSolver' - run #1
Objective:   Minimize(R0)

SUBMITTED
Model size:    10387 constraints,   10881 variables,        39780 non-zeros.
Sets:                                   0 GUB,                  0 SOS.

Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2.
The primal and dual simplex pricing strategy set to 'Devex'.

Relaxed solution                   0 after      10774 iter is B&B base.

Feasible solution                320 after      22515 iter,      7838 nodes (gap 32000.0%)
Improved solution                319 after      23350 iter,      8716 nodes (gap 31900.0%)
Improved solution                318 after      24221 iter,      9633 nodes (gap 31800.0%)
Improved solution                317 after      25192 iter,     10569 nodes (gap 31700.0%)
Improved solution                316 after      26182 iter,     11556 nodes (gap 31600.0%)
Improved solution                315 after      27604 iter,     12611 nodes (gap 31500.0%)
Improved solution                314 after      28657 iter,     13614 nodes (gap 31400.0%)
Improved solution                313 after      29865 iter,     14645 nodes (gap 31300.0%)

Now the software has done about 4,000,000 iterations in about two hours without further progress.

I have very little knowledge of linear programming, so I am asking:

Is it possible to make that ILP problem faster by modifying it, use another software or change solver parameters?

Can we say anything about the expected completion time?

$\endgroup$
8
  • $\begingroup$ You might want to explain that all variables are binary (according to the linked answer). Also, your Pastebin link is currently not working (either private or awaiting moderation). $\endgroup$
    – prubin
    Nov 18, 2022 at 20:27
  • $\begingroup$ I emphasized now that all variables are binary. The link to the problem is now public. Now 2 hours without improvements. $\endgroup$ Nov 18, 2022 at 21:24
  • 1
    $\begingroup$ I think lpSolve was designed as a tool for teaching how to design a solver. Not as a tool for use in production. So using another solver could be your best choice. $\endgroup$ Nov 19, 2022 at 14:45
  • 1
    $\begingroup$ @prubin The formulation doesn’t enforce it, but if two rows are identical, they cover the same column pairs and you can replace one of the duplicate rows arbitrarily without hurting the objective value. $\endgroup$
    – RobPratt
    Nov 19, 2022 at 16:57
  • 1
    $\begingroup$ LpSolve is not a strong solver. You can submit MIP problems to state-of-the-art solvers using neos-server.org/neos. $\endgroup$ Nov 19, 2022 at 17:01

2 Answers 2

4
$\begingroup$

Is it possible to make that ILP problem faster by modifying it, use another software or change solver parameters?

Using other software: Definitely, as Rob Pratt's answer indicates. (I got an incumbent solution with value 67 in about 30 seconds with CPLEX, after which progress stalled.)

Changing solver parameters: This depends to some extent on the solver (different solvers have different parameters). For example, I set the "MIP emphasis" parameter in CPLEX to 5 (heavy emphasis on heuristics) to encourage it to get a "good" solution quickly.

Modifying the model: This is the tricky part. One problem with your model is that it has a "weak" formulation, meaning that relaxing integrality and solving it as an LP produces an answer with a very low objective value (0).* I tried switching the MIP emphasis in CPLEX to improvement of the lower bound, but after five minutes (the limit of my patience) the lower bound was still 0. So a stronger (tighter) formulation would definitely help ... if you could find one.

An obvious weakness is the constraint $a_{k,i} + a_{k,j} \leq 2 d_{k,i,j},$ which is presumably intended to say that $d_{k,i,j}$ must be 1 if either $a_{k,i}$ or $a_{k,j}$ is 1. You can get the same restriction using two constraints ($a_{k,i}\le d_{k,i,j}$ and $a_{k,j} \le d_{k,i,j}$ at the cost of a modest increase in model size. Using separate constraints is somewhat stronger. For instance, if in an LP relaxation the solver sets $a_{k,i}=1$ and $a_{k,j}=0,$ the revised formulation forces $d_{k,i,j}=1$ whereas the original formulation only forces $d_{k,i,j}=0.5.$ Unfortunately, in my tests, that change did not accomplish anything useful by itself.

Another issue with the model is symmetry. Branch and bound solvers can bog down when equivalent solutions exist in multiple branches of the search tree. In your case, permuting the rows of the $A$ matrix in any solution produces another solution with identical objective value.

Can we say anything about the expected completion time?

You will get a provable optimum within your lifetime ... if you are immortal (and assuming your computer does not run out of power or memory). Seriously, predicting solution times for integer programs is somewhere between impossible and not even that easy.

* Unless the actual optimal value is 0, in which case the problem is not a weak formulation but rather difficulty improving the primal bound (best feasible solution).

$\endgroup$
5
  • $\begingroup$ Thank you. Splitting $a_{k,i} + a_{k,j} \leq 2 d_{k,i,j}$ didn't help with LPSolve. I will try to use another one. $\endgroup$ Nov 18, 2022 at 23:39
  • $\begingroup$ You can also try relaxing $t_{i,j}$ to be nonnegative. If you disaggregate the second constraint, you can also relax $d_{k,i,j}$ to be nonnegative. $\endgroup$
    – RobPratt
    Nov 18, 2022 at 23:58
  • $\begingroup$ If relaxing integrality on $t,$ you need to keep the upper bound of 1. That's not important when relaxing $d.$ $\endgroup$
    – prubin
    Nov 19, 2022 at 4:20
  • $\begingroup$ No value of $t$ greater than $1$ would be optimal because reducing it to $1$ preserves feasibility and improves the objective. $\endgroup$
    – RobPratt
    Nov 19, 2022 at 5:16
  • $\begingroup$ My bad. I thought the sum on the left could be bigger than $h$ -- misread the limit of summation. $\endgroup$
    – prubin
    Nov 19, 2022 at 14:29
5
$\begingroup$

Here are the $a_{k,i}$ values for a feasible solution with objective value $61$, obtained in a few minutes with a different solver. Please verify.

1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 
1 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 0 0 0 
1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 
0 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 
1 1 1 1 1 0 1 0 0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 1 
1 1 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 0 0 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 
0 1 0 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 0 1 0 0 0 1 1 
0 1 1 0 1 1 0 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 1 
1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 1 1 1 1 
0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 
1 1 0 1 0 0 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 
0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 
1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 0 1 1 1 1 0 0 0 1 1 0 1 0 

Here's a better solution with objective value $57$, obtained by relaxing the first constraint from $=$ to $\ge$. Each row still has exactly $26$ ones.

1 1 0 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1
1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 1 1
0 1 1 0 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0
1 0 1 1 1 1 0 0 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 0 1 0
1 0 0 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 0 1
1 1 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1
1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 1 0
0 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 0 1
1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1
1 0 1 1 1 1 1 0 0 1 0 1 1 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 1 0
1 0 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1
0 1 0 0 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

The minimum is $0$:

1 1 0 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 1 
0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 
1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 0 1 0 1 1 0 
1 0 1 0 1 0 1 0 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 
1 1 1 1 1 1 0 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 
1 1 1 0 0 1 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 0 1 1 1 
1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 1 0 
1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 0 
1 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 
0 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 0 0 1 1 0 0 
0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 1 1 
1 0 1 1 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 
0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 

By focusing on the locations of the zeros, you can interpret a solution with objective value $0$ as a $(39,13,2)$-covering design with $13$ blocks, like the one found here: https://ljcr.dmgordon.org/show_cover.php?v=39&k=13&t=2

$\endgroup$
4
  • $\begingroup$ Verified thank you very much. By the way it could be that the minimum in the linked original problem is always $f(n) = 61$ for $n \ge 23$. $\endgroup$ Nov 18, 2022 at 23:37
  • $\begingroup$ Oh well, $57$ then, thank you. $\endgroup$ Nov 19, 2022 at 0:09
  • $\begingroup$ I suspected overnight that it might be $0$. I will need to add more constraints to the original problem. How long did it take to get $0$? $\endgroup$ Nov 19, 2022 at 7:55
  • 1
    $\begingroup$ To find that $0$ solution took only a few minutes via a MILP local search that starts with a feasible solution and modifies only two rows at a time. $\endgroup$
    – RobPratt
    Nov 19, 2022 at 13:26

Your Answer

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

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