Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
1answer
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}$$ ...
1
vote
3answers
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$ ...
0
votes
2answers
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$ ...
3
votes
1answer
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 ...
0
votes
0answers
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:...
1
vote
2answers
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 ...
2
votes
0answers
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:...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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. ...
0
votes
1answer
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 ...
0
votes
0answers
14 views

Totally uni-modular matrix

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{...
2
votes
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 ...
2
votes
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 ...
1
vote
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} ...
1
vote
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$ ...
1
vote
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 ...
1
vote
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}...
0
votes
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,...
0
votes
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$ ...
4
votes
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 + ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
4
votes
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)...
2
votes
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, ...
0
votes
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 ...
0
votes
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}{...
1
vote
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 \...
5
votes
2answers
133 views

How to prove that this matrix is total unimodular

This matrix is total unimodular (tested by a computer program). ...
1
vote
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 ...
-3
votes
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 ...
0
votes
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?
1
vote
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)}$ $...
2
votes
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)$$ ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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$...
1
vote
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 ...
1
vote
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 \...
3
votes
0answers
38 views

NP-hardness of solving congruence equations in several variables

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 ...