Need for Creation of a new type of variable in the CBC Solver (Bucket Variable)

[SanTanBan]

I earnestly request you to kindly guide me regarding the process of creating a new type of variable in the CBC Solver.

I have been requesting repeatedly for the introduction of a new variable which is necessary for me to show proof of something new which I have stumbled upon regarding a novel( possibly much faster) way of solving a specific type of problems.

This is presently possible using multiple Binary variables but I wish to use a novel method.
The concept of this new variable (which I shall hence refer to as Bucket Variables) is similar to the Binary Variables.
Binary Variables take only 0 and 1
Bucket Variables will take its values from among any value provided by the user, i.e. it may take values from [3,6,9] or from [0,1] as well. (This may also be extended to float; but I am in extreme need of integer Buckets only.)

I shall be extremely grateful to you.

[svigerske]

You can use Cbc's lotsize object for this: https://github.com/coin-or/Cbc/blob/master/examples/lotsize.cpp

[SanTanBan]

I presently require a variable to only use certain specific integer values.

I am not going to use solvers that convert such variable into binary variables (cvxpy/cvxpy#1740 (comment)) which would defeat the computational purpose itself.

I was advised to look at the CoinModel class here: https://github.com/coin-or/CoinUtils/blob/master/src/CoinModel.hpp to input the problem directly via the C++ API, but am not making head or tails of this since I am not conversant with C++.

I am interested to take any help available. and it would be great if we can collaborate for the specific update to the code in the case of integer values as you suggested above (since your "simple" means a few years for me).

I think we could also collaborate with the

1. PuLP: How to make PuLP take numbers from a predefined bucket? pulp#499 (reply in thread)
2. CVXPY: Finite sets cvxpy/cvxpy#1740 (comment)
3. Gurobi: https://support.gurobi.com/hc/en-us/community/posts/9160893511185/comments/9315790699281
   communities to include this form of variable creation....

[SanTanBan]

I got a reply from Stefan regarding input from LP files since MPS file creation is possibly very cumbersome. I was referred to the CoinModel class: https://github.com/coin-or/CoinUtils/blob/master/src/CoinModel.hpp to input the problem. I am conversant with Python but C++ is absolutely foreign to me. I, therefore, am getting stuck and confused multiple times. In case PuLP would have been able to access this feature of Lotsize/Bucket variables, I could have implemented my code in a day.

However, due to this not being the case, I humbly request your help in developing the simplest program to incorporate a novelty and test whether this would actually be something beneficial. I have ideated to test this on the Sudoku problem but need to use the Coin-OR Lotsize variables for this case. Due to this, the formulation which I would be considering is greatly reduced (81 Lotsize variables and 27 constraints for the 9x9 Sudoku, instead of 729 binary variables and 324 constraints). I wish to test this, especially for large Sudoku (upto ~1000x1000) problems to report the difference in speeds for the fastest existing Sudoku solution technique.

A year before I thought this would be a weekend affair and I would be able to complete a paper reporting possible improvement in solution time using my new technique. However I have not been able to do implement this and am looking collaboration. This will also help test and improve the Lotsize variables further as indicated by you.

[jjhforrest]

To examine performance and improve/debug lotsizing variables, I suggest the following.
It is easy to output an .lp file from pulp and I presume it is simple to write out a file with a simple format. So model with variables as general integer variables and create an .lp file. Also provide a file where each line is name,n1,n2,n3.... where name is the name of the integer variable and n1,.. are the values the variable can take.

I have created an example cpp file in master/Cbc/examples called lotsize2.cpp (it should also work with stable). To see if it works you can compile that and solve a modified version of the miplib3 problem bell5 by --- lotsize2 bell5.mps bell5.lot -preprocess off -solve.

bell5.lot is a file giving lotsizing information (also in examples). preprocess off is probably not needed but safer for now.

You should be able to compile and run that simple program. If you have problems, you can send me the .lp file and lotsizing information file. If it works, i can see what can be put into pulp.

[SanTanBan]

I was able to make CBC solve the basic lotsize problem (with the 0-1 variables to be interchanged into lotsize variables; present in the original lotsize example)

However when I tried to use my problem parameters there, I was unable to do so. I concluded that maybe it is because of my lotsize specification. (In the example provided, all Binary Variables were being replaced by a range of continuous or discrete values within [0,1] interval. However my problem requirement is outside this range.

Therefore I considered your new example implementation of the lotsize variables. I created .lp, .mps and the .lot files as directed by you. I was able to generate this by formulating my problem in Gurobi with the Lotsize variables as general Integers (as per your comment above). There seems to be something wrong within the code itself and I am unable to run this (it may be a C++ configuration issue and my novice knowledge of C++).

I have all the requisite files ready and would be highly grateful if you can help as you have suggested. I have shared a GitHub repository (https://github.com/SanTanBan/Sudoku) and am eagerly awaiting your response.

[jjhforrest]

Will look at it sometime over next few weeks

[jhmgoossens]

@SanTanBan the repo link to Sudoku seems to be broken.

[SanTanBan]

Since the repo is now public...

[jjhforrest]

I don't understand the formulation. Valid values of the variables seem to be 0,1,3,7,15 etc but if I set x_1_4 in size 3 to 7 the problem is infeasible - just as an lp without lotsizing.

[SanTanBan]

For this answer, I have to give everything out, and since I was unable to implement my understanding as yet, I feel this would be cooler:

Presently we are using binary variables for representing every layer of the Sudoku Grids by making layers for each of the values it may take...

To prevent this from happening, i.e. to make the problem more compact, I developed an extension of the Binary Variables so that we may be able to write A+B+C=D and get unique A, B, C (given for a specific set of variable values)

Reducing this, a Binary is A + B =D (where each of the variable values are 0 or 1)

Extending this the series is as you mentioned. However, I cannot find the reason for your mention of infeasibility...

Regarding the Filtering:-
I am initially creating full Sudoku problems (solved containing all values).
Then randomly Filtering these to remove some values (with some probability of removal ranging from 0.3 to 0.7).
These filtered Sudoku are then used as the input problems for the LP.

In this case SET1 is one such Filtered Set of Input. (1 original Sudoku can thus be filtered to generate multiple SET of inputs)

[jjhforrest]

As I said in previous comment, I don't really understand what filtering means as all variables seem to be in. I think it sensible to try and get a simple formulation working - so I have uploaded sudoku3.cpp. This would be compiled from a Cbc/examples directory.
sudoku3 sudoku_sample.csv will solve a 9x9 sudoku in two ways - first by all different cuts and then by lotsizing. The lotsizing code could be much improved, but it is interesting. With standard lotsizing (in debug mode) I get
All different 108 rows, 810 columns took 0.2137758.2 seconds
Lot sizing 27 rows, 81 columns took 2.1942938.2 seconds
If I use a modified lotsizing (included in sudoku3) the time goes down to 0.66 and there is much more that could be done.
As you can see the lotsizing version is as compact as possible - but not necessarily best.

If I solve a more difficult 9x9 one I get
All different 108 rows, 810 columns took 2.8024158.2 seconds
Lot sizing 27 rows, 81 columns took 1417.2666988.2 seconds

[SanTanBan]

The idea is very simple & I explain part of the Linear Programming formulation:

Just like we presently use two values to depict two distinct states using Binary Variables; what should be the possible extension for such a case of 3 states?

In case we just add another value of 2; making the variable take the Integer values of {0,1,2}; this would not be a problem except that we would need to intelligently constraint that this variable should take only values from among a specific set of values in an unique manner distributing the states uniformly.

Say if we have 3 variables (x_1,x_2, x_3) which need to have three of these distinct states; a simplest linear constraint might be tough to find (?).
So, x_1+x_2+x_3=(0+1+2)=3  does not work only because 1,1,1 would be a solution. 

I was able to solve this problem by understanding that in case of developing complex formulations, simpler formulation could be developed by integrating this idea of the constraint to find the specific number sequence. In this case a sequence of 0,1,3 works:

x_1+x_2+x_3= (0+1+3) =4

would always make the variables take one of the individual states distinctively, i.e. provided the variables take up the values of only 0,1,3 (thus providing a start to extend the Binary Variables).

I have previously read somewhere that for the exact same problem, the smaller the problem size (in terms of describing the problem in terms of equations and exact storage units) the better. Through this new formulation, I was able to formulate this Sudoku into a much more compact form. However, the Coin-OR CBC runtime outcome seems unsatisfactory as this was beaten by the All Different constraint in Constraint Satisfaction.

I therefore request opinions on whether:

1) There is any possibility of improving the runtime using other methods

2. Can this idea help in improving the way "All Different" works?

Some peculiarities & insights of the sequence can be seen:-

1. This successful formulation (beaten due to some higher runtimes) seems to give me an understanding of discrete mathematics. Just like how using Linear programming, some the the Real Numbers can never be encountered as solutions (Transcendental); we can encode some of our constraint requirements into a number sequence and try to find whether this would help in decreasing runtime(?)

2. The sequence itself is also equivalent to:
           1
         10
       100
     1000
   10000
   and so on. Adding the same number to all these would make no change. We can also use these numbers from different bases and to keep their sizes the smallest, I used the smallest base of 2 to obtain the present sequence (0,1,3,...)

[jjhforrest]

One major flaw is that if a variable is fixed say to 31, this can not easily influence other variables. The most you can say is that another variable must be between 0 and 15 OR 63 and ... There is no easy cut to do that. You could try branching on smallest values first (and down) so that is a variable was 0 then other variables could have their lower bounds changed to 1 etc. This would mean having CbcLotsizeBranchingObjectAlt inheriting from Cbc....Object and writing specific code.

I have written an example sudoku3.cpp (and the coding is far too hurried) which solves sudoku by all different, lotsizing and brute force backtracking. For a 9x9 sudoku

All different 108 rows, 810 columns took 0.1800 seconds
Lot sizing 27 rows, 81 columns took 0.0033 seconds
and backtracking was timed at 0.0 seconds

but for a 16x16 one
All different 304 rows, 4352 columns took 1.3524 seconds
Lot sizing 48 rows, 256 columns took 147635.9266 seconds (stopped with no solution)
Backtracking algorithm took 145.4324 seconds