Tagged Questions

Questions on optimization constrained to integer variables.

100 views

Binary integer program with nonlinear function

I have given a matrix $A^{m \times n}$ and I am looking for a submatrix $B^{m \times k}$ for a given $k$ that maximizes the following expression: $$\sum_{i=1}^m \max_{j \in \{1 \dots k\}} B_{i,j}$$ ...
59 views

Mixed Integer Linear Programming Conditional Constraints

I have a set of variables: $x_1,x_2,x_3,x_4$ $x_1$ is a binary integer variable while the rest are real numbers all between 0 and 1 I want a constraint such that: if $x_2+x_3+x_4$>0 then $x_1=1$ ...
33 views

Integer Programming Conditional Constraints

I have a set of integer [0,1]variables $x_1,y_1,x_2,y_2,x_3,y_3,x_4,y_4$ I want a conditional constraint such that if any of the $x$ variables is equal to 1, I want the sum of the subsequent $y$ ...
158 views

Linear constraints to placing N queens on an N x N chessboard?

I'm trying to formulate the problem of placing N queens on an N x N chessboard such that no two queens share any row, column, or diagonal. I managed to define my decision variable as x[n][n], a ...
69 views

Hungarian Method algorithm question. Dual solution.

I have included two images which I have to prove the next problem. The first image is the alternate(k) algorithm (alternate paths algorithm) and the second is the Hungarian Method algorithm. Question:...
47 views

How can I maximize this expression?

