Passing Initial Solution

[Nicholas Howard]

I've formulated a large Integer Program, and I already have a 'decent' solution in hand that I want to pass to CBC as a initial start point for all of the integer variables.

How do I do this?  Can I set just the integer decision variables, or do I need to set everything to pass an initial solution?

Thanks.

-Nick

[Stuart Mitchell]

Sorry at the moment there is no way to pass the initial solution to cbc (which pulp calls through its command line interface)

Both the gurobi and cplex solvers allow you to access the underlying solver representation of the model so you can use these to pass an intial solution.

Stu

--
You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discu...@googlegroups.com.
To post to this group, send email to pulp-or...@googlegroups.com.
Visit this group at http://groups.google.com/group/pulp-or-discuss.
For more options, visit https://groups.google.com/groups/opt_out.

--

Stuart Mitchell

PhD Engineering Science

Extraordinary Freelance Programmer and Optimisation Guru

www.stuartmitchell.com

[Nicholas Howard]

Is there an open source MIP solver that will allow me to pass an initial solution?

[Stuart Mitchell]

There is no reason why YAPOSIB should not support it (and YAPOSIB is supported by pulp) but I can't seem to find it in the documentation. 

http://yaposib.readthedocs.org/en/latest/index.html

Stu

[Nicholas Howard]

It appears that YAPOSIB is not currently supported on Windows.

 

Do you know if GLPK supports passing an initial solution?

[Stuart Mitchell]

Sorry for the late reply, I don't think you can not even with the python binding.

However, I sometimes find that if is just as useful to set the initial solution objective value as a constraint on the MIP objective, then it is to actually provide an initial solution.

i.e

z_0 = initial solution objective

so set z <= z_0 in the MIP before you solve it.

Stu

[Romain Montagné]

Hello Stu,

I have been the approach you propose (set z <= z_0 in the MIP before you solve it) but about 50% of the time, it increases the solution time and number of nodes in the branching tree.

Is there any explanation of why this happens?

Thanks

[Stuart Mitchell]

Mip can be hard perhaps set it it 1-10% below the initial value.

For more options, visit https://groups.google.com/d/optout.

[Bernhard Leder]

Hello,

I just discovered this topic and think it could concern a problem I am currently having. 

Some posts above it was mentioned that it is possible to pass an initial solution to gurobi using pulp and therefore I got curious. 

My situation: 

I am currently solving two MIPs (MIP1, MIP2) using pulp and the gurobi solver considering 2 objectiv functions (lets call them OF1 and OF2).

First, I solve the MIP1 problem for OF1, which works pretty fast.

Second, I use the OF1.value of the obtained solution as a RHS value for a hard constraint for the optimization of MIP2 with OF2, but the run time is now really long.

My question:

How do i pass the solution values of the MIP1 solution to the gurobi solver as an initial solution for MIP2 and OF2, so I maybe could get a decent bound faster and eventually a shorter run time?

Some research showed me, that if I would use gurobipy instead of pulp, I would be able to generate a .mst-file of the MIP1 solution and pass the values of the variables to gurobi as an initial solution for MIP2 ( f.e. MIP2.read("input.mst")).

But since I already generated the model using pulp I wonder if there is a decent way to pass the solution without rewriting everything. 

Maybe, all this has an obvious answer, but since I am rather new to programming and couldn't find anything fitting so far, I would appreciate any tip I could get. 

I hope that I was able to express my situation and the concerning problem well enough. 

best regards,

Bernhard

[Stuart Mitchell]

Sorry we do not support initial values in pulp.

but you do have full access to the gurobi model from pulp.

Stu

[Joel Cofield]

After much toil and heartache I have made come headway using PuLP/CBC with an initial solution. I am sharing here in case you guys can benefit or help:

1. Since version 2.8.0 of CBC, there is a command line option 'mips' which reads in an initial solution. So first and foremost, you must upgrade
PuLP's version of CBC if it isn't already. I did this by downloading the .tar, following the INSTALL file, then dragging the new cbc.exe file into my pulp solver dir (and renaming it to whatever your old one was)

2. Now you can pass an initial solution as follows:
model.solve(PULP_CBC_CMD(options=['mips','initialSolutionFilePath.sol']))

