Newest 'binary-variable' Questions

2

votes

0answers

63 views

Indicator function for integer variable with inequality constraint

I have $n$ integer variables $\vec{x}$ with the following integer programming problem. $$ COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0) $$ Here, $a_i, b_j \in \mathbb{R}_+$ ...

asked Oct 6 at 16:22

Omar Shehab

1312 bronze badges

1

vote

0answers

32 views

Interger programming using gray encoding

Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...

optimization mixed-integer-programming integer-programming binary-variable

asked Sep 29 at 8:07

Omar Shehab

1312 bronze badges

0

votes

0answers

30 views

Linearizing max constraint Problem [duplicate]

I want to linearize a max constraint as below: In which x_(i,t),are binary decision variables and T is a constant. How can I linearize this constraint?

modeling integer-programming constraint binary-variable logical-constraints

asked Sep 24 at 16:08

Yousef Mirzaeian

92 bronze badges

2

votes

1answer

48 views

Formulating indicator constraint set

I am having difficulty formulating the indicator constraints for the following: Consider a set of $A_{n}$ decision variables such that $A_{1},A_{2},⋯,A_{n}<A$. While all of them are integers that ...

optimization modeling binary-variable indicator-constraints reformulation-linearization

asked Sep 9 at 10:55

Mike

3671 silver badge8 bronze badges

3

votes

1answer

90 views

Logical constraint in ILP

I want to write the following constraint: Let $z$ be an integer variable such that $0\le z\le M$, and $t$ be a binary variable where $M$ denotes big-M. The logical constraint is as follows: if $z \...

mixed-integer-programming linear-programming linearization binary-variable logical-constraints

asked Aug 15 at 19:08

che

1173 bronze badges

4

votes

2answers

112 views

Faster implementation of “or” constraints in ILP

I have implemented a set of "or" constraints in my ILP using binary decision variables (as in this method). It works fine for smaller problems, but when I try to increase the number of ...

linear-programming integer-programming constraint binary-variable indicator-constraints

asked Aug 5 at 15:45

Animik

1414 bronze badges

3

votes

1answer

51 views

Linearizing separable functions: SOS2 sets or binary variables

When linearizing a separable nonlinear function is there an advantage/disadvantage in using SOS2 sets in comparison to using binary variables?

linearization binary-variable sos2 separable

asked Aug 3 at 15:05

Clement

1,0171 silver badge9 bronze badges

5

votes

1answer

95 views

Minimize binary variable's distance with respect to the index values

For a given binary decision variable $x[i,j,k]$ my goal is to get as dense results in terms of k for successive values of j. Distance of k value to be kept as close as possible throughout j values: $d ...

optimization constraint linearization binary-variable minimax

asked Aug 3 at 8:03

Psyndrom Ventura

3157 bronze badges

4

votes

1answer

51 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 ...

reference-request binary-variable logical-constraints nonconvex-programming yalmip

asked Jun 29 at 18:50

independentvariable

3,3024 silver badges27 bronze badges

5

votes

1answer

315 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 ...

reference-request binary-variable computational-complexity

asked Jun 9 at 7:33

Mostafa

1,7314 silver badges20 bronze badges

4

votes

2answers

151 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 \ \ \...

binary-variable logical-constraints

asked May 20 at 9:50

Psyndrom Ventura

3157 bronze badges

3

votes

1answer

103 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$ ...

mixed-integer-programming modeling binary-variable

asked May 12 at 19:30

Clement

1,0171 silver badge9 bronze badges

3

votes

1answer

85 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\...

modeling binary-variable pyomo ampl minlp

asked May 10 at 1:42

Oguz Toragay

7,1581 gold badge5 silver badges34 bronze badges

2

votes

1answer

67 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 ...

linear-programming combinatorial-optimization binary-variable logical-constraints

asked Apr 30 at 0:20

Sam

1516 bronze badges

2

votes

1answer

63 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 ...

linear-programming integer-programming linearization binary-variable

asked Apr 24 at 12:14

Dav

234 bronze badges

5

votes

3answers

