3
$\begingroup$

I have an MILP model, say $$ \begin{array}{rl} \mbox{minimize} &f_1(x) + f_2(x)\\ \mbox{subject to} &x\in X \end{array} $$ which is hard to solve. And I find it simple to solve the two problems below ($i=1,2$) $$ \begin{array}{rl} \mbox{minimize} &f_i(x)\\ \mbox{subject to} &x\in X \end{array} $$ Let's say the optimal objective value is $LB_1$ and $LB_2$, respectively. Then $LB_1+LB_2$ becomes a lower bound of the original problem. I find that in my case, the final relaxation bound of the original problem within the timelimit seems always worse than my bound, but that doesn't mean my bound can help solve the problem. The only way I think I can do to utilize it is something like $$ \begin{array}{rl} \mbox{minimize} &f_1(x) + f_2(x)\\ \mbox{subject to} &x\in X\\ &f_1(x) \geq LB_1\\ &f_2(x) \geq LB_2 \end{array} $$ But that neither helps find better feasible solution (unpredictable I think?) nor further increase the objective of relaxed problem to a higher bound.

Does that mean this bound is useless to this model (other than improving the gap, which could be done posterior anyway)?

Edit: Maybe I should provide some more information about the model.

The variable $x$ is like a permutation matrix for sorting, or variables in assignment problem. It gives out a sequence like "ABBAABA", and $f_i(x)$'s are some complex functions to evaluate the sequence, with some more (integer or continuous) variables and constraints which is not shown above.

Differents evaluation standards conflict with each other. The bound above describes how good it could be if there is no conflicts.

Feasible solutions are easy to find for the solver (although I don't know how good they really are), but the bound is hard to improve. So the main concern for me is to improve the bound, or 'to prove there must be conflicts'.

Thanks for all your answers and advices, and I think decomposition methods is what I should try.

$\endgroup$
7
  • 1
    $\begingroup$ For problems with this structure, you might consider Lagrangian decomposition: minimize $f_1(x_1)+f_2(x_2)$ subject to $x_1 \in X, x_2 \in X, x_1 = x_2$. You would relax the $x_1=x_2$ constraints. $\endgroup$
    – RobPratt
    Jul 30 at 14:19
  • $\begingroup$ @RobPratt I've tried the Lagrangian decomposition method. I noticed my bound is the optimal value of the relaxation problem when dual variables are all 0s. Further it seems 0 is also the optimal solution of dual variables. I've tried with some different model parameters, and the conclusion is all the same. Is that possible or am i doing it wrong? $\endgroup$
    – xd y
    Aug 5 at 9:51
  • $\begingroup$ How did you implement Lagrangian decomposition? $\endgroup$
    – RobPratt
    Aug 5 at 12:49
  • $\begingroup$ Actually I have more than 2 objective functions, so my relaxed problem is $\min\{ \sum_i f_i(x_i) + v_i^T(x_i-y) \mid x_i\in X, y\in X\}$. I take $(x_i - y)$ as a subgradient of $v_i$ and perform 0.618 method for line search. $v_i$ is not constrained since they are equality constraints. When I start from $v_i=0$, the step of line search is always 0, and if I start from a random point, it seems to work fine. $\endgroup$
    – xd y
    Aug 6 at 1:59
  • $\begingroup$ And the functions $f_i$ are not linear, they are realized with some auxiliary variables and constraints. $\endgroup$
    – xd y
    Aug 6 at 2:01
2
$\begingroup$

There are different approaches to solve MILP problems since you didn't mention what kind of solver you are using i assume you mean in context of branch and bound solver.

Feasible solutions are found using a feasibility pump which tries to guess a low feasible solution.The feasibility pump could be positively affected by those additional constraints as a part of the relaxation is cut. However you also grew the size of constraint matrix which could make all the linear algebra slower.

About the bounds of the relaxations i want to note that if your objective is linear (as MILP suggests) the solver can derive this additive structure of the sub-objectives itself. If the MILP algorithm authors found that this strategy gives benefits they could have added such functionality internally and chosen along which variables to split based on information that became available at solve time. What you are accomplishing with precalculating those bounds on the partial objective beforehand is that you make the presolver and the root node aware of this information. However this information is more worthless than you might think initially if the variables that go into $f_1$ and $f_2$ interact as it the partial configurations that lead to $LB_1$ and $LB_2$ might be incompatible with regard to the constraints to lead to both. However a constraint of the type:

$$f_1(x) + f_2(x) \geq LB_1 + LB_2$$

might help the solver when a solution $f_1(x) + f_2(x) = LB_1 + LB_2$ is found, as it is be able to stop at this moment while without this information it might explore some more regions whose relaxation goes lower.

Summary

Unless you have good reason to suspect that your arbitrary division into $f_1$ and $f_2$ reveals the minimum of the hard problem to be $LB_1 + LB_2$ i wouldn't give the solver this information as to a linear solver this separability is obvious and it could decide to exploit it if it is sufficiently clever.

$\endgroup$
2
$\begingroup$

My overall experience is that feeding constraints of the form $\rm objval \geq lb$ is detrimental to MIP solver performance.

The main reason is the following:

  • MIP solvers rely on branch-and-bound algorithms...
  • ... whose performance depends heavily on branching decisions...
  • ... which are themselves based on how the dual (lower if you're minimizing) bound changes after branching

Therefore, adding a constraint of the form $\rm objval \geq lb$ creates two main issues:

  • the solver looses access to a lot of information on how the objective value changes when branching on particular variables. Branching decisions then become more or less random, which can be terrible for performance
  • constraint also creates a lot of degeneracy in the underlying LPs that are solved at every node, which can further slow down the solution of each node. This also affects the cut generation and heuristics. More precisely:
    • without the constraint $\rm objval \geq lb$, you can discriminate between LP solutions based on their objective value
    • with the constraint $\rm objval \geq lb$, you loose that distinction (at least for all LP solution whose original objective value was smaller than $\rm lb$). Thus, the obtained solution will be pretty much a random guess between all these now-equivalent LP solutions ---> that's usually not a good thing.

So what's the best way of exploiting that lower bound of yours? That'll require a deeper interaction with the solution process.

  • As mentioned in a previous comment, you can use a Lagrange decomposition approach, which however requires you to implement a few things yourself.
  • If you know your bound $\rm lb$ is really good, you can query the current MIP solution, manually compute its optimality gap w.r.t $\rm lb$, and terminate the solve if it fits your needs.
$\endgroup$
1
  • $\begingroup$ Thank you. I believe my bound is not good enough to be the "meeting point", so maybe I should try decomposition methods. $\endgroup$
    – xd y
    Aug 3 at 7:26
1
$\begingroup$

I'm not aware of any solver that can exploit a lower bound to a minimization problem. (An upper bound can be used to prune the search tree, assuming you are using branch-and-bound/branch-and-cut.) CPLEX, for instance, will let you supply the lower bound via the LowerCutoff parameter, but it only uses that information in a maximization problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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