Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
36
questions
4
votes
1answer
48 views
Maximizing 1-norm: using binary variables to relax non-convexity
It is well-known that when we maximize a 1-norm, e.g., $\|Ax\|_1$, we can use binary variables and obtain a mixed-integer convex problem (otherwise maximizing 1-norm is non-convex). I am mentioning ...
4
votes
1answer
273 views
Polynomially solvable cases of zero-one programming
I am dealing with a problem having two types of variables: binary variables, and continuous variables.
In some cases, the continuous variables are not used, and so the problem contains those binary ...
4
votes
2answers
123 views
Conditional Constraint in MIP
I need to formulate a conditional constraint for a binary variable z defined as:
$z_{i,j,k}$, $\ \ i=1:10 \ , \ j=1:5 \ , \ k=1:3$
If any $z_{i,j,3} = 1$ then $z_{i,j,1} + z_{i,j,2} = 0 \ \ \...
3
votes
1answer
96 views
Modeling the sum of binary variables
Suppose $x_{1},x_{2}, \cdots ,x_{n}$ are binaries.
I would like to model the following:
IF $x_{1} + x_{2}+ \cdots +x_{n} \ge 2$ THEN $x_{1} + x_{2} = 2$
IF $x_{1} + x_{2}+ \cdots +x_{n} \ge 3$ ...
3
votes
1answer
64 views
How to define hybrid variables without using additional binary variables?
I am working on a large NLP model with equilibrium equations in which the variables are defined in the following form:
$$x_i \in [L_B, U_B] \cup\{0\} \quad \text{where} \quad L_B \ \& \ U_B \in\...
2
votes
1answer
58 views
Same values constraint and grouping of variables
In a linear program, I would like some variables to:
1. Take the same values
2. Group some variables i.e. some variables should take same values or lie within certain percentage.
3. All different ...
2
votes
1answer
44 views
Inequality Constraint Linearization of a product of an integer and a binary variable
I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable?
But the answers to that questions didn't help me find a solution for my ...
5
votes
3answers
76 views
Requiring exactly $n_j$ slots for job $j$ (if scheduled)
Let $x_{j}(t)=1$ iff job $j$ is scheduled at time $t$. I want to say that if the job is scheduled at all, then it is scheduled at $n_j$ slots. I wrote this as:
$$x_{j}(t)\sum_{s=1}^{T}x_{j}(s)=n_jx_{...
3
votes
1answer
131 views
Approximation methods for a mixed integer convex optimization problem
I have a convex objective function, e.g., minimizing the negative entropy function. My constraints are also linear. The only issue is that I also have binary variables.
I am currently aware of AIMMS'...
9
votes
3answers
448 views
Is there a better way to formulate this constraint?
Let $x_{r}^{j}=1\iff$ the machine schedules job $j$ using resource $r$. My constraint says that: a resource cannot be used twice, i.e., if $x_{r}^{j}=1$, then $x_{r}^{j'}=0$ for $j'\neq j$. I write ...
4
votes
1answer
53 views
Find the number of idle intervals with weights
We have one job $i$ and one machine. Let $\mathbf{x}_i=[x_{i,1},x_{i,2},\ldots,x_{i,T}]$ be a binary vector where $x_{i,t}=1\iff$ job $i$ is scheduled at time $t$. Let $u$ be a positive number. I ...
6
votes
2answers
1k views
IF X = 0 THEN Y = 1, IF X > 0 THEN Y => 0
I'm trying to model the following
IF $tS = 0$ THEN $Y = 1$, IF $tS \gt 0$ THEN $Y \ge 0$
$tS$ is a positive real number and $Y$ is binary.
I tried the following:
$tS - \epsilon \ge -M Y$ but ...
5
votes
2answers
256 views
How can this relationship be modelled?
I declare an array of binary variables as $y(i), i = 1, ..., N$
I would like to model the following:
If $y(i-1) + y(i) = 1$ then $y(k) = 0$ for $k < i$ and $y(m) = 1$ for $m \geq i$
To make ...
-4
votes
2answers
83 views
How can I model this binary logic?
I am looking for a constraint to express the following:
IF W1 = 0 AND W2 = 0 THEN Y = 0
IF W1 = 0 AND W2 = 1 THEN Y = 1
IF W1 = 1 AND W2 = 0 THEN Y = 0
IF W1 = 1 AND W2 = 1 THEN Y <= 1
...
6
votes
2answers
196 views
How can this be expressed as a MILP constraint?
I am looking for a constraint to express the following:
IF W1 = 0 AND W2 = 0 THEN Y = 1
IF W1 = 0 AND W2 = 1 THEN Y = 1
IF W1 = 1 AND W2 = 0 THEN Y = 0
IF W1 = 1 AND W2 = 1 THEN Y <= 1
...
5
votes
1answer
500 views
How can I deal with a possibly undefined constraint?
I have a minimization problem minimizing $d_k \geq 0$ and some other variables with all strictly positive coefficients. I leave my objective function below to better convey my goal.
$$\min_{\mathbf{d}...
8
votes
1answer
91 views
Complexity comparision between purely BLP and MILP problems?
Could someone please comment and answer on the complexity of purely binary linear programming (BLP) and mixed-integer linear programming (MILP)?
In MILP, we have both binary and continuous variables ...
13
votes
2answers
767 views
How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?
When I have to write the formulation of an IP, I usually have the choice between writing $i\times j$ binary variables with two indices such as $ x_{i,j} $ or, writing $j$ integer variables $x_i$.
Is ...
8
votes
2answers
254 views
How can I transform this MILP into an LP problem?
I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient ...
12
votes
0answers
130 views
Integrality gap in bilevel binary linear programming problem
I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is
$$
\begin{alignat}2
\min\limits_x&\...
9
votes
3answers
404 views
Interval variables in MIP
In Constraint Programming it is possible to use interval variables to represent intervals of time during which something happens (see here), usable in scheduling problems, for example.
Is there ...
7
votes
1answer
122 views
Help with formulating an implication
I have a binary variable $y$ and a set of binary variables $x_i$, where $i\in I$.
My problem requires that $$\sum\limits_{i\in I}x_i = b.$$
What I want to formulate is the following implication: if $\...
8
votes
1answer
245 views
How to linearize the multiplication of an integer and a binary integer variable?
I have the following constraints
\begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align}
where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable ...
5
votes
2answers
156 views
How to establish constraint between variables with multiple indexes using CPLEX in Python
I am new in CPLEX and I am using docplex in Python to solve an ILP.
I would like to translate the following constraint in docplex:
$$\sum_{c}(X_p{_w}_{cj}+X_{p+1}{_{w'}}_{cj+1})\leqslant T_w{_{w'}}...
14
votes
4answers
211 views
Does this $0-1$ integer program have any speciality?
Given matrix $A \in \{0,1\}^{m \times n}$ and vector $b \in (\mathbb{Z^+})^m$, where $\mathbb{Z^+}$ is the set of positive integers,
$$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ...
9
votes
1answer
99 views
Constraint to state the relation between 2 binary variables
I'm trying to deal with a process planning and machine layout allocation simultaneously.
I have the following variables:
$X_p{_w}_{cj}=1$ if an operation $p$ is done by a machine $w$ with a ...
9
votes
1answer
208 views
Should I factor in time as a parameter or a variable in a scheduling problem with MILP?
I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written....
7
votes
1answer
511 views
Excel Solver linear programming - Is it possible to use average of values as a constraint without #DIV/0! errors or sacrificing linearity?
I'm trying to create an assignment optimization model where the areas are assigned to either the south or north school districts so that the total distance is minimized. Each school must have at least ...
9
votes
1answer
90 views
Binary variable to count appearances
Let $x \in \mathbb{R}^n$ be an optimization variable. Now, at a constraint, I would like to count how many times a value, say $2$, appears in $x$ decision.
I think we can have a binary variable $y_i$...
6
votes
1answer
117 views
Obtaining the intermediate solutions in AMPL
I know that for some solvers, for example, the constraint programming solver in Google OR-Tools, it is possible to see all the intermediate solutions that the solver finds while it searches for an ...
11
votes
1answer
289 views
Representing an indicator function: binary variables and “indicator constraints”
I want to represent the indicator function:
$$ \mathbb{1}_{(y=j)}$$
where $y$ is a non negative, integer variable.
My attempt is as follows: define a binary variable:
$$ z_j =\begin{cases}
1 \qquad\...
7
votes
2answers
327 views
How can I linearize or convexify this binary quadratic optimization problem?
I have an optimization problem as below. I am having a hard time with the last constraint.
$\max \eta$
subject to
${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$
here
$\bf{A}$ is a Binary ...
16
votes
2answers
448 views
What are some real-world applications of QUBO?
QUBO (Quadratic Unconstrained Binary Optimization) is the minimization of a quadratic function of binary variables.
It has been used for computer vision, Ramsay numbers, factoring numbers, the ...
16
votes
2answers
168 views
Can we replace a binary variable with a continuous variable using a quadratic equality constraint?
Is it possible to replace a binary variable $x$ with a continuous variable that satisfies the quadratic equality constraint $x^2 - x=0$?
The function $f(x) = x^2 -x$ is not a convex function. Can ...
24
votes
1answer
1k views
How to linearize the product of a binary and a non-negative continuous variable?
Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
26
votes
2answers
2k views
How to linearize the product of two binary variables?
Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
