7
$\begingroup$

Suppose a MILP model includes the following constraint:

$ \begin{gather*} B_{1} + B_{2} + B_{3} \le 100 \end{gather*} $, where $B_{1},B_{2},B_{3}$ are nonnegative reals.

Suppose that

$\begin{gather*} (B_{1},B_{2},B_{3}) = (10,30,60) \\ (B_{1},B_{2},B_{3}) = (20,60,20)\\ (B_{1},B_{2},B_{3}) = (80,10,10) \\ (B_{1},B_{2},B_{3}) = (60,10,10) \\ \cdots \end{gather*} $

are optimal solution vectors.

Is there a way to tell the solver to prefer one of these solution vectors over the others? For example, is it possible to formulate a constraint that tells the solver to prefer an optimal solution with increasing values (if it exists?)?

Edit

I think I need to clarify the purpose of the approach I am looking for. The purpose is not really to find a "preferred" solution but to help the B&B to get faster to the optimal solution by cutting off solutions that have the same value as the "preferred". So I don't want to determine all alternative solutions and then choose one, I want to get as fast as possible to a solution.

Adding constraints $B_{1} \le B_{2} \le B_{3} ... $ would help if I knew that there exists an optimal solution that satisfies these constraints, but I don't know this.

$\endgroup$
2
  • 1
    $\begingroup$ This might not be the best way, but you could solve it first with no preference instructions provided. Then solve a feasibility problem consisting of the original constraints, plus the constraint that the objective value is at least as good as original, plus constraints $B_i \le B_{I+1}$. If this new problem is feasible, it will return a preferred solution, and if not feasible, it is not possible to get preferred solution without degrading optimal objective value. $\endgroup$ Commented Apr 28, 2020 at 14:48
  • 1
    $\begingroup$ If these constraints you mentioned should be added to the model when a new incumbent solution has been found, you would try using user-cut or lazy-cut to define them. Many of the modern solvers have such capability. Is it what you you are looking for? $\endgroup$
    – A.Omidi
    Commented Apr 29, 2020 at 0:22

2 Answers 2

4
$\begingroup$

An alternative to @Mark L. Stone's comment would be to define new variables $\delta_i \in \{0,1\}$ and add the following constraints: $$ B_i \le B_{i+1} + M \delta_i\quad \forall i $$ and then penalize the activation of $\delta_i$ in the objective function by adding a term such as $\sum_{i}\omega_i \delta_i$. In your example, $M:=100$ is suitable.

This way, if there exists a solution with increasing values of $B_i$, it will be returned, with $\delta_i =0$. Otherwise, the constraint is deactivated, at the expense of a penalty.

Note however that this approach may disrupt your initial objective function, you will have to choose proper weights $\omega_i$ for variables $\delta_i$.

$\endgroup$
2
$\begingroup$

The following is solver-specific. CPLEX has a "solution pool" feature. By setting certain parameters, you can tell CPLEX to accumulate many or possibly all optimal solutions. Once CPLEX has terminated, you can scan through the optimal solutions using code you wrote that picks the solution you most prefer. I don't which, if any, other solvers have a solution pool feature.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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