Questions tagged [binary-programming]

An optimization problem in which the decision variables are binary.

Filter by
Sorted by
Tagged with
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),...
user avatar
-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,...
user avatar
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-.....
user avatar
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 $\...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ~...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 $...
user avatar
  • 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{...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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\;...
user avatar
  • 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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 \...
user avatar
  • 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_{...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
-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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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}...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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.
user avatar
  • 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 ...
user avatar
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?
user avatar
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\...
user avatar
  • 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(...
user avatar
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$ ...
user avatar
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\}$. ...
user avatar
  • 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: ...
user avatar
  • 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 ...
user avatar
  • 113