Questions tagged [binary-programming]

An optimization problem in which the decision variables are binary.

Filter by
Sorted by
Tagged with
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 ...
E-O's user avatar
  • 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 ...
Astrinus's user avatar
  • 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}^...
Jon Warneke's user avatar
  • 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 ...
HulliSeb's user avatar
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 ...
Yuri Santos's user avatar
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 $...
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
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 ...
manofthousandnames's user avatar
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 ...
manofthousandnames's user avatar
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} ...
Jonathan Kerr's user avatar
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 ...
Oytunxxx's user avatar
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 ...
Wissem's user avatar
  • 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 ...
Aislin_367's user avatar
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 ...
E-O's user avatar
  • 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: $...
dkoutsou's user avatar
  • 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.
TurboChad's user avatar
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 ...
F.Hand's user avatar
  • 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, ...
maverick's user avatar
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 ...
Mark Martin's user avatar
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 ...
Kandinskij's user avatar
  • 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....
lex2763's user avatar
  • 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 ...
Rogério Rocha's user avatar
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 ...
esv's user avatar
  • 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}...
WilliamRyan's user avatar
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. ...
freshmathhead's user avatar
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 ...
testman7's user avatar
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. ...
scotch01's user avatar
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 ...
Zohar Levi's user avatar
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 ...
someone random's user avatar
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),...
Martin Vesely's user avatar
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 $\...
ljk07's user avatar
  • 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 ...
Stephen Ge's user avatar
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 ...
Tiemo's user avatar
  • 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-...
Ilya's user avatar
  • 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 ...
CorporalGiraffe's user avatar
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 ...
HARVEER RAWAT's user avatar
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 ...
novice5095's user avatar
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 $...
zzzz za's user avatar
  • 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{...
the_candyman's user avatar
  • 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 ...
Rutger's user avatar
  • 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\;...
zzzz za's user avatar
  • 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 $...
Pwaol's user avatar
  • 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 ...
user13's user avatar
  • 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 ...
Rutger's user avatar
  • 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 \...
incud's user avatar
  • 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_{...
mkultra's user avatar
  • 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 ...
parag's user avatar
  • 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 ...
parag's user avatar
  • 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 ...
hamed manshadian's user avatar
-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, ...
Heng's user avatar
  • 1

1
2 3 4 5