Initial Feasible Solution

[Nic Woyak]

The MIP problem I'm trying to solve is quite large and would normally be very time consuming to solve. When using a solver like CPLEX it can spend quite a bit of time just looking for a feasible solution before even starting to work towards optimizing the objective. The problem does have a nice structure so for any instance I can pretty easily find a feasible solution. Is there a way to give the solver this initial feasible solution and sort of guide the process? Would such a thing actually be useful? 

[Victor Zverovich]

This question has already been answered here: https://groups.google.com/d/msg/ampl/YkkZ-mO-GXs/zt8Kam1f5RMJ

HTH,

Victor

On Thu, Jul 7, 2016 at 12:13 PM Nic Woyak <nichola...@gmail.com> wrote:

The MIP problem I'm trying to solve is quite large and would normally be very time consuming to solve. When using a solver like CPLEX it can spend quite a bit of time just looking for a feasible solution before even starting to work towards optimizing the objective. The problem does have a nice structure so for any instance I can pretty easily find a feasible solution. Is there a way to give the solver this initial feasible solution and sort of guide the process? Would such a thing actually be useful? 

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[Nic Woyak]

I've gotten the assigning of an initial feasible solution to work so that it displays back to me and the solver recognizes that there is something to start with. When I go to solve though, sometimes the solver seems to discard the solution. For small instances it works fine, but for large ones it almost never takes. What are some reasons this might happen?

[Victor Zverovich]

What makes you think that the solver discards the solution? Is there any specific part of the solver output that suggests that?

- Victor

[Nic Woyak]

I have several reasons. The output as it begins doing cuts and branch and bound and so forth is identical to when it is started without a solution. Additionally, the column that reports the best objective starts blank as it would from a start without a solution, rather than with the objective of the given initial feasible solution. Solve time is the same for it, with and without a solution.

As I said for the smaller instances it seems to use the solution and it shows in the output as well as a decrease in the solve time.

[Robert Fourer]

Normally if CPLEX is sent a starting solution that is not feasible, it will display a message (when mipdisplay=2 is included in the cplex_options string) like

Retaining values of one MIP start for possible repair.

Can you post your CPLEX output starting from "CPLEX 12.6.3.0: ..." and continuing to the point where branching begins (as specified by a positive value in the Node column)? An example where the initial solution is used and one where it is not used would be helpful for comparison. Maybe that will suggest some further ideas.

Also if you have not done so already, it is a good idea, after assigning initial values for the variables, to check in AMPL with commands like

display {i in 1.._ncons: _con[i].slack < -1e-6} (_conname[i],_con[i].slack);
display {j in 1.._nvars: _var[j].slack < -1e-6} (_varname[j],_var[j].slack);

to confirm that there are no infeasibilities greater than the tolerance specified (1e-6 in this example).

Bob Fourer
am...@googlegroups.com

=======

[Nic Woyak]

Thanks for the insight Bob. I don't have an example at the moment, but I've noticed something that might help. I am using two different formulations for my problem, one with a 2 index decision variable and one with a 3 index decision variable. My questions to this point have been in reference to the 2 index form. Since I posted earlier, I was able to get a large instance to accept the initial feasible solution in the 3 index variable form.

The scripts I've made to generate these initial feasible solutions only explicitly say what the decision variables are. For the 3 index form, this is a complete or what CPLEX calls "m1" solution. For the 2 index form, there are some indicator variables that aren't explicitly assigned a value. Is there some level of completeness an initial solution has to have to be utilized? If that's the case, then maybe for the small instances just providing the decision variables reaches this level, while for the large instances it doesn't. 

At this point I will probably just try to write a script that also gives me the value of those indicator variables so the 2 index form's initial solution is also complete, but I'm still interested in figuring out this quirk in case something like this comes up in the future. Thanks again.

[Robert Fourer]

If you set values for only some of the variables, the rest will be seen be seen by CPLEX as having a default value of zero. Thus CPLEX will see an infeasible starting solution. CPLEX will try to fix that into a feasible solution, but there is no guarantee that it will succeed; and as you have seen, there may be success with some problem instances but not with others.

Unfortunately it is not possible to be more specific as to what level of completeness is needed in the initial solution. IBM does not publish the details of the heuristics that preprocess a problem and that try to build an initial feasible solution; and even if we knew the details, these heuristic routines are too complex to predict how they will interact with different instances and different settings of variable values. In some cases you might determine by experimentation the level of completeness needed in the initial solution, but the only really reliable approach is to give an initial solution that is explicitly feasible.