Questions tagged [binary-programming]
An optimization problem in which the decision variables are binary.
182
questions
0
votes
0
answers
19
views
Testing functions for binary optimization
It is well known that it is hard to find optimum of some functions, mainly those with lot of local extremes, discontinuities etc. To assess quality of optimization algorithms (particularly heuristics),...
- 373
-1
votes
0
answers
15
views
Disjunctive Constraint , Logical Constraints, Using Binary Variable to Replace a If or condition
I am trying to use a binary variable based on an inequality.
The value of binary variable $q $ is 1 or 0 based on the following equation.
[
$q $ =
\begin{cases}
0,& \text{if } b \geq \pi ,\\
1,...
0
votes
0
answers
23
views
Solving an Quadratic Polynomial with binary variables
Let's say you have a set of $n$ variables $S=\{a,b,c,d,...\}$, each of which can either be $0$ or $1$. How many solutions where exactly $l$ variables are equal to $1$ such that $3l-c_0ab-c_1ac-c_2ad-.....
0
votes
1
answer
50
views
Binary matrix multiplication optimization problem
I am looking for pointers to and names of computational approaches to solve a binary matrix optimization problem of:
$$ minimize: ||\mathbf{X}\mathbf{Y} - \mathbf{T}||_{L1} $$
where $\mathbf{X}$ and $\...
- 103
0
votes
1
answer
53
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,
\begin{equation}
\max_{x\in\{1,0\}} c^\top x
\end{equation}
and for constraints, I need all ...
- 307
2
votes
1
answer
36
views
Linear program with exponential decay between variables
I'm trying to create a linear program to solve a scheduling problem, below is a description of the problem, I'll try my best to keep it short but comprehensive.
The core of the problem is that a daily ...
- 23
0
votes
0
answers
25
views
Constrained coloring of bigraph nodes
I have a graph $G(U,V,E)$ representing a set of documents ($U$) and queries ($V$). Every document has 1-5 queries it is connected to, and every query has 1-50 documents it is connected to. There are ~...
- 176
0
votes
0
answers
26
views
Finding a binary vector that satisfies non-linear constraints
I’m looking for good heuristics for finding at least one (of a probably large set, although possibly none) high dimensional ($|v|>5000$) binary vector that satisfies a set of non-linear/non-...
- 176
-1
votes
1
answer
47
views
Linear programming mathematical model
The problem:
There are $N$ cities $(1, 2, \dots, N)$. There are roads connecting $M$ pairs of cities in $N$.
Stores need to be build in way that for each city $X$ store is in city $X$ or in ...
0
votes
1
answer
32
views
Conditional constraints in binary integer programming problems
I am confronted with the problem of writing conditional constraints in a binary integer programming problem. Let us consider a typical knapsack problem. The constraint is that if items $1$ and $2$ are ...
- 715
0
votes
1
answer
67
views
How can I solve a binary quadratic program in MATLAB?
I'm not an expert in MATLAB. Can I use MATLAB function fminimax to solve the problem below?
Let's say I have matrix $\mathbf P$ and let's say $\bf Px = b$. My ...
0
votes
0
answers
35
views
Establish constraints
This question is based on this. There are two equations given as solutions by prubin.
However, now I want something different. I want the first constraint to ensure that at least $a$ out of the first $...
- 75
1
vote
2
answers
72
views
Binary programming problem. Any closed solution and/or lower bound for this particular case?
Consider the following problem:
$$\begin{array}{ll} \underset{{\bf x} \in \{0, 1\}^N}{\text{minimize}} & {\bf x}^\top {\bf A} \, {\bf x}\\ \text{subject to} & {\bf B} {\bf x} = {\bf c}\end{...
- 13k
3
votes
1
answer
74
views
Modeling contiguity of machine processing in a flow shop environment via a MIP
I'm working on a Mixed-Integer-Programing (MIP) formulation for a flow shop scheduling problem. One of the requirements/wishes is that for each machine $i$, processing should be contiguous, or at ...
- 101
0
votes
0
answers
16
views
A001511 is the `O(1)` space complexity implementation of DFS for full binary trees. What is the general case?
I found an interesting O(1) space complexity solution for DFS in a full binary tree where path information is not required. I need your help to find the general ...
- 1,410
1
vote
1
answer
118
views
Linear constraint considering binary bit position
Right now, I have some binary variables for a linear programming problem:
$x_1\;x_2\;x_3\;x_4\;x_5\;x_6\;x_7\;x_8$
Say these are groups of 4 bits each in this example. So:
Group 1 ={$x_1\;x_2\;x_3\;...
- 75
2
votes
1
answer
32
views
Is this how this question supposed to be solved? (Writing a system of constraints that represents this connection between variables).
Given that $x,y,z,w,v\in \{0,1\}$. The connection between the variable is given by:
$\max\{\min\{x,y\},z,v\}=w$.
Write a system of linear constraints that represents this connection.
My Work:
Let $...
- 2,051
0
votes
1
answer
40
views
Best subset selection
Consider an $n \times d$ data matrix $D$ in which you want to find
the best subset of $k$ features that are related to the $n$-dimensional regressand vector $y$. Therefore, the following mixed integer ...
- 1,645
2
votes
1
answer
46
views
Modeling sequence dependent setup times via a MIP for flow shop scheduling
As part of a Non-Permutation Flowshop Scheduling (NPFS) problem, I would like my MIP model to be able to deal with sequence dependent setup times. That is, for each pair of consecutive jobs, a setup ...
- 101
0
votes
0
answers
32
views
Construct linear floorplanning constraints
This question is an extension of a previous question.
Right now, what I have are these "cheap" equations. The goal is to have the floorplan allow a circle with diameter, $D$ outside the red ...
- 71
1
vote
1
answer
131
views
Proof of correctess: Max Cut reduction to QUBO
Consider an undirected, unweighted graph $G=(V,E)$. We want to find the Maximum-Cut of the graph, which is defined to be $A \subseteq V$ maximizing the value
$$\sum_{uv \in E, \; u \in A, \;v \in V \...
- 153
0
votes
2
answers
62
views
Does this system of inequalities have a solution?
Consider the following system of inequalities:
$$ \left\{ \begin{array}{ll}
x_{ab}+x_{ac}+x_{ad}+x_{abc}+x_{abd}+x_{acd}+x_{abcd}\ge 4+x_{bc} +x_{bd}+x_{cd}+x_{bcd}\\
x_{ab}+x_{bc}+x_{bd}+x_{abc}+x_{...
- 1,320
0
votes
1
answer
61
views
Need help in framing the set of linear equations for a binary variable as per following conditions [closed]
I have a binary variable array: $Y(i,j)$. Where $i=1,\dots,I$ and $j=1,\dots,K$. Here $K$ and $I$ need not to be same. In other words, the matrix formed $Y(i,j)$ is not necessarily be a squared ( but ...
- 65
0
votes
1
answer
55
views
Help in writing linear equations based on conditionality in GAMS (9 variables)
I have tried following problem, but I could not solve it. Can you please help me in this?
I have 8 binary variables : a,b,c,d,e,f,g,h
I want to define a variable (x) with the help of linear equations ...
- 65
0
votes
1
answer
99
views
one way conditional statement in binary variable linearization
I am trying to write a one-way conditional statemen with binary variables. my condition is (x and y are both binary variables)
(if x=1 then y=0)
and it is the only ...
-1
votes
1
answer
45
views
Notations in Binary Integer Model
I am trying to build a model to solve a problem.
In the problem, one product set consists of different product items, for example, product set 1 consists of Pencil A + Pen D + Eraser B + Scissor C, ...
- 1
0
votes
1
answer
162
views
Relaxation of the binary optimization problem doesn't make sense in terms of the original problem - how do I repose the model to make sense?
Suppose I have a set of binary variables $x\in \{0,1\}^N$,
where in the context of my optimization problem these binary parameters mean to include the parameter in a model or not include it, where ...
- 581
0
votes
1
answer
44
views
Inequality into Binary variable in Linear Programming
I want to solve this problem :
We have 100 cities where if there is a fire we need to call at least 1 police officier and 3 firefighters from place that are in distance of 100 km or less.
The distance ...
0
votes
2
answers
78
views
Linear Programming Cutting Problem
I'm doing some self studying and I have come across a problem I don't quite understand. The problem only gives me the single constraint:
The first question asks me to show that the given constraint ...
- 55
1
vote
2
answers
69
views
Find subset of integers that sum to a specific value [closed]
I have a column in an Excel spreadsheet that is composed of positive and negative integers (credits and debits from an accounting ledger). I also have a specific value that is the sum of some subset ...
2
votes
0
answers
71
views
Pseudo-Boolean Function - Interpretation of a Property
I am considering the following Pseudo-Boolean function $f:\{0,1\}^{3}\rightarrow \mathbb{R}$, where f is
$$ f(I_{1},I_{2},I_{3}) = \left(I_{1}+I_{2}+I_{3}\right)^{\beta} $$
with $\beta>0$.
after ...
- 67
1
vote
1
answer
30
views
Complex logic binary and M
Here's the problem:
a and b are continuous between -15 and 15. Explain how the following conditions can be represented as linear constraints using binary variables: At least two of the conditions must ...
- 49
1
vote
1
answer
34
views
Formulating a complicated if else statement with linear programming
I'm trying to convert the following statement into «only one» inequality. Is it possible?
If $M[i] < M[j]$ and $M[j] < M[k] $ and $A[i,k] = 1$ then $A[i,j]=1$
$M$ is an array of size N and its ...
- 33
0
votes
1
answer
34
views
determine whether if a linear system has binary solutions.
Is there any general method that helps to determine a linear system have binary solutions?
E.g. For a linear system
$$
Ax=b
$$
Where $A \in \mathbb{N}^{m\times n}, b \in \mathbb{N}^{m\times 1}$. Is ...
- 1,113
1
vote
1
answer
48
views
Establish rules
I think the above constraint when the absolute value of the HW for 2 strings is less than the HD between those strings. Any thoughts on the proof, please?
Also, how do I make it a constraint if it's ...
- 75
-1
votes
1
answer
37
views
Valid inequality with chvatal gomory for problem with binary variables
I am not able to find a valid inequality with chvatal gomory for my problem that increases the value of the relaxed problem.
My problem:
Determine the optimal allocation of n workers to m machines in ...
1
vote
2
answers
114
views
Nonlinear Binary Programming
I am trying to understand what is the best approach to solve this binary programming problem
$$ \max_{X\in \left\{0,1 \right\}^{N}} \left(\sum_{i=1}^{N} a_{i}X_{i}\right)^{\beta} - \sum_{i=1}^{N}c_{i}...
- 67
0
votes
1
answer
93
views
Either-or condition for equality constraints
Consider the following optimization problem
\begin{equation*}
\begin{split}
\text{min} & \sum_{j\in J} c_jx_j \\
& \quad \sum_{j\in J} a_{1j}x_j \leq b_1 \\
& \quad \sum_{j\in J} a_{2j}x_j ...
- 2,516
0
votes
1
answer
63
views
Either-or condition for set of constraints
Consider the following optimization problem
\begin{equation*}
\begin{split}
\text{min} & \sum_{j\in J} c_jx_j \\
& \quad \sum_{j\in J} a_{1j}x_j \leq b_1 \\
& \quad \sum_{j\in J} a_{2j}x_j ...
- 2,516
1
vote
1
answer
81
views
Integer/Binary Programming - Convert nonlinear constraint to linear constraint
I have a constraint based on matrix multiplication. It involves summation of a product. The product multiplies two entries of a variable matrix named order, and an entry of a constant matrix named ...
- 11
1
vote
1
answer
273
views
Converting job assignment problem into a 0-1 linear programming problem
There are $n$ people who need to be assigned to execute $n$ jobs, one person per job. (That is, each person is assigned to exactly one job and each job is assigned to exactly one person.) The cost ...
- 71
3
votes
1
answer
130
views
Is this problem NP-hard?
Is the following problem NP-hard?
Let $Ax=b$, where $a_{i,j} \in \{0,1\}, b_i \in \{0,1\}, x_j \in \{0,1\}$.
Decide, wether there is a solution or not.
- 154
0
votes
1
answer
179
views
Linearizing constraint ( multiplication of binary variables)
I am trying to think of contraint(s) that can linearize constraint below.
$\sum_{T} \sum_{TR} Z_{(T,D)}* Y_{(TR,T)} \leq CAP_{(D)} \forall D$
Both Z nad Y are Binary Variables and CAP is capacity ...
1
vote
1
answer
45
views
Find binary vector furthest away from set of binary vectors? [closed]
How can I find the binary vector furthest away from a set of binary vectors?
- 322
0
votes
1
answer
50
views
(0-1) knapsack polytope
$$P = \{x \in \{0,1\}^4 : 4x_1 + 3x_2 + 2x_3 + x_4 \leq 4\}$$
I have to disaggregate the main constraint in $P$ by using minimal cover extension procedure.
I have found that minimal cover is: $\{2,3,4\...
- 1
-1
votes
1
answer
80
views
Model the constraint ‘Only if decision 1 is yes and decision 2 is no, then decision 3 is allowed to be yes’ [closed]
Model the constraint ‘Only if decision 1 is yes and decision 2 is no, then decision 3 is allowed to be yes’ as a set of linear constraints that should simultaneously be satisfied. Add binary variable(...
0
votes
1
answer
370
views
Linearize absolute value constraint
I want to linearize the following absolute value constraint for MILP:
$ \sum_{l=1}^{n} |x_{gl} - x_{hl} | > k $, where $x_{g}$ and $x_{h}$ represent different types of bit strings of length $n$ ...
- 71
0
votes
1
answer
49
views
Creative solution to set of nonlinear equations
I have a set of $N$ equations and $N$ unknown variables $x_{i}$ like $0 = x_{0}x_{1} - 1 - x_{0}x_{2}$. That's an example. Realistically the equations will be much larger. Each $x_{i} \in \{0, 1\}$. ...
- 317
0
votes
1
answer
42
views
Solution to quadratically constrained binary integer program
I'm trying to solve a problem for $x$ which is a vector of length $n$ with only binary elements, i.e. each $x_{i}$ is either $0$ or $1$.
There are two constraints on $x$, one quadratic and one linear:
...
- 317
1
vote
1
answer
67
views
Constrain binary optimization to avoiding certain patterns
If I have a set of binary variables that indicate whether something is active or not (in my case this is for employee scheduling) like so:
$$x_1E_1 + x_2E_1 + x_3E_1 + x_4E_1 $$
where $x_i$ is a ...
- 113