# Questions tagged [binary-programming]

An optimization problem in which the decision variables are binary.

223 questions
Filter by
Sorted by
Tagged with
1 vote
46 views
+50

### Calculation of special subsets in high-dimensional binary matrices

I need to solve a rather specific problem related to binary matrices. The task is to count the number of specific "combinations", where "combination" means the following: this is ...
• 305
15 views

### Optimizing a Complex Project-Employee Assignment Function (Pure nonlinear 0-1 programming)

I'm working on optimizing a project-employee assignment problem involving a complex objective function. I'm seeking help to understand the best approach to maximizing this function. The objective ...
1 vote
49 views

### Minimizing $\|Ax-b\|$ given that x can only take values 0 or 1

earlier I stumbled upon a question about finding a vector x that minimises $\|Ax-b\|$ where A is a known matrix and b is a known vector. However, I was wondering whether this can be achieved under the ...
1 vote
42 views

### How to make this conversion from a binary integer linear program to a quadratic program?

I saw a conversion from a binary integer linear program (BLP) to a quadratic program (QP) in this link https://qr.ae/psu9Wr. I will repeat the problem below. The original problem is \begin{align} \...
26 views

### Convert 0-1 integer linear program to quadratic form.

I am searching for a general conversion from 0-1 integer linear programs to (integer) quadratic programs. And I see this answer using a general example. https://qr.ae/psu9Wr. I checked the optimality ...
37 views

### Explanation of multiple constraints from one rule [closed]

I'm trying to understand this case study: https://github.com/DorisRipley/Art-Exhibition-Optimization-A-BIP-Modeling-Approach/blob/main/Art%20Exhibition%20Optimization.pdf and I'm having trouble with ...
1 vote
78 views

### Why this ILP and LP are equivalent?

Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
82 views

### Dual of LP representation of graph coloring

I have found a representation of the graph coloring problem as an ILP. Given a graph $G = (V, E)$. Let $C$ represent the set of colors. Let $w_c$ be a binary variable that is $1$ if the color $c$ is ...
• 511
68 views

### Binary solution to least squares linear regression [closed]

I am looking for a closed form solution $x^*$, binary vector, to $$\arg\min_{x}(\|M x + b\|_2),$$ restricted to $x \in \{ 0,1 \}^n$. Here $b \in \mathbb{R}^{m}, M \in \mathbb{R}^{m \times n}$ are ...
• 11
24 views

• 15
48 views

• 23
43 views

### Operations research | Employee availability problem

So I have a problem with school and I am not sure if it is a employee schedueling problem, here is the situation: We have to minimize the amount of employees at a non profit organization(Sanquin) and ...
180 views

• 1
1 vote
44 views

### Condition of constraint in BILP

I have a set of $n$ activities $a_i \in A$. Each activity $a_i$ has a set of child activities $C_i \subset A$, an associated cost $k_i$, and a start time $t_i$. In the BILP model I use, I consider a ...
• 99
1 vote
45 views

• 103
66 views

### Question on designing a binary (integer) programming problem

Given a vector $c\in\Re^n$ and a vector $b\in\Re^n$, I would like to design a binary programming problem, $$\max_{x\in\{1,0\}} c^\top x$$ and for constraints, I need all ...
• 149