15 votes

How can we write a binary variable as a power to a constant number?

If you check the two cases for $x_{i,j}$, you will see that you can rewrite the expression as a linear function of $x_{i,j}$: $x_{i,j}=0$ yields $1-0.3^0=0$ $x_{i,j}=1$ yields $1-0.3^1=0.7$ So $1-0....
  • 23.1k
8 votes

How to construct my mixed integer programming problem with constraint of minimum consecutive ones

Define a two sets of binary variables : variables $x_i$ take value $1$ if and only if the $i^{th}$ term of the sequence equals $1$, and variable $y$ that takes value $1$ if and only if one of the ...
  • 10.9k
7 votes
Accepted

Binary variable switch constraints

You want to enforce $$ \lnot y_{i,i+1}\iff (x_i\iff x_{i+1}). $$ Rewriting in conjunctive normal form yields $$ (\lnot y_{i,i+1} \lor \lnot x_i \lor \lnot x_{i+1})\land (\lnot y_{i,i+1} \lor x_i \lor ...
  • 23.1k
6 votes
Accepted

Constraints like "max(column a + column b) == 2" are not DCP

Not sure if it is DCP, but you can write it as a quadratic constraint: $$\sum_k z_{k,i} z_{k,j} \ge 1$$ You can also linearize as follows: \begin{align} \sum_k x_{k,i,j} &\ge 1 \\ x_{k,i,j} &\...
  • 23.1k
6 votes
Accepted

Constraint on groups of variables

For your first question, let binary decision variable $y_{i,g}$ indicate whether variable $x_i$ is assigned to group $g$, and let variable $z_g$ represent the common value of variables in group $g$. ...
  • 23.1k
5 votes
Accepted

Robust way to implement $(x=0) \Rightarrow (y=0)$, with $x$ nonnegative and $y$ binary

Equivalently, you want to enforce the contrapositive $y = 1 \implies x > 0$. The standard approach is to introduce a small constant tolerance $\epsilon > 0$ and enforce $y = 1 \implies x \ge \...
  • 23.1k
5 votes

Modeling an either-or-constraint

Based on the clarification about regions, it seems that all you have to do is add the constraints $$x_{ij}=0\quad\forall i\in I,j\notin J.$$ How to handle the "treat it differently" part may ...
  • 31.9k
5 votes
Accepted

Meaning of infeasible model: unsuccessful solving for an IP model with binary variables

It might be worth trying this alternative formulation, with your same $x_k$ variables (one for each of the $2^n$ subsets) and nonnegative slack variables $s_i$. The problem is to minimize $\sum_{i=0}^...
  • 23.1k
5 votes
Accepted

Binary/integer variables get real values in docplex

All solution values will be floating-point numbers - independent of the variable types. In an optimal or feasible solution, they will simply be close to an integer value, depending on the specified ...
  • 1,493
5 votes

Implement if-else without then part using int variables {0,1}

One way to do this is to introduce three auxiliary variables: $x$ and $y$ are non-negative integers and $z$ is binary. The binary variable $z$ should equal 1 if and only if $a_0+a_1+a_2 \mbox{ mod } 2=...
  • 5,543
4 votes

Assistance in formulating binary constraint(s)

Via conjunctive normal form: $$ A_i \implies \bigwedge_j \lnot B_j \\ \lnot A_i \lor \bigwedge_j \lnot B_j \\ \bigwedge_j (\lnot A_i \lor \lnot B_j) \\ \bigwedge_j (1-A_i +1- B_j\ge 1) \\ \bigwedge_j (...
  • 23.1k
4 votes
Accepted

mixed integer programming with if then statement for two binary sequences

You want to enforce $$ ((P_{1.i} \land \lnot P_{1,i+1}) \lor (P_{2,i} \land \lnot P_{2,i+1})) \implies (\lnot P_{1,i+1} \land \lnot P_{1,i+2} \land \lnot P_{2,i+1} \land \lnot P_{2,i+2}) $$ Rewrite in ...
  • 23.1k
4 votes
Accepted

Taking derivatives of objective function with a binary variable to find minimum

First order stationary point conditions will usually not help when your variables are discrete. In this particular case, if $\tau$ is a constant (and assuming $x$ and $X$ are the same thing), the ...
  • 31.9k
4 votes
Accepted

Modeling a special case of conservation of flow

Introduce binary variables $x_a,\dots,x_e,$ with each variable taking value 1 if the corresponding arc is used. To limit yourself to a single input, add the constraint $$x_a + x_b = 1$$ (or $x_a + x_b ...
  • 31.9k
4 votes
Accepted

Modeling an either-or-constraint

You can introduce an additional binary variable $y$ that takes value $1$ if and only if at least one node from $I$ is matched with another one from $J$: \begin{align*} x_{ij} &\le y \quad \forall ...
  • 10.9k
3 votes
Accepted

Modelling not evenly distributed discrete levels of a decision variable

If you plot your power levels versus the integers 0 to 3, you will see that the function is neither convex nor concave. For that reason, I am fairly confident you will need to use binary variables.
  • 31.9k
3 votes
Accepted

How can we write a binary variable as a power to a constant number?

Suppose it is needed to linearize the expression $Z=P^U$. It can be written as $$Z=U\times P+1-U$$ where $U$ is a binary variable and $P$ is a parameter. This is a general formulation for calculating $...
3 votes

Multiprocessor Scheduling Problem: How to modify some constraints after variable changing?

The condition (*), that every job is assigned to exactly one machine, simply requires $$\sum_{i=k}^n z_{i,k} \ge 1 \quad \forall i=1,\dots,n.$$ That ensures that every job belongs to a cluster. It ...
  • 31.9k
3 votes

Binary variable to indicate zero probabilities

You are going to bump into a limitation of finite-precision floating point arithmetic. Basically, a small enough probability value will be indistinguishable from rounding error. Assuming you are using ...
  • 31.9k
3 votes

How to find the point on the exterior of a given set of points?

I posted a heuristic, based on a Delaunay triangulation, on my blog. Basically, you start with the triangulation, including the boundary of the convex hull. You then roam the boundary, looking for ...
  • 31.9k
2 votes

How to linearize the product of two binary variables?

As the first answer: $$ \begin{align} z &\leq x_i \quad \forall i = 1, \ldots, n.\\ z &\geq \sum_{i=1}^n x_i - (n-1). \end{align} $$ We should note that, the property holds for an aggregated ...
2 votes

How to find the point on the exterior of a given set of points?

Just a quick heuristic idea: Step 1) I would start with determining the convex hull of the original set of points in $\mathcal O(n \log n)$ with the Graham scan. There are various implementations out ...
2 votes

Transfer an integer model to binary

To avoid confusion, I will use $\bar{w}$ for the original (integer) $w$ variable. Assuming you have a constant upper limit $T$ on possible waiting time, you can define your new binary variables via ...
  • 31.9k
2 votes
Accepted

Disjunctive Constraint , Using Binary Variable to Replace a If or condition

The usual approach to this requires that $b$ be bounded, say $L \le b \le U$ for some constants $L$ and $U.$ You can come close to what you want with the following: $$b \ge \pi (1-q) + L q$$ $$b \le \...
  • 31.9k
2 votes

Assignment Problem with continuous decision variable

Is there even a possibility that the mathematical optimal solution is a continuous value I would say it depends on the parameterization, i.e., the values of c and t and b in your problem. From your ...
2 votes
Accepted

Are there examples where introducing clusters of binary variables provides a benefit for solving?

Whether a presolver would eliminate the $y_k$ would depend on how the presolver was programmed. Assuming the variables survived presolve, giving the $y_k$ higher priority than the $x_i$ in branching ...
  • 31.9k
2 votes

Lifting a 3rd order polynomial into a higher dimensional space

Products of binary variables can be expressed as the logical and operation. The MILP formulation of that introduces a new binary variable. We overcome "non linearity" by having more ...
1 vote

Methods for binary linear programming

Your problem can be classified as a 0-1 integer linear program. Problems in this class are NP-hard in general, even when the coefficients are all integers and there is no objective function. There are ...
1 vote
Accepted

Ensure that scheduled repeating maintenance has to be completed

Following @prubin's link in the comments, I reached Erwin Kalvelagen's blog, which seems to answer my question. A way to model this would be: $$ \sum_{i=t}^{t+k-1}m_{i} \geq k(m_{t}-m_{t-1}), \forall ...
1 vote

What fraction of the search space has been searched for ILP?

I would expect the measure of Xpress (and SCIP) to work reasonably well for infeasible problems. They take into account at which levels nodes have been pruned during search and that directly relates ...
  • 11

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