3. The format of the .sol file is the same format as a cbc solution output. You can see one by running
model.solve(PULP_CBC_CMD(options=['solu','outputPath.sol'])) and viewing the file 'outputPath.sol' in the local directory.
If that gives you an empty file except for "Status Unknown", try:
model.solve(PULP_CBC_CMD(options=['solve',solu','outputPath.sol']))

Now from there, you should be able to just craft a .sol file and provide it as an input. I have seen from CBC terminal log that this CAN actually work:
>>
Welcome to the CBC MILP Solver
Version: 2.9.7
Build Date: Nov 17 2015
opening mipstart file ./initialSolution.sol.
MIPStart values read for 1032 variables.
Continuous objective value is -1720 - 117.10 seconds
Cgl0008I 4753 inequality constraints converted to equality constraints
Cgl0003I 0 fixed, 0 tightened bounds, 9506 strengthened rows, 0 substitutions
Cgl0005I 4753 SOS with 104566 members
Cgl0004I processed model has 16417 rows, 116133 columns (104566 integer (104566 of which binary)) and 577194 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0045I MIPStart provided solution with cost 10866
>>

3. It isn't as easy as it might seem from there. Here are two obstacles:
A. The names of the variables in the .sol file are default X0000000, X0000001, etc... Instead of the variables names you assign in your model.
This only happens from PuLP. When I run in CBC command line, I can generate or use .sol files with variables names

This is an example command in command line CBC that generates a good .sol file (how can we do this via PuLP??):
>>cbc -import aModelThatIsAlreadyCreated.lp -solve -solution testCmdLine.sol -quit

Now testCmdLine will be something like:

Optimal - objective value 0.00000000
     62 x_(64,_100,_0)                              1                       0
    185 x_(89,_100,_1)                              1                       0
    280 x_(86,_100,_10)                             1                       0
    322 x_(100,_128,_11)                            1                       0

To circumvent the variable name issue, I am using a copy of my model to generate a .sol file. I simply run the copy with no objective and force my variables to be my initial solution. Then the output should be the initial solution file I want. Then I turn around and rerun the original model with the new .sol file.

B. I pass what appears to be a valid and feasible .sol file, but CBC sometimes says "WARNING: Not able to make use of the mipstart solution. Ignoring" I have not wrapped my head around this, but if anyone else sees this issue please point it out!

I hope people can benefit from this. Let me know if you have any other suggestions, especially as it pertains to part A.

(P.S. Simply using a cutting constraint with the intitial solution's objective or 95% of it was not satisfactory for me either)

[Khalid Abdulla]

Hi Stu,

First of all I have found the PuLP module incredibly useful, so congratulations on it, and many thanks for developing it.
I was wondering if there's anywhere I could find more details about how to access the full gurobi model from pulp. Like others on this thread I'm trying to set an initial solution.

I have asked a full question on stack overflow (http://stackoverflow.com/questions/40144122/how-to-set-mip-start-initial-solution-with-gurobi-solver-from-pulp) but in essence what I have is to set (assuming 'prob' contains a PuLP LpProblem:

prob.solverModel.getVars()[0].start = someValue

In the hope that this would behave the same as setting the `.start` property of variables in a full gurobi model as indicated here (https://www.gurobi.com/documentation/6.5/examples/mip_starts.html) but it does not work as I expected.

Is there any documentation I could refer to about how to access the full gurobi model via the PuLP interface?

Kind regards,

- Khalid.

[Khalid Abdulla]

Hi Stu (and others interested),

An answer has been posted to my stackoverflow question: http://stackoverflow.com/questions/40144122/how-to-set-mip-start-initial-solution-with-gurobi-solver-from-pulp/40158904#40158904

I think my issue was that I was changing the MIP start of the Gurobi model object, but then calling a solve on the original Pulp LpProblem object. For anyone who's interested in setting MIP starts for the Gurobi solver via the PuLP interface, there is a working example at the stackoverflow post above (you have to make the change pointed out in the accepted answer).

Best regards,

- Khalid.

[Stuart Mitchell]

Great thanks for Sonja Mars from Gurobi for answering that.

The interaction between Pulp and Gurobi is not well documented but if you look at the code in solvers.py you will see that after the model is built the gurobi variables and model are attached to the pulp variables and model.

If you are doing this level of solver specific modelling I would recommend you take the 30minutes or so and convert your pulp model to gurobi proper (the syntax is very similar) and continue from there.

Stu

--

You received this message because you are subscribed to the Google Groups "pulp-or-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to pulp-or-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to pulp-or-discuss@googlegroups.com.
Visit this group at https://groups.google.com/group/pulp-or-discuss.

For more options, visit https://groups.google.com/d/optout.

[Franco Peschiera]

In case anyone is interested I’ve been working on giving initial solutions to solvers in a standardized way. I have it still in my own branch of pulp but at some point it could be incorporated into pulp. It mainly lacks documentation and tests, so incomplete but working. Working for COIN_CMD/ PULP_CBC_CMD and CPLEX_CMD. It should not be too difficult to add GUROBI, I guess.

The link is this one: https://github.com/pchtsp/pulp-or/tree/mip_start

To try it out, you’d have to install it using the following:

pip install https://github.com/pchtsp/pulp-or/archive/mip_start.zip

Mainly,

1. I’ve implemented the existing “setInitialValue” method in variables to edit the value of each variable.
2. I’ve added a binary “mip_start” argument to CPLEX and CBC solvers.

Under the hood, pulp creates the relevant solution file using the values of variables that are not None and gives it to the solver so it can use it.

Additionally, I’ve added a “fixValue” method to variables to edit the bounds to the present value, in case it is not None.

Example:

In this problem, you’d have to add the following changes before solving (after adding constraints):

# Missing here: the rest of the problem definition.

# I've taken the optimal solution from a previous solving. x is the variable dictionary.
solution = {
    ('M', 'N'): 1.0,
    ('E', 'F', 'G'): 1.0,
    ('A', 'B', 'C', 'D'): 1.0,
    ('I', 'J', 'K', 'L'): 1.0,
    ('O', 'P', 'Q', 'R'): 1.0
}
for k, v in solution.items():
    x[k].setInitialValue(v)

seating_model.solve(pulp.PULP_CBC_CMD(msg=1, mip_start=1))  
# seating_model.solve(pulp.CPLEX_CMD(msg=1, mip_start=1)) also works.

Which gives the following (cropped) log:

...
will open mipstart file .\623dde8d3842403f8e97c4989b247afe-pulp_init.sol.
mipstart values read for 3213 variables.
Continuous objective value is 12 - 0.01 seconds
Cgl0004I processed model has 18 rows, 3213 columns (3213 integer (3213 of which binary)) and 15062 elements
Cutoff increment increased from 1e-005 to 0.9999
Cbc0045I mipstart provided solution with cost 12
...

or, for CPLEX:

...
CPLEX> MIP start file 'C:\Users\FRANCO~1.FR\AppData\Local\Temp\c26468d4d5e74923b42ba16635ca5976-pulp.mst' read.
CPLEX> New value for indicator for advanced starting information: 1
CPLEX> 1 of 1 MIP starts provided solutions.
MIP start 'm1' defined initial solution with objective 12.0000.
...

Hope someone finds it useful.

Franco

​