Questions tagged [binary-programming]
An optimization problem in which the decision variables are binary.
231 questions
1
vote
0
answers
50
views
Semidefinite relaxation for a binary quadratic program with an $\ell_1$ penalty term
I am considering the following regularized binary quadratic optimization problem with a sparsity penalty
$$ \min_{{\bf x} \in \{\pm 1\}^n} \; {\bf x}^\top {\bf C} \, {\bf x} + \| {\bf A} {\bf x} - {\...
- 93
0
votes
1
answer
55
views
Seeking advice on how to "see" this derivation
I'm struggling to model this constraint for a problem:
$$x_C^4 = 1 \implies (x_A^4 + x_B^4 \geq 1 \land x_A^1 + x_B^1 = 0) \;\lor\; x_A^2x_B^3 = 1 \;\lor\;x_A^3x_B^2=1.$$
where all variables are ...
- 2,129
0
votes
0
answers
47
views
Solve system of linear diophantine equations such that solution vectors only have entries $\in \{0,1\}$
I want to find all solutions $\mathbf{x}$ of the system of linear diophantine equations
$$
\mathbf{A} \mathbf{x} = \mathbf{b}
$$
where $\mathbf{A}$ is a $m \times n$ matrix such that $A_{ij} \in \...
- 261
1
vote
1
answer
126
views
Relaxing a binary constraint in an optimal control problem
Crossposted at Operations Research SE
I am attempting to optimize the operation of an electrical system that produces some amount of thermal power $P_t$ and keeps a temperature $x_t$ within a certain ...
- 11
0
votes
0
answers
32
views
Generating relations from linear equation system with binary coefficients
Given a binary coefficient matrix $A \in \{0,1\}^{m\times n}$, $n>m$, and a real-valued vector $b\in \mathbb{R}_+^m$, the corresponding linear equation system is underdetermined and does not admit ...
- 203
1
vote
1
answer
199
views
How to tackle this optimization with binary variables?
So, I have a (practical) optimization problem in which (somewhat large, say $1500$) $N$ binary variables need to be found.
$
\min_{a \in \{0,1\} ^N} \sum_i \left(\frac{a_i w_i}{\sum_j a_j w_j}\right)^...
- 3,288
4
votes
3
answers
431
views
Is there an elegant general method for solving linear multiplicative system of equations in modulo 2? Here is an interesting example problem.
Here is the following problem:
I have solved the system of equations with simply using brute force but I feel there must be a ...
- 41
1
vote
0
answers
65
views
Efficient Algorithm for Binary Tensor Decomposition?
I've been working with high-dimensional binary tensors (e.g., tensors with entries that are only 0s and 1s) and I'm looking for an efficient way to decompose them into rank-1 components. The tensors I'...
- 11
2
votes
1
answer
154
views
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 ...
- 371
1
vote
1
answer
74
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 ...
- 13
1
vote
1
answer
105
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}
\...
- 11
0
votes
1
answer
115
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 ...
- 11
2
votes
2
answers
49
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
1
answer
117
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 ...
- 13
0
votes
0
answers
180
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 ...
- 523