Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
1answer
29 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 ...
2
votes
2answers
406 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
0
votes
0answers
35 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 ...
3
votes
0answers
21 views

Why calculating XOR of consecutive values can be simplified?

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, ...
1
vote
1answer
291 views

Linear Integer Programming: consecutive/adjacent variables constraint

Given a set of binary variables $x_{ij} \in X,\ i=0,..,N,\ j=0,..,M$ how do I model an adjacency constraint on $i$'s such that: $\sum_i^N\sum_j^Mx_{ij} = \alpha, \;\text{with }\ 0 < \alpha < ...
2
votes
0answers
25 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
0answers
12 views

Conversion of network-like matrix

I have given a network in the following form (Example): x1 + x2 - x3 = 0 x3 + x4 - x5 = 0 x5 + x6 - x7 = 0 where = is something like a node, where flow needs to ...
0
votes
1answer
27 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 ...
0
votes
1answer
16 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 ...
1
vote
0answers
18 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 ...
1
vote
1answer
34 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 ...
5
votes
1answer
39 views

How to prove that this matrix is total unimodular

This matrix is total unimodular (tested by a computer program). ...
0
votes
1answer
24 views

Linear/Integer programming reference request

There are a few other similar questions out there, but I think mine is not a duplicate because I am looking for a different kind of references than most people. I am primarily a discrete ...
0
votes
1answer
23 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
11 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
50 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
0answers
28 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
1answer
388 views

general formula for an orthogonal projection of a point onto a line

Could someone confirm this or correct the mistakes because this seems somehow wrong although I double checked it. $(m_x,m_y)$ are coordinates of a point , $(p_x,p_y),(k_x,k_y)$ are coordinates of a ...
0
votes
0answers
18 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
18 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
58 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
31 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
50 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 ...
0
votes
2answers
40 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
19 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
14 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
9 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 ...
2
votes
3answers
168 views

Is there any methods to solve for integer solution of a quadratic equation like $ax^2 + bx + c = 0$

Is there any method to solve for integer solution of a quadratic equation like following: $$ax^2 + bx + c = 0$$ where $a, b, c \in \mathbb{Z}$ If not is it possible for the Special case: ? $$x^2 -x ...
0
votes
1answer
64 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 ...
3
votes
0answers
23 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 ...
2
votes
2answers
78 views

How to find nonnegative solutions of a linear system?

I have a $M$ equation and $N$ variables like this : $ \begin{bmatrix} 3 & 0 & 1 & 0 & -1 & -3 & 2\\ 1 & 2 & 0 & 4 & 0 & 0 & -1\\ 1 & 1 & 0 ...
1
vote
1answer
41 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
22 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
31 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$ ...
2
votes
1answer
53 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 ...
1
vote
1answer
79 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 ...
1
vote
1answer
67 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. ...
0
votes
1answer
78 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} ...
2
votes
1answer
72 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
21 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 ...
0
votes
1answer
31 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
2answers
104 views

Linear programming: expressing the fact that precisely $k$ variables are nonzero

Given some variables $x_1,\ldots,x_n$ is it possible to somehow express in a linear program the fact that precisely $k$ of them are non-zero? I suspect this would already be enough to simulate ...
2
votes
1answer
58 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 ...
1
vote
0answers
18 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 ...
1
vote
0answers
185 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Is is possible to describe, and locate efficiently, the maxima of the function below in the parameters $\mathbf{x}$ $$\sum_{i} p_i \log( N + \sum_j x_j[B_j +(A_j-B_j)\delta_{ij} + min(A_j,B_j) ]) ...
0
votes
0answers
33 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
42 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 ...
3
votes
0answers
153 views

Binary optimization

Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows: There are ...
0
votes
0answers
10 views

optimization of formulas involving binomial coefficients

I encountered such a problem. We need to find the min value and max value of $f(x,y)$. $x$ and $y$ are integers $\in[0,n]\times[0,n]$ and $(x,y)\neq (0,0)$ or $(n,n)$. $$ ...