Skip to main content

Questions tagged [binary-programming]

An optimization problem in which the decision variables are binary.

Filter by
Sorted by
Tagged with
1 vote
0 answers
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 ...
Disciple's user avatar
  • 305
0 votes
0 answers
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 ...
QZDBX's user avatar
  • 1
1 vote
1 answer
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 ...
BunnyPancake's user avatar
1 vote
1 answer
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} \...
Shengzhi Lai's user avatar
0 votes
1 answer
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 ...
Shengzhi Lai's user avatar
2 votes
2 answers
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 ...
Sergio Morales's user avatar
1 vote
1 answer
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 ...
occasional's user avatar
0 votes
0 answers
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 ...
mNugget's user avatar
  • 511
-1 votes
1 answer
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 ...
Yeb02's user avatar
  • 11
0 votes
1 answer
24 views

How to linearize or reformulate an implication constraint that implies that a decision variable belong to an interval?

I am an electrical engineer who is working in computer network and I need to model my delay with respect to a binary variable $x$ as folow $\left\{ {\begin{array}{*{20}{c}} {x = 1 \Rightarrow \left( {...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
65 views

Solving an SAT problem with objective

I have 8192 bits, denoted $b_0, b_1, ..., b_{8191}$. The bits are subject to some XOR constraints (e.g. $b_0 \oplus b_3 \oplus b_{42} \oplus \cdots \oplus b_{8191} = 1$). The objective function to be ...
nalzok's user avatar
  • 836
1 vote
1 answer
68 views

Formulation of an integer linear programming problem

I want to formulate the following problem in an integer linear programming problem: We have $n$ elements $m_1,\dots, m_n$ elements with $m_i = (m_i^1, \dots, m_i^p) \in \mathbb{R}_{\geq 0}^p$ for all $...
Ferdi 17's user avatar
0 votes
1 answer
48 views

Constraint Integer Linear Programming

I have an integer linear programming problem where i want to maximize over $\{0,1\}^n$, so i have the problem $$\max_{x \in \mathbb{R}^n}c^Tx, \text{ subject to } x_i \in \{0,1\} \text{ for all } i ...
Ferdi 17's user avatar
0 votes
1 answer
61 views

Counting the number of binary solutions to system of equations by finding the coefficient of a term in a generating function

I am trying to solve the number of binary solutions to a system of linear equations, the same as in this question: number of binary solutions under linear restrictions. Shortly: Consider $ x1,…,x_n ∈ ...
Ilmard's user avatar
  • 3
0 votes
0 answers
28 views

Outer approximation algorithm for non-convex integer nonlinear program

Consider a particular non-convex binary nonlinear problem of the following form: $$ \min_X f(X) \\ \text{s.t. } X = (x_1, \ldots, x_L)^T \in \{0, 1\}^{L \times V } \\ \sum_{j=1}^V X_{ij} = \sum_{j=1}...
Jacques's user avatar
  • 23
0 votes
1 answer
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 ...
Thijssie3032's user avatar
2 votes
2 answers
180 views

How to reformulate or linearize the phrase "become redundant" or "not needed"?

I am an electrical engineer and currently I have to deal with an optimization problem with a very specific requirement: $\begin{array}{*{20}{c}} {\mathop {Min}\limits_x }&{f\left( x \right)}\\ {{...
Tuong Nguyen Minh's user avatar
0 votes
2 answers
92 views

How to linearize If-then constraint in linear programming?

I have the following decision variables: $a_i, x_i^t$ and $x_i^0$ are binary variables. I want to realize the following four conditions: if $a_i = 1, \sum_{t=0}^n x_i^t = 0$, then $x_i^0 = 0$; if $...
Long's user avatar
  • 1
1 vote
1 answer
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 ...
E-O's user avatar
  • 99
1 vote
1 answer
45 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 ...
Astrinus's user avatar
  • 131
2 votes
1 answer
65 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}^...
Jon Warneke's user avatar
  • 4,937
0 votes
2 answers
68 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 ...
HulliSeb's user avatar
0 votes
1 answer
132 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 ...
Yuri Santos's user avatar
0 votes
3 answers
70 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 $...
HulliSeb's user avatar
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 ...
Jubeyer Rahman's user avatar
0 votes
2 answers
114 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 ...
manofthousandnames's user avatar
0 votes
1 answer
47 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 ...
manofthousandnames's user avatar
0 votes
1 answer
85 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} ...
Jonathan Kerr's user avatar
1 vote
2 answers
135 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 $4\times 4$ matrix is symmetrical. Blocks cannot be rotated, they must be used as given....
Oytunxxx's user avatar
3 votes
1 answer
149 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 ...
am567's user avatar
  • 319
1 vote
3 answers
94 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 ...
E-O's user avatar
  • 99
0 votes
3 answers
99 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: $...
dkoutsou's user avatar
  • 345
0 votes
1 answer
119 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.
TurboChad's user avatar
1 vote
1 answer
76 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 ...
F.Hand's user avatar
  • 37
0 votes
1 answer
69 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, ...
maverick's user avatar
0 votes
1 answer
140 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 ...
Mark Martin's user avatar
1 vote
1 answer
126 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 ...
Kandinskij's user avatar
  • 3,536
1 vote
0 answers
23 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....
lex2763's user avatar
  • 111
1 vote
1 answer
336 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 ...
Rogério Rocha's user avatar
1 vote
0 answers
339 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 ...
esv's user avatar
  • 21
0 votes
1 answer
33 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}...
WilliamRyan's user avatar
2 votes
1 answer
107 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. ...
freshmathhead's user avatar
2 votes
1 answer
199 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 ...
testman7's user avatar
2 votes
2 answers
87 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. ...
scotch01's user avatar
3 votes
2 answers
847 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 ...
Zohar Levi's user avatar
1 vote
1 answer
23 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 ...
someone random's user avatar
0 votes
1 answer
120 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),...
Martin Vesely's user avatar
0 votes
1 answer
194 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 $\...
ljk07's user avatar
  • 103
0 votes
1 answer
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, \begin{equation} \max_{x\in\{1,0\}} c^\top x \end{equation} and for constraints, I need all ...
Stephen Ge's user avatar
2 votes
1 answer
62 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 ...
Tiemo's user avatar
  • 23

1
2 3 4 5