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 ...
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, ...
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 ...
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
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 ...
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 ...
1
vote
0answers
17 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
1answer
39 views

How to prove that this matrix is total unimodular

This matrix is total unimodular (tested by a computer program). ...
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 ...
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
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 ...
3
votes
0answers
22 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
63 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
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$ ...
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. ...
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 ...
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 ...
1
vote
1answer
78 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
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} ...
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
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 ...
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 ...
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 ...
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)$. $$ ...
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) ]) ...
1
vote
0answers
18 views

Linear Integer Optimzation Problem (scheduling problem)

Does any of you know how to get this done?
4
votes
1answer
49 views

Is the optimal solution of a strictly convex function over $\mathbb{Z}^d$ a rounded version of its optimal solution over $\mathbb{R}^d$

Consider a strictly convex function $f: \mathbb{R}^d \rightarrow \mathbb{R}$. Let $x^* = \min_{\mathbb{R}^d} f(x)$ denote the (unique) minimum of this function over $\mathbb{R}^d$. Similarly, let ...
0
votes
1answer
67 views

convertion into integer linear program

I am trying to model the Ising spin state problem into Integer linear program and find the optimal ground state using lp_solve. (This is just a miniature version of Ising state problem) $$ maximise: ...
1
vote
1answer
14 views

How to think about minors of the rectangular matrix in the context of a system of Diophantine linear equations

My question is related to my previous question How to prove existence of solutions to the system of Diophantine linear equations. In particular, to the theorem which I've used to prove some subset of ...
1
vote
1answer
67 views

Can you generate math problems that are solveable?

If you take Linear Programming, it problems are formulated like this: You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. ...
1
vote
2answers
41 views

Fog of War Influence Map

I'm in the process of making an RTS game and I've ran into a problem I could use help with. I want to create a fog of war system that reveals an area around a unit that belongs to you like how it's ...
0
votes
1answer
22 views

Replacing a max constraint in a binary program

For $x \in \{0,1\}$, I want to express $x = 1 \Leftrightarrow \exists k: y_k = 2$ where $y_k \in \{0,1,2\}$, i.e. $x \leq 0.5\max_k\{y_k\}$ using binary decision variables but I can't figure out how ...