1
$\begingroup$

I'm trying to solve optimization problems of the form: $\min\{cx|Ax\preceq b,\;x\geq 0\}$, where $\preceq$ means lexicographic order; that is, the set of linear inequalities need only to be satisfied lexicographically. I'm guessing these inequalities are treated conditionally by means of binary variables thus transforming the problem into a mixed integer linear program. I'm also aware of the more direct approach, which is solving a sequence of linear programs, starting with $\min\{cx|A_{1}x\leq b_{1},\;x\geq 0\}$ and continuing with linear programs of the form $\min\{cx|A_{i}x=b_{i},\;A_{k}x\leq b_{k},\;1\leq i<k,\;x\geq 0\}$ whenever the inequality constraint at $k-1$ is satisfied in strict equality.

I'm interested in a solution by means of binary variables if there is any, or any other approach. Thanks in advance for your help.

$\endgroup$
  • 1
    $\begingroup$ What's wrong with solving the sequence of linear programs? Solving the sequence of linear programs is likely to be better than anything using MILP. If you must code it with binary variables, see cs.stackexchange.com/q/67163/755 and cs.stackexchange.com/q/51025/755, but you'll probably needs bounds on $A_ix$ to apply those techniques. $\endgroup$ – D.W. Sep 21 '17 at 16:15
  • $\begingroup$ There's nothing wrong with solving a sequence of linear programs. It should be definitely better than the MILP approach, but I really need the MILP formulation since I will then try to solve $\min\{cx|A^{1}x\{\preceq\text{or}\succeq\} b^{1},A^{2}x\{\preceq\text{or}\succeq\} b^{2},\ldots,A^{l}x\{\preceq\text{or}\succeq\} b^{l},\;x\geq 0\}$; which, I believe, cannot be solved sequentially. Maybe I should have asked about this problem initially, but I found it unnecessary once I have the MILP formulation of the former. $\endgroup$ – P-Cañedo Sep 21 '17 at 16:57
2
$\begingroup$

If you want to have only initial constraints to be strictly equal and rest of them should be strictly less

First, add regular constraints: $$ A_i x \le b_i $$ Next, add checks for equality as in https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ : $$ e_i = A_i x \stackrel{?}{=} b_i $$ Finally, we want only some initial of these variable to be true, and for that we can use material implication as in https://blog.adamfurmanek.pl/2015/08/22/ilp-part-1/ : $$ e_{i+1} \implies e_i = 1 $$ or we can simply add the following constraints: $$ e_{i+1} \le e_i $$

Disclaimer: I am the author of the blog posts but I don't want to advertise here, only include them as a reference.

If you want some initial of the constraints to be strictly equal, the next one should be strictly less, and rest of them can be not satisfied

Do not add any regular constraints.

Create equality constraints as before: $$ e_i = A_i x \stackrel{?}{=} b_i $$

Calculate prefix conjunction of equality constraints: $$ E_i = e_1 \wedge e_2 \wedge \ldots \wedge e_{i} $$

Variables $E_i$ indicates whether first $i$ constraints are strictly equal.

Next, calculate less than constraints: $$ l_i = A_i x \stackrel{?}{<} b_i $$

Finally, make sure that after $i$ initial strictly equal constraints there is a strictly less constraint or another strictly equal constraint satisfied: $$ E_i \implies \left( l_{i+1} \vee E_{i+1} \right) = 1 $$

$\endgroup$
  • $\begingroup$ Can you write out how you will implement the "check for equality" as ILP constraints? Does it require bounds on the values of $A_ix$ (that they can't be too large or too small)? Naively, it seems like it will. I already mentioned that approach in my comment, but as I mentioned, the problem is that it requires us to bound the value of $A_ix$... and the question doesn't promise any bounds on it. $\endgroup$ – D.W. Oct 23 '17 at 6:23
  • $\begingroup$ See the linked post for details. Yes, it requires bounds, but since you are probably going to solve this using computer and floats, you are constrained anyway, either by floating precision or by other numerical representation (such as MPS format). $\endgroup$ – user1543037 Oct 23 '17 at 9:22
  • $\begingroup$ If you use as your upper bound the largest number representable in floating point format, the constant $M$ (called $K$ in your post) will be so huge that I suspect ILP solvers may have a difficult time solving the problem. Not sure whether this is going to work in practice or not... $\endgroup$ – D.W. Oct 23 '17 at 13:56
  • $\begingroup$ I checked all operations described on my blog with CPLEX, Gurobi, SCIP and LpSolve. Gurobi and CPLEX have no problems with comparison operations with $K$ around $2^{28}$, which is a maximum value meeting technical requirements and still fitting into typical integer variable. I didn't check value near boundary of IEEE754 float/double though, but I would worry more about numeric precision and not time to be honest, e.g., LpSolve makes a lot of errors even when working on 32-bit integer numbers. $\endgroup$ – user1543037 Oct 23 '17 at 15:39
  • $\begingroup$ user1543037 and @D.W. thanks for your answer and comments. But I think approach of user1543037 does not guarantee that constraints are satisfied lexicographically or at least it does not solve my problem. To be clear, If we suppose that $Ax\prec_{lex} b$, then we have $1\leq i\leq n$ so that $A_{j}x=b_{j}$ holds for $j<i$ and $Ax_{i}<b_{i}$; there a possibility open for $A_{k}x\geq b_{k}$ for $i<k\leq n$. This is not the case if we write the regular constraint $A_{i}x\leq b_{i}$ for all $i$ as you suggested. $\endgroup$ – P-Cañedo Oct 23 '17 at 19:03
0
$\begingroup$

One possible solution aside from solving the sequence of linear programs could be solving the following MILP, in which $\epsilon$ is a very small positive number and $M$ a big one: $$ \min cx\\ \text{s.t.}\quad Ax+s=b\\ \epsilon y_{1}\leq s_{1}\leq My_{1}\\ -M y_{1}+\epsilon y_{2}\leq s_{2}\leq M y_{2}\\ \vdots\\ -M (y_{1}+y_{2}+...+y_{m-1})+\epsilon y_{m}\leq s_{m}\leq M y_{m}\\ y_{1},y_{2},\ldots,y_{m}\in \{0,1\}\\ x\geq 0 $$ As I said in the above comment. This allows to solve the more general problem $\min\{cx|A^{1}x\{\preceq \text{or}\succeq\}b^{1},A^{2}x\{\preceq \text{or}\succeq\}b^{2},…,A^{l}\{\preceq \text{or}\succeq\}b^{l},x\geq0\}$; which, I believe, cannot be solved sequentially. Nevertheless, I have not been able to test it exhaustively, so if anyone can spot errors or maybe find a better way, I would be very grateful.

$\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.