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: \begin{equation} 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