Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
1answer
24 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
28 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 ...
0
votes
2answers
95 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. ...
0
votes
1answer
49 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
102 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
14 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
17 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
26 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
41 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
93 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
32 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
57 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
133 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, ...
2
votes
1answer
60 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
31 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 ...
1
vote
0answers
26 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
97 views

How to prove that this matrix is total unimodular

This matrix is total unimodular (tested by a computer program). ...
1
vote
1answer
58 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 ...
-2
votes
1answer
50 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
29 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
24 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
67 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
51 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
41 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
21 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
82 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
42 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
60 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
56 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$, ...
1
vote
1answer
36 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
24 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 ...
0
votes
0answers
14 views

Gomory's cut typical running time until the constraint is fractional

I was considering the following problem. Say we are given an linear programming problem $$ \max c^Tx $$ $$ Ax \le b $$ $$ x \ge 0$$ Where instead I consider $i^{th}$ the optimal solution $X_i$ of ...
3
votes
0answers
31 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 ...
0
votes
1answer
189 views

How to linearize this constraint a summation of a product of a integer with a binary

I have to linearize the following constraint, $$ \sum_{i \in V_C} \sum_{j \in V} \sum_{k \in K} y_{ik} \cdot x_{ijk\ell} \leq I_\ell \qquad \forall \ell \in V_D $$ where $y$ is a integer variable ...
1
vote
1answer
52 views

Operations Resarch Optimal Scheduling

Consider the following problem: A car manufacturing company needs to transport car frames, which are $10$ cubic units each, and wheels, which are $2$ cubic units each, across the Atlantic ocean. ...
0
votes
0answers
27 views

(Proving NP Hardness) Maximizing ratio of polynomials

I have a function $\prod_{i = 1}^N \alpha_i$ $\alpha_i = \displaystyle \frac{(\sum_{j = 1}^{M} R_j x_j I_i(j))^2}{\sum_{j = 1}^{M} R_j x_j}$ The variables are $x_j$s, and $R_j$s are some positive ...
0
votes
1answer
39 views

minimising quadratic function subject to integer solutions

I would appreciate if one could help me to solve this problem. I have a bivariate quadratic function: $$ f(a_1,a_2)=(1-u_1^2)a_1^2 +(1-u_2^2)a_2^2 -2u_1u_2a_1a_2 $$ where $u_1^2+u_2^2=1$ and $a_1$ ...
1
vote
1answer
166 views

Solving an integer linear programming problem without a graph

I am new to linear prorgramming and so far I have been solving LP problems with the help of a graph solution. However, when there are more than 2 variables obviously I can't plot them on the graph. ...
2
votes
1answer
68 views

Chocolatier sampler boxes problem: applying goal programming and mixed-integer programing to optimally compromise goals.

QUESTION: A boutique chocolatier is planning to make a number of sampler boxes, each containing $36$ chocolates. (Therefore the total number of chocolates should be divisible by $36$.) The ...
2
votes
1answer
83 views

Help with Math software (macaulay 2)

I just started working with Macaulay 2 and need some help. I need to find the number of solutions of a system of equations. I am having difficulty imputing this into the software so please be specific ...
1
vote
0answers
28 views

Binary depending on the sign of another variable

I'm writing a mixed integer linear problem, where I have an indicator function in the objective function counting the instances of negative values of a decision variable. I thought of defining a ...
1
vote
0answers
22 views

Book recommendation on integer programming ? (in order to solve a set cover problem)

I'm trying to solve a set cover problem. To put it shortly, my problem is about covering a $N \times M$ grid, by using various rectangles which have associated cost depending on their shape and ...
1
vote
1answer
221 views

How do I convert a constraint with a product of two integer variables to a linear constraint?

I have a constraint of the form: $$\theta \leq a_1x_1 + a_2x_2 + a_3x_1x_2$$ where, $x_1$ and $x_2$ are integer variables with ranges $x_1 \in \{0, m\}$ and $x_2 \in \{0, n\}$. I would want to ...
0
votes
1answer
84 views

How to solve the coupled integer programming problem?

I have the following integer linear programming problem: $$\begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} && \sum_{k=1}^K\sum_{t=1}^Tx_{kt} \\ & \text{subject to} ...
0
votes
1answer
46 views

Solution of the LP relaxation - always round to the nearest integer?

If an optimal solution to the LP relaxation of an IP is not integer, can we always get a feasible IP solution by rounding it to the nearest integer? Or can we generalize this process by saying, if we ...
1
vote
0answers
22 views

Is there any general algorithm to solve such a 3D cutting problem?

Suppose a cuboid $\mathbb{A}$ has $L$,$M$ and $N$ as its length, width and height respectively, where $L\ge{M}\ge{N}>0$; Now we want to cut $\mathbb{A}$ into smaller cuboids with length $x$, width ...
2
votes
1answer
62 views

On/off variables in MILPs with infinite bounds

I have an LP defined by $$A x = b$$ $$0 \leq x \leq U$$ and would like to extend it to an MILP through introduction of binary on/off variables $z$ such that $$z_i = 0 \implies x_i = 0.$$ This ...
0
votes
0answers
44 views

minimising multivariate quadratic function over integer variables

I have a quadratic function $x_1^2+x_2^2-(u_1x_1+u_2x_2)^2$ which I need to minimise over integer $x_1$ and $x_2$; also, the coefficients $u_1,u_2<1$. In other word, assuming coefficients ...
-1
votes
1answer
115 views

Linear Programming constraint equivalent of conditional

I would like to use the following conditional in my linear program: if(A == 1) then B = C + 1 A = binary, B and C are continuous. In the else case, any relation ...