# Tag Info

13

First of all, I would say that "fast solvable in practice" is possible also when your remaining problem still is NP-hard. But since you ask specifically for polytime solvability, there are some cases. Most well-known is probably "TU-ness" of your matrix. When you solve a MIP $$\min\{c^tx \mid Ax\geq b, x\in Z^n\times Q^q\}$$ then you will obtain an integer ...

9

Presumably you have binary decision variables like $x_{ik} = 1$ if marble #$i$ is in slot #$k$. Then you can write a constraint like $$x_{ik} \le 1 - x_{jl} \qquad \forall \text{i < j and k > l}$$ In other words, if $i < j$ and $j$ is in slot $l$, then $i$ cannot be in any slot $k$ that comes after $l$.

9

The big-M values need not be the same. You should choose $M_1$ in $(1)$ to be a small upper bound on $q$ and $M_2$ in $(2)$ to be a small upper bound on $p$. An alternative formulation is $p q = 0$, but that is nonlinear. If your solver supports indicator constraints, you can write the desired implications directly, without specifying big-M: \begin{align} y ...

8

@Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form: $$\lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \omega_i) \ge 1 \\ \sum_{i=1}^n \omega_i \le n-1 \\$$

8

How about $$\omega_1 + \cdots + \omega_n \le n-1$$ This way, at most all variables but one of them can take value $1$ simultaneously. In the context of knapsack problems, if each variable models the selection of a given item and that the sum of the weights of the items exceed the knapsack capacity, these inequalities are called cover inequalities.

7

Answers to the linked question mention both big-M constraints and semicontinuous variables. To speed up the big-M approach, you might consider introducing the constraints dynamically only as they are violated ("row generation" or "cut generation"). Explicitly: Omit all big-M constraints and the associated binary variables. Solve the ...

6

If I understand correctly, the following enforces your desired behavior: \begin{align} y_1 &= d_1 \\ y_2 &= d_2 \\ y_3 &= d_3 \\ y_4 &\ge d_1 + d_2 - 1\\ y_5 &\ge d_1 + d_2 + d_3 - 2\\ \end{align} If you also want to enforce $y_4 \implies (d_1 \land d_2)$ and $y_5 \implies (d_1 \land d_2 \land d_3)$, then include these additional ...

6

@user3680510 gave the correct answer in a comment. Here's a way to derive it via conjunctive normal form: $$i \not= j \\ (i \implies \lnot j) \land (\lnot i \implies j) \\ (\lnot i \lor \lnot j) \land (i \lor j) \\ (1 - i + 1 - j \ge 1) \land (i + j \ge 1) \\ (i + j \le 1) \land (i + j \ge 1) \\ i + j = 1$$ To prevent both to be 1 at the same time: $$\... 6 For simplicity, I will omit the i and j subscripts. Rewriting your logical proposition in conjunctive normal form somewhat automatically yields two linear constraints: z_3 \implies (\neg z_1 \land \neg z_2) \\ \neg z_3 \lor (\neg z_1 \land \neg z_2) \\ (\neg z_3 \lor \neg z_1) \land (\neg z_3 \lor \neg z_2) \\ ((1- z_3) + (1- z_1) \ge 1) ... 6 How about z_{i,j,1} + z_{i,j,2} \leq 2 \cdot (1 - z_{i,j,3}) \quad \forall i,j ? For more context, I refer you to this excellent self-answer by user D.W. on CS.SX, which includes a link to a helpful gallery of such common "building blocks", all with practical examples stated in prose. 5 Does x_i \ge x_{i+1} do what you want? 5 Provide the standard citation for YALMIP @inproceedings{Lofberg2004, address = {Taipei, Taiwan}, author = {L{\"{o}}fberg, J.}, booktitle = {In Proceedings of the CACSD Conference}, title = {YALMIP : A Toolbox for Modeling and Optimization in MATLAB}, year = {2004} } which is shown at https://yalmip.github.io/reference/lofberg2004/ Then perhaps you can ... 5 As per the answer by @LarrySnyder610, we can use position-based variable x_{ik} to model such scenarios. Note that we also need the following constraints to ensure that each i is assigned to exactly one position k:$$ \sum_{k}x_{ik}=1 ~~~~~~~~ \forall i $$If n is the total number of possible i or k, then this method requires \mathcal{O}(n^4) ... 4 Consider the following tiny example. You have two factories, one warehouse and two product. Factory 1 can produce both goods in sufficient quantity to meet demand but has a very large cost coefficient. Factory 2 only produces the second product, with adequate capacity and a small cost coefficient. The optimal solution to the original problem is to ship ... 4 Suppose we know an upper bound M for y such that |y| \leq M, we can linearize this constraint as follows. First, we introduce a new variable h \in \mathbb{R} with h = b y. Then we need to model that h equals y if b = 1 and equals 0 if b = 0. For this purpose we add the following linear constraints:$$ \begin{align} h &\leq b M \tag{1} ...

4

