# Tagged Questions

Questions on optimization constrained to integer variables.

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 ...
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? ...
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 ...
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, ...
291 views

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

### How to prove that this matrix is total unimodular

This matrix is total unimodular (tested by a computer program). ...
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 ...
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?
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)}$ ...
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)$$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$, ...
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 ...
14 views

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

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