Let $d_1,...,d_n$ be non-negative integers such that $d_1 + ... + d_n = n -1$ and $d_{i} \leq i$. What is the value of the following expression: $\sum_{i=1}^n d_i (n - i)$ when maximized (a good ...
36 views

Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t$$ subject to:...
13 views

Definition of support of a nonzero vector

I am studying integer programming and specifically Graver Basis and Circuits. However, to define a circuit they use the term of support of a non zero vector $supp(c)$ and say it is minimal. Does ...
130 views

Linear programming. Find the maximum number of vertex disjoint paths in a directed graph.

How I can write like an objective function subject to its corresponding restriccions the next problem? (max "...") subject to ($\sum "..." - \sum "..."=0$ $\forall$ "...") I have a directed graph ...
24 views

The cost function in the Weighted Bipartite Matching Problem (a.k.a the Assignment Problem)

In the definition of this problem, the weight/cost function generally takes value in $\mathbb{Z}$ (or sometimes $\mathbb{Q}$). This is what I observed from some books (e.g. "Combinatorial ...
30 views

Beyond quadratic in binary integer programming

If I have an integer programming problem with binary decision variables in a quadratic objective function with quadratic constraints, I can solve it using branch and bound in a few different solvers. ...
22 views

Integer Programming Problem - Machines To Products

A man is trying to decide how he can assign his five machines to four products in order to maximize output. The estimated output per day for each machine is shown and reflect its productivity for each ...
I encountered the following matrix and am wondering whether it is totally uni-modular or not: $$\begin{bmatrix} A_{n\times m} & 0_{n\times m}\\ I_{n\times m} & I_{n\times m}\\ \end{... 2answers 81 views Linear Programming Model (or IP) - Staff Allocation A retailer is trying to decide how best to assign its 3 staff to two internal departments in order to maximize sales. The estimated sales revenues per day for each staff member are shown and reflect ... 0answers 72 views Approximate algorithms for integer linear programming (for optimal subset selection) I'm trying to select an optimal subset of some items. I've tried 2 optimal approaches (branch-and-bound and integer programming) but both proved impossible for the size of the problem. I'm wondering ... 1answer 29 views How to increase the lower bound on possible counter-examples to the Collatz Conjecture? According to Wikipedia, all positive integers up to 2^{60} have been tested and follow the Collatz Conjecture. This got me thinking, could one write a program that tests integers of the form 2^{60} ... 0answers 24 views Social welfare convergence in large assignment problems with random utilities Suppose there are N agents each to be assigned one of N objects. The utility an agent gets for a particular object is drawn uniformly, i.i.d., from the set of integers between 0 and 100 ... 1answer 25 views Optimization of a colour graph Formulate as a discrete optimization problem: Label each node of the graph with a different non negative integer number, in such a way that the numbers of the nodes of each path composed of the same ... 1answer 59 views Defining an integer (binary) linear program to solve a logistics problem As an analogy, lets say I have k buckets and n items I want to put into these buckets. So we have binary variables x_{ij} (1 \leq i \leq n, 1 \leq j \leq k), whether or not we put the i^{th}... 2answers 219 views Binary integer LP problem Joe Henderson runs a small metal parts shop. The shop contains three machines – a drill press, a lathe, and a grinder. Joe has three operators, each certified to work on all three machines. However,... 1answer 119 views Formulation of mutually exclusive condition So I have two integer variable and they can be one of the following x=0, y=1 x=1, y=0 x=2, y=0 how can I formulate this as an integer program? I've gotten x + y \le 2 and y \le 1 ... 0answers 131 views ax+by+cz<=d, find the maximum value of ax+by+cz. I am recently calculating that kind of questions as shown in title. And of course, I use a lot of time to find the answer. Therefore I would like to know how I can calculate faster. Q.: ax + by + ... 0answers 15 views Adding an upper bound increases the number of branching nodes I am solving a maximization problem by means of integer programming and have observed the following curiosity: When I add an upper bound in the input for the solver (an upper bound that is tighter ... 0answers 21 views Integer programming - multi-set partitioning I'm trying to solve this question: Let S be a multi-set of n integers, can S be partitioned into two sub-multi-sets S1,S2, such that:$$ \sum_{x \in S1} x = \sum_{y \in S2} y $$I'm trying to ... 0answers 27 views How to determine the smallest N such that there are X (or more) prime numbers with exactly N bits? I understand how I can use the prime number theorem to determine how many primes exist for a given bit length: \pi(2^n)-\pi(2^{n-1}). However, my specific problem is that I need to approach this ... 1answer 47 views Zero-one linear programming with substitutable constraints Suppose x_1, x_2, \ldots, x_n each take values zero or one and we want to solve the following linear programming problem:$$ \min_{x_1,x_2,\ldots, x_n} f(x_1,x_2,\ldots,x_n) $$subject to a bunch ... 1answer 149 views How can linearize the product of decision variables in ILP? Here, we have something like this: R + (1-R)T + (1-R)(1-T)S + (1-R)(1-T)(1-S)Q = 1 where R, T, S, Q are binary decision variable How can I convert this ... 1answer 35 views 01-integer programming can someone please explain to me what is meant by easily converting negative objective function coefficients? This may seem like a restrictive set of conditions, but many problems are easy to ... 0answers 64 views Find all answers to a Mixed-Integer-Linear-Program using branch and bound? I am trying to solve a MILP which might have multiple answers (all give the same value for objective function). Is a branch and bound based algorithm able to find all solutions? Is it possible to ... 1answer 322 views Why calculating XOR of consecutive values can be simplified? [duplicate] I was trying to calculate integer xor of 0..n. I named the function xored(n). Note that in examples below ^ does not mean power but integer xor (like in C or Java language) So, xored(0) = 0, xored(1)... 1answer 80 views Prove that this matrix is total unimodular Is there an easy way to prove that this matrix is total unimodular ?$$ \begin{bmatrix} 1 & F_1 & 0\\ 1 & 0 & F^T_1 \\ 0 & F_2 \end{bmatrix} $$1 is the identity matrix, ... 1answer 19 views Lattice points in simplices - reference request I found this paper http://homepages.math.uic.edu/~yau/35%20publications/An%20upper.pdf which, in formulas (1.2) and (1.3), relates the number of non-negative and positive integer values that are ... 1answer 32 views Integer Points in Simplex Let$$A_w(d,q):=\left\{{\bf k} \in \mathbb{N}_0^d: \sum_{j=1}^d w_j k_j \leq q\right\}$$denote the number of non-negative integer points in the \ell_1-ellipse with semi-axes of length \frac{q}{... 0answers 33 views Understanding ILP formulations of combinatorial optimisation problems I am having trouble understanding and producing integer linear programming formulations for combinatorial optimisation problems. I can understand basic ones like the knapsack problem: min \quad \... 2answers 133 views How to prove that this matrix is total unimodular This matrix is total unimodular (tested by a computer program). ... 1answer 74 views How many solutions does a LP problem with the graphical method have? are following statements correct: 1) when solving an LP problem with the graphical method and the acceptable range is bounded. Then there is always a unique solution. in addition, the unique ... 1answer 58 views Linear/Integer programming for discrete mathematicians I am primarily a discrete mathematician (designs/finite geometries), and I've been using Gurobi to solve some integer programming problems related to my research. While I'm comfortable using the ... 1answer 31 views The number of solutions of a binary integer programming problem A 0-1 linear programming problem with three variables can have at most 3! = 6 acceptable solutions? Is this right or wrong? 0answers 26 views Optimization formulation for a dynamic system. Constructing constraints for a problem. I am trying to formulate a problem that goes the following Min f(.) This is a generalized objective function. Subject to, x_{i}^{(t+1)} = x_{i}^{(t)} + r_{i}^{(t)} - x_{i}^{(t)}z_{i}^{(t)} ... 1answer 69 views Integer programming: if a or b then a, b, and c I'm writing a mixed integer programming (MIP) constraint where my \color{blue}{\texttt{binary variables}} are a, b, and c to meet the following condition:$$ (a \lor b) \to (a \land b \land c)$$... 1answer 55 views When exactly are quadratic objective functions polynomial time solvable I'm considering quadratic programming problems of the form:$$ \max x^tQx+Bx$$subject to the linear constraint$$ Ax \le b $$I read that if is the case that$$ x^tQx + Bx \ge 0 \ \forall x$$or ... 0answers 53 views Optimization problem shortest path distance and critical node detection problem (interdiction). I am trying to formulate this optimization problem, max d_{ij} where d_{ij} is the shortest distance between active nodes i and j. However my problem is connecting my decision variable with the ... 1answer 25 views Why should the matrix A in an ILP be integer? Almost everywhere I read about integer linear programming (ILP), I found that the matrix has to be integer (by definition). More precisely, an ILP is defined as follows: An ILP in canonical form is ... 1answer 96 views Prerequisite reading for Concrete Mathematics? [closed] I'm a freshman computer science major who has just started reading Concrete Mathematics, mathematics for computer science. Is there any prerequisite reading or learning I should do before embarking on ... 2answers 53 views Transportation: Minimizing Cost I am trying to solve this problem, but I have had no luck. I have tried to set this up in MS Excel, so I could use Solver to find the solution, but I don't really know how to form this problem. As far ... 1answer 62 views Binary Integer Programming I need to form teams. There are 8 projects and 60 students. Each project has different requirements. For example, out of 5 total requirements, project 1 has 2 requirements: must have a programmer and ... 2answers 61 views Eliminating non-integer solutions to ab / (2\sqrt{ab} + a + b) I am writing a program to output all a,b \in \mathbb{N}, where a \le b \le n (for a given n \in \mathbb{N}), such that$$ \frac{ab}{2\sqrt{ab}+a+b}=c\in \mathbb{N} $$For example, a=9, b=36... 1answer 46 views Finding grid nodes a line passes through For 2D grid pathfinding, I want to do a quick broadphase to check if there is a direct path from the start to the target by conceptually checking all nodes touching the line segment formed by ... 0answers 30 views CPLEX solver on a standard vertex coloring problem I have a very straightforward ILP model of vertex coloring that I'm trying to solve with CPLEX. With a binary variable x_{vc} for every (v,c) \in \{ V \times C\} there is a constraint$$ \sum_{c \...
You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): \beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l ...