If I understand correctly, you can obtain the desired linear constraints via conjunctive normal form. Explicitly, suppose $f(\bar{x}_1,\dots,\bar{x}_n)=1$, and let $S_0 = \{j\in\{1,\dots,n\}:\bar{x}_j = 0\}$ and $S_1 = \{j\in\{1,\dots,n\}:\bar{x}_j = 1\}$. You want to enforce $$\left[\left(\bigwedge_{j\in S_0} \lnot x_j\right) \bigwedge \left(\bigwedge_{j\... 4 The big-M constraint z \le M t does enforce z > 0 \implies t = 1, equivalently its contrapositive t = 0 \implies z = 0, but not the converse$$z = 0 \implies t = 0. \tag1$$To enforce (1), consider its contrapositive$$t = 1 \implies z > 0 \tag2,$$which you can enforce via big-M constraint$$\epsilon - z \le (\epsilon - 0)(1 - t),$$... 4 Many state-of-art real-world large-scale combinatorial optimization problems are based on heuristics that use some sort of local search in them. Although not stated directly as a QUBO, many of these local search moves are based on solving a QUBO (with no "tricks" of penalizing the constraints). For example in the Travelling Salesman Problem, the ... 3 An alternative approach to binary variables or semicontinuous variables is the following cubic polynomial inequality:$$x(x-L_B)(U_B-x)\ge 0$$Because x \ge 0, this constraint enforces$$(x = 0) \lor (x - L_B \ge 0 \land U_B - x \ge 0),$$as desired. The case (x - L_B \le 0 \land U_B - x \le 0) is prevented by L_B < U_B. After further consideration,... 3 Introduce a variable y_{i,j} to represent$$\left|\sum_k k x_{i,j,k}-\sum_k k x_{i,j-1,k}\right|,together with constraints \begin{align} y_{i,j} &\ge \sum_k k x_{i,j,k}-\sum_k k x_{i,j-1,k} &&\text{for all i and j} \\ y_{i,j} &\ge -\sum_k k x_{i,j,k}+\sum_k k x_{i,j-1,k} &&\text{for all i and j} \end{align} The objective ... 3 In order to query the GRB_DoubleAttr_UnbdRay attribute, you need to optimize the problem with the InfUnbdInfo parameter set to 1. 3 To enforce x = 1 \implies y = 1 for binary variables x and y, impose linear constraint x \le y. You can derive this constraint via conjunctive normal form: x \implies y \\ \lnot x \lor y \\ (1 - x) + y \ge 1 \\ x \le y $$3 You can use conjunctive normal form to derive the desired constraints. The first one is:$$a \ge b \implies a\ge c\\ (b \implies a) \implies (c \implies a)\\ \lnot(\lnot b \lor a) \lor (\lnot c \lor a)\\ (b \land \lnot a) \lor (\lnot c \lor a)\\ (b \lor \lnot c \lor a) \land (\lnot a \lor \lnot c \lor a)\\ (b \lor \lnot c \lor a)\\ b+ 1- c +a \ge 1\\ a+b \...

3

You are not going to be able to add these logs and quadratic terms to the model via simple double-sided big-M constraints, as they generate non-convex use of convex quadratics and logs, and CVX does not support that. The use of the squared log is not possible either. I don't think it supports automatic modelling of nonconvex use of abs operator either. Most ...

2

Considering you have a set of n variables (elements) $p_1, p_2, …, p_n$ to be sorted in ascending order so that $p_{[1]}, p_{[2]}, …, p_{[n]}$ where $p_{[1]} \leq p_{[2]} \leq …\leq p_{[n]}$, you can introduce $n^2$ binary decision variable $x_{i,j}$ and $n$ variables $A_i$. $x_{i,j}=1$ if $i-th$ element is assigned to $j-th$ position. $min \left \{ \... 2 I don't know whether this is the reason, but the documentation says that InfUnbdInfo is for LP only. So we might have to work with the LP. Two thoughts: x = 0, u = 0 is a feasible solution for the MIP. As x is bounded, x will not be part of the ray. Thus, any ray for the LP should also be a ray for the MIP. So if Gurobi decides your problem is unbounded, ... 2 Do you mean$i$and$j$instead of$v$and$v’$? If so, the constraints you want are$\alpha_{i,j}\le A_i$and$\alpha_{i,j}\le A_j\$.

2

GLPK is not the best performing MILP solver. Instead, you could give one of the leading commercial MILP solvers a try (e.g. Gurobi). You can also try open-source solvers like SCIP a try. Those solvers should be faster out of the box. You can quickly evaluate different solvers with your model by writing it out as .MPS file. Every MILP solver I know of can ...

1

{0,1}-ILP can be rewritten as Pseudo-Boolean programming or MAX-Sat. It might be worth to explore alternative solving technologies for your problem.

1

Mathematically they are equivalent, but some solvers will exploit SOS2 structure with customized branching rules. Here is IBM's explanation of this for CPLEX.

Only top voted, non community-wiki answers of a minimum length are eligible