78 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_{...

linear-programming integer-programming binary-variable

asked Apr 22 at 0:15

zdm

3594 bronze badges

3

votes

1answer

153 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'...

solver binary-variable nonconvex-programming convex-optimization aimms

asked Apr 4 at 16:09

independentvariable

3,3024 silver badges27 bronze badges

9

votes

3answers

454 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 ...

constraint binary-variable

asked Mar 27 at 19:50

zdm

3594 bronze badges

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 ...

integer-programming binary-variable

asked Mar 22 at 21:51

zdm

3594 bronze badges

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 ...

mixed-integer-programming binary-variable big-m

asked Mar 19 at 19:11

Clement

1,0171 silver badge9 bronze badges

5

votes

2answers

263 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 ...

mixed-integer-programming modeling binary-variable

asked Mar 11 at 23:16

Clement

1,0171 silver badge9 bronze badges

-4

votes

2answers

91 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 ...

mixed-integer-programming constraint binary-variable

asked Mar 5 at 14:41

Clement

1,0171 silver badge9 bronze badges

6

votes

2answers

204 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 ...

mixed-integer-programming constraint binary-variable

asked Mar 5 at 9:11

Clement

1,0171 silver badge9 bronze badges

5

votes

1answer

513 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}...

linear-programming linearization binary-variable

asked Feb 20 at 16:09

Taner Cokyasar

8751 silver badge9 bronze badges

8

votes

1answer

102 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 ...

mixed-integer-programming computational-complexity binary-variable

asked Jan 8 at 22:51

dipak narayanan

1,4111 silver badge13 bronze badges

13

votes

2answers

799 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 ...

modeling integer-programming binary-variable

asked Dec 18 '19 at 13:27

JonathanZ

1335 bronze badges

8

votes

2answers

274 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 ...

optimization mixed-integer-programming nonlinear-programming linearization binary-variable

asked Dec 16 '19 at 23:15

dipak narayanan

1,4111 silver badge13 bronze badges

12

votes

0answers

148 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&\...

integer-programming binary-variable duality bilevel-optimization

asked Dec 12 '19 at 9:11

abebebebahabe

1834 bronze badges

9

votes

3answers

431 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 ...

mixed-integer-programming modeling constraint-programming binary-variable

asked Dec 6 '19 at 15:07

Libra

8152 silver badges12 bronze badges

7

votes

1answer

124 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 $\...

modeling binary-variable

asked Nov 1 '19 at 11:58

Djames

8271 silver badge9 bronze badges

8

votes

1answer

366 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 ...

linear-programming integer-programming linearization binary-variable

asked Oct 24 '19 at 10:44

dipak narayanan

1,4111 silver badge13 bronze badges

5

votes

2answers

224 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'}}...

integer-programming cplex python binary-variable docplex

asked Oct 11 '19 at 14:30

campioni

1,0271 silver badge9 bronze badges

14

votes

4answers

230 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 ...

optimization linear-programming integer-programming binary-variable

asked Oct 9 '19 at 8:27

worldterminator

2431 silver badge3 bronze badges

9

votes

1answer

104 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 ...

linear-programming constraint binary-variable

asked Oct 8 '19 at 8:08

campioni

1,0271 silver badge9 bronze badges

9

votes

1answer

209 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....

optimization mixed-integer-programming linear-programming integer-programming binary-variable

asked Oct 4 '19 at 1:46

Dom

914 bronze badges

7

votes

1answer

639 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 ...

optimization linear-programming solver binary-variable assignment-problem

asked Sep 21 '19 at 16:50

Jacob Myer

4471 silver badge6 bronze badges

9

votes

1answer

92 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$...

modeling logical-constraints binary-variable

asked Sep 12 '19 at 1:40

independentvariable

3,3024 silver badges27 bronze badges

6

votes

1answer

121 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 ...

integer-programming solver nonlinear-programming binary-variable ampl

asked Aug 24 '19 at 16:59

Oguz Toragay

7,1581 gold badge5 silver badges34 bronze badges

12

votes

1answer

365 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\...

modeling cplex academia binary-variable indicator-constraints

asked Aug 17 '19 at 15:42

Libra

8152 silver badges12 bronze badges

7

votes

2answers

342 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 ...

linearization combinatorial-optimization quadratic-programming convexity binary-variable

asked Jul 9 '19 at 0:00

dipak narayanan

1,4111 silver badge13 bronze badges

17

votes

3answers

596 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, Ramsey numbers, factoring numbers, the ...

optimization combinatorial-optimization binary-variable

asked Jun 29 '19 at 19:02

Nike Dattani

9102 silver badges20 bronze badges

16

votes

2answers

177 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 ...

optimization constraint quadratic-programming binary-variable

asked Jun 15 '19 at 2:17