Questions tagged [binary-programming]
An optimization problem in which the decision variables are binary.
205
questions
1
vote
1
answer
37
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 ...
- 55
1
vote
1
answer
32
views
Modeling AND of implication in integer/binary linear programming
Problem statement
Let $\beta \in \{0, 1\}$ for brevity. A set of $K$ numbers $M_k$, represented as individual bits $B_{ik} \in β $, must be distributed to a set of $ J \le K$ pairs $F_j = (c_{ij} \in ...
- 131
2
votes
1
answer
41
views
Binary program that maximizes ratio of quadratic forms
I'd like to solve the following optimization problem. Given $\mathbf a, \mathbf b \in (0, \infty)^n$, find $\mathbf x \in \{0, 1\}^n$ which maximizes
$$ f (\mathbf x) = \frac{\left( \sum\limits_{i=1}^...
- 4,877
0
votes
2
answers
66
views
Model legal shift constraints
I need your help.
My decision variable $b_{fds}$ indicates whether a fireman $f$ works shift $s$ on day $d$. I need two constraints:
a) No more than 5 consecutive working
days
b) At least 2 ...
- 3
0
votes
1
answer
50
views
How to linearize a weighted average using Pyomo?
I'm learning about linear optimization problems using Pyomo. At this time I'm looking to practice and ended up getting stuck in a constraint that contains the weighted average formula. Using this ...
0
votes
3
answers
65
views
Defining binary variable
I am currently working on my modeling skill and I wanted to try to find a linear constraint, that models a binary variable in a specific way. The new binary variable $\gamma_i$ should take the value $...
- 3
0
votes
1
answer
24
views
How to ensure an increase happens a certain interval after the last decrease in a variable?
I have three binary variables x, y, and z each indicating an increase, decrease, and stable values of another variable P. Now the issue is I want to formulate a constraint that makes sure that a y can ...
0
votes
2
answers
104
views
Modelling a shift change
I have the following problem. I am currently modeling shift schedules. There is the variable $x_{itk}$ which tells whether the cashier $i$ completes the shift $k$ on day $t$. Now I want to model the ...
0
votes
1
answer
41
views
Problems to find a suitable formulation for a constraint
I have the following problem. I would like to model the following relationship. I have three binary variables $x_1$, $x_2$ and $x_3$. These become either 0 or 1. I need a constraint for a mathemstical ...
0
votes
1
answer
60
views
How to do i prove that this inequality is valid in the given set?
How do I prove that $$z_1 + x_{12} + x_{22} + x_{13} + x_{23} + z_4 \geq 2$$
is a valid inequality for my constraints:
\begin{align}
x_{11} + x_{12} + x_{13} &\geq 1 \tag1\label1\\
x_{12} + x_{13} ...
1
vote
2
answers
111
views
Placing number blocks so that the resulting matrix is symmetric
There are some number blocks given as follows:
The aim is placing these blocks in such a way that the resulting 4X4 matrix is symmetrical. Blocks cannot be rotated, they must be used as given.
My ...
- 13
0
votes
0
answers
25
views
Find a facet for the maximum weight matching problem in a not oriented graph
Consider the problem of finding a maximum weight pairing in a graph
unoriented G = (V, E), where V is the set of its vertices and E the set of its
edges. In such a problem, we associate a weight pe to ...
- 13
3
votes
1
answer
79
views
Does a (5,3,4)-code exist?
I am a bit confused on whether a binary (5,3,4)-code exists.
As far as I am aware, this code exists if and only if a binary (4,3,3)-code exists according to Theorem 2.7 in Raymond Hill's book "A ...
- 207
1
vote
3
answers
63
views
How to model this constraint linearly in binary integer linear programming?
I have a directed acyclic graph, and two binary decision variables:
$a_{ij}$, which is equal to one when the corresponding edge between the nodes $i$ and $j$ of the graph is selected, and zero ...
- 55
0
votes
3
answers
70
views
Linear programming combination of variables
I am trying to formulate the following linear programming problem.
My inputs are the following:
A set of $N$ tables $\Pi_1, \dots, \Pi_N$
A cost budget $G$
I have the following decision variables:
$...
- 325
0
votes
1
answer
60
views
Linearizing product of binary variables
How would I linearize the following expression
$$ z = (1-x)y $$
where $x,y \in \{0,1\}$? Ideally, I would want to formulate this as a system of linear inequalities.
- 61
1
vote
1
answer
59
views
Conditional constraints in Integer Linear Programming
I think it's rather a simple question. I'm trying to construct a reduction from graph problem to ILP. When I have variables $x_1, x_2, \dots ,x_n \in \{0, 1\}$ for every vertex, can I create ...
- 37
0
votes
1
answer
40
views
Linearize Min Max Index in List as Constraint
I'm trying to solve an optimization problem by creating an optimization model (which I shall solve using CBC solver) and I need to linearize it. Please help me to reformulate it :
Given Data : A1, A2, ...
- 1
0
votes
1
answer
82
views
Triangles in a graph via LP
I have a linear program and I can't formulate the objective function and constraints.
For a graph $G = (V, E)$ we may select a set $S$ of vertices of $V$. Each vertex carries a cost $c_v > 0$ if it ...
1
vote
1
answer
79
views
Minimizing a quadratic function with binary variables and a totally unimodular constraint
Let $q=q(x_1,...,x_n)$ be a quadratic polynomial. I want to solve the following optimization problem:
$$\min_{Ax = b, x\in \{0,1\}^n}(q)$$
where $A$ is totally unimodular. Is there some neat algorithm ...
- 3,537
1
vote
0
answers
18
views
Nonlinear discrete and continuous optimization problem
I'm trying to minimize a cost function that is made up of dependent binary variables and continuous variables.
For example the cost function could look like:
$F(x_{0}, x_{1}, x_{2}, r_{0}, r_{1}) = 0....
- 111
1
vote
1
answer
168
views
How can I apply the McCormick Envelopes to the product of two binary variables?
I've seen the McCormick envelopes applied many times to the product of two continuous variables, but I can't seem to find when both of them are binaries. Also, I applied the restrictions as described ...
1
vote
0
answers
100
views
LP relaxation of ILP and the ILP have the same optimal value
I have an ILP (all variables are binary) and on several instances I’ve observed that its optimal value coincides with the LP relaxation optimal value.
The LP relaxation is not integral for fractional ...
- 21
0
votes
1
answer
31
views
About the greedy solution for a specific linear-fractional programming problem
Let $a_i>0, b_i>0, \forall i $.
The optimizing problem is
$$\max_{x_i}(\frac{\sum_{i=1}^{n}x_i a_i b_i}{\sum_{i=1}^{n}x_i b_i})$$
with constrains:
\begin{align}
x_i \in \{0,1\}\\
\sum_{i=1}^{n}...
- 129
2
votes
1
answer
94
views
How do I solve this mixed integer program?
I have a minimisation problem in the following form
$$\textrm{min}: x^TAx$$
constrained by $\sum x_i=N$
where $x$ is a vector containing only 1's and 0's, and $A$ is a square matrix of real numbers.
...
2
votes
1
answer
136
views
What is the best way to convert this into a integer linear program and what is the best way to solve such a problem?
I am studying a mixed integer program in the form
$$ \textrm{min}: \sum A x$$ constrained by $\sum x_i = N$
where $x$ is a vector containing only 1's and 0's, N is an integer, and $A$ is a square ...
- 33
2
votes
2
answers
68
views
How do I transform the following set of conditions into inequalities?
I've been working on a mixed integer linear program for quite a while now and I need to set up constraints involving binary variables. I just can't find the correct answer to the following problem. ...
- 21
2
votes
2
answers
441
views
Methods for binary linear programming
I have an LP problem (linear objective with eq and ineq constraints) in binary variables.
Except for the objective, all the coefficients are integer, mostly in {-1,0,1}. Maybe the objective coeff ...
- 253
1
vote
1
answer
19
views
Reconfiguration to find other solutions of a Binary Linear Program (NOT ILP)
Assuming we are to optimize 0-1 problem. If we've found the first solutions where multiple solutions might exists. How do we reconfigure the system (maybe through unimodular operations) inorder to ...
0
votes
0
answers
74
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
0
votes
1
answer
149
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
62
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 ...
- 239
2
votes
1
answer
52
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
66
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
49
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
92
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 ...
- 789
0
votes
1
answer
128
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
37
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
124
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{...
- 13.9k
3
votes
1
answer
88
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 ...
- 111
1
vote
1
answer
156
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
34
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,103
0
votes
1
answer
84
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,675
2
votes
1
answer
85
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 ...
- 111
1
vote
1
answer
496
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 \...
- 155
0
votes
2
answers
67
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,372
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
58
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
241
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
66
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