ILP Part 83 — Concatenation – Random IT Utensils

This is the eightieth third part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve Dolepki. We have some natural number $n$ for which we know that a sum of an arithmetic progression $1+2+\ldots+n$ is equal to $1x153$ (concatenated $1$ , $x$ , and $153$ ). Let’s solve it with ILP.

var x = solver.CreateAnonymous(Domain.PositiveOrZeroInteger);

var sum = x.Operation<Multiplication>(x.Operation<Addition>(solver.FromConstant(1))).Operation<Division>(solver.FromConstant(2));

var extendedX = x.Operation<Multiplication>(solver.FromConstant(1000)).Operation<Addition>(solver.FromConstant(153));
List<IVariable> conjunctions = new List<IVariable>();

for (int t = 1; t <= 1e7; t *= 10)
{
	var c = solver.FromConstant(t).Operation<IsLessOrEqual>(extendedX)
		.Operation<Conjunction>(solver.FromConstant(t * 10).Operation<IsGreaterOrEqual>(extendedX));
	conjunctions.Add(c);
	c.Operation<MaterialImplication>(solver.FromConstant(t * 10).Operation<Addition>(extendedX).Operation<IsEqual>(sum))
	.Set<Equal>(solver.FromConstant(1));
}

solver.Operation<Addition>(conjunctions.ToArray()).Set<Equal>(solver.FromConstant(1));

solver.AddGoal("goal", solver.FromConstant(0));
solver.Solve();

Console.WriteLine(solver.GetValue(x));

var x = solver.CreateAnonymous(Domain.PositiveOrZeroInteger);

var sum = x.Operation<Multiplication>(x.Operation<Addition>(solver.FromConstant(1))).Operation<Division>(solver.FromConstant(2));

var extendedX = x.Operation<Multiplication>(solver.FromConstant(1000)).Operation<Addition>(solver.FromConstant(153));

List<IVariable> conjunctions = new List<IVariable>();

for (int t = 1; t <= 1e7; t *= 10)

{

var c = solver.FromConstant(t).Operation<IsLessOrEqual>(extendedX)

.Operation<Conjunction>(solver.FromConstant(t * 10).Operation<IsGreaterOrEqual>(extendedX));

conjunctions.Add(c);

c.Operation<MaterialImplication>(solver.FromConstant(t * 10).Operation<Addition>(extendedX).Operation<IsEqual>(sum))

.Set<Equal>(solver.FromConstant(1));

}

solver.Operation<Addition>(conjunctions.ToArray()).Set<Equal>(solver.FromConstant(1));

solver.AddGoal("goal", solver.FromConstant(0));

solver.Solve();

Console.WriteLine(solver.GetValue(x));

Should be pretty straightforward. First, we calculate the sum of progression by using well known formula. Next, we calculate extendedX which is a helper variable with concatenated $x$ and $153$ . Finally, we generate consecutive powers of ten and use the one greater than the $x$ . We use material implication to perform the “if” condition.

CPLEX output:

Tried aggregator 2 times.
MIP Presolve eliminated 146 rows and 45 columns.
MIP Presolve modified 666 coefficients.
Aggregator did 172 substitutions.
Reduced MIP has 474 rows, 268 columns, and 1438 nonzeros.
Reduced MIP has 203 binaries, 65 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (3.98 ticks)
Probing fixed 125 vars, tightened 443 bounds.
Probing changed sense of 15 constraints.
Probing time = 0.02 sec. (3.23 ticks)
Cover probing fixed 0 vars, tightened 206 bounds.
Tried aggregator 3 times.
MIP Presolve eliminated 321 rows and 196 columns.
MIP Presolve modified 209 coefficients.
Aggregator did 29 substitutions.
Reduced MIP has 124 rows, 43 columns, and 365 nonzeros.
Reduced MIP has 13 binaries, 30 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (1.37 ticks)
Probing time = 0.00 sec. (0.14 ticks)
Tried aggregator 2 times.
Aggregator did 1 substitutions.
Reduced MIP has 123 rows, 42 columns, and 363 nonzeros.
Reduced MIP has 13 binaries, 29 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.00 sec. (0.38 ticks)
Probing time = 0.00 sec. (0.13 ticks)
Clique table members: 1.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec. (0.54 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

      0     0        0.0000    18                      0.0000       52         
      0     0        0.0000    18                  MIRcuts: 2       67         
      0     2        0.0000    18                      0.0000       67         
Elapsed time = 0.06 sec. (18.10 ticks, tree = 0.00 MB, solutions = 0)

Mixed integer rounding cuts applied:  1

Root node processing (before b&c):
  Real time             =    0.06 sec. (18.09 ticks)
Sequential b&c:
  Real time             =    0.00 sec. (0.55 ticks)
                          ------------
Total (root+branch&cut) =    0.06 sec. (18.63 ticks)
ILOG.CPLEX.CpxException: CPLEX Error  1217: No solution exists.

Tried aggregator 2 times.

MIP Presolve eliminated 146 rows and 45 columns.

MIP Presolve modified 666 coefficients.

Aggregator did 172 substitutions.

Reduced MIP has 474 rows, 268 columns, and 1438 nonzeros.

Reduced MIP has 203 binaries, 65 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.02 sec. (3.98 ticks)

Probing fixed 125 vars, tightened 443 bounds.

Probing changed sense of 15 constraints.

Probing time = 0.02 sec. (3.23 ticks)

Cover probing fixed 0 vars, tightened 206 bounds.

Tried aggregator 3 times.

MIP Presolve eliminated 321 rows and 196 columns.

MIP Presolve modified 209 coefficients.

Aggregator did 29 substitutions.

Reduced MIP has 124 rows, 43 columns, and 365 nonzeros.

Reduced MIP has 13 binaries, 30 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (1.37 ticks)

Probing time = 0.00 sec. (0.14 ticks)

Tried aggregator 2 times.

Aggregator did 1 substitutions.

Reduced MIP has 123 rows, 42 columns, and 363 nonzeros.

Reduced MIP has 13 binaries, 29 generals, 0 SOSs, and 0 indicators.

Presolve time = 0.00 sec. (0.38 ticks)

Probing time = 0.00 sec. (0.13 ticks)

Clique table members: 1.

MIP emphasis: balance optimality and feasibility.

MIP search method: dynamic search.

Parallel mode: none, using 1 thread.

Root relaxation solution time = 0.00 sec. (0.54 ticks)

Nodes Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

0 0 0.0000 18 0.0000 52

0 0 0.0000 18 MIRcuts: 2 67

0 2 0.0000 18 0.0000 67

Elapsed time = 0.06 sec. (18.10 ticks, tree = 0.00 MB, solutions = 0)

Mixed integer rounding cuts applied: 1

Root node processing (before b&c):

Real time = 0.06 sec. (18.09 ticks)

Sequential b&c:

Real time = 0.00 sec. (0.55 ticks)

------------

Total (root+branch&cut) = 0.06 sec. (18.63 ticks)

ILOG.CPLEX.CpxException: CPLEX Error 1217: No solution exists.

That’s remarkable. It’s one of the problems where CPLEX fails to find a solution even though it’s there. However, we can try MIPCL:

Start preprocessing: Rows - 3345, Cols - 3345 (Int - 2424, Bin - 716), NZs - 6788
==================================== Probing =====================================
     Time  Round  Probed vars  Fixed vars  Mod. entries  New var bds  Implications
    0.120      1          303          89           487         1042           444
    0.170      2          214          38           284          363           246
    0.177      3          176          80           254          514           339
    0.195      4           96          26           184          276            42
    0.202      5           70          14           166          176             5
    0.204      6           56          56           333          153            13
==================================================================================
After preprocessing: Rows - 0, Cols - 0 (Int - 0, Bin - 0), NZs - 0
Preprocessing Time: 0.204
===========================================
MIPCL version 2.5.4
Solution time: 0.204
Branch-and-Cut nodes: 1
5582
Objective value: 0.0000 - optimality proven

Start preprocessing: Rows - 3345, Cols - 3345 (Int - 2424, Bin - 716), NZs - 6788

==================================== Probing =====================================

Time Round Probed vars Fixed vars Mod. entries New var bds Implications

0.120 1 303 89 487 1042 444

0.170 2 214 38 284 363 246

0.177 3 176 80 254 514 339

0.195 4 96 26 184 276 42

0.202 5 70 14 166 176 5

0.204 6 56 56 333 153 13

==================================================================================

After preprocessing: Rows - 0, Cols - 0 (Int - 0, Bin - 0), NZs - 0

Preprocessing Time: 0.204

===========================================

MIPCL version 2.5.4

Solution time: 0.204

Branch-and-Cut nodes: 1

5582

Objective value: 0.0000 - optimality proven

MIPCL succeeded.