Questions tagged [binary-variable]
For questions that involve variables than can only take on one of two values, usually 0 or 1.
18
questions
8
votes
1answer
82 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 ...
12
votes
2answers
723 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
234 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
104 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&\...
8
votes
3answers
374 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
115 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
125 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
75 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
184 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
93 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
202 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
349 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
84 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
111 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
204 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
315 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
350 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
150 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 ...
