Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

0
votes
2answers
201 views

What is the logic to calculate triangle-inequality-theorem

So I want to know is there any simple formula to get the result for the triangle-inequality-theorem I know what is the theorem but any formula rather than doing it the routine way of adding then ...
0
votes
0answers
184 views
0
votes
1answer
100 views

How to minimize cost of group of items given that weights of item sums up to fixed value and atmost 'n' number of items are allowed?

Given that we have a set of items :- { (c1, w1) , (c2, w2), (c3, w3) , ... } where (ci, wi) are the respective cost and weight of the ith item. Its required to minimize total cost of items C such ...
1
vote
2answers
449 views

LP relaxation for ILP\IP (integer linear programming)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...
5
votes
2answers
138 views

Minimize sum of smallest and largest among integers on the real line.

Suppose there are 3 non-negative integers $x$, $y$ and $z$ on the real line. We are told that $x + y + z = 300$. Without loss of generality, assume $x$ to be the smallest integer, and $z$ to be the ...
1
vote
0answers
78 views

Problem formulation for maximizing the number of smaller rectangle inside larger rectangle

I stumble upon a problem which i would like to pose it as "Optimization Problem". Given the dimension of larger and smaller rectangle, i would like to find the maximum number of smaller rectangle ...
1
vote
2answers
337 views

$\ell_0$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min:\|x\|_0$ subject to:$Ax=b$. $\|x\|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time has ...
1
vote
0answers
215 views

sum of maxima vs the maximum of the sum

Consider the following integer program $$ \begin{align} \max &\sum\nolimits_{i,j} U_i(j)\cdot x_{i,j}\\ \text{subject to}& \sum_{i}x_{i,j}\cdot f\left(i,j\right)\leqslant c_j,& ...
1
vote
0answers
253 views

Book recommendation on Applied Integer Programming/Combinatorial Optimization/OR

Having some very basic and theoretical knowledge about these topics from my study, I'm looking for a book (or other good sources) that explains the stuff from a practical point of view. On the one ...
2
votes
1answer
220 views

Is there a formula for nCr that considers a min/max range? (restricted composition estimation)

I'm bad at math and hope I explain this right(please don't be upset if I don't, I'm not trying to be lazy or a jerk, I really don't understand what information is sometimes required and focus on the ...
3
votes
2answers
74 views

How does one find the minimum of an equation of integers?

Going through a book of probability problems and am working on the Sock Drawer Problem: A drawer contains red socks and black socks. When two socks are drawn at random, the probability that both ...
0
votes
1answer
69 views

Chaotic solutions to mixed integer linear problems

Is there a way to get the branch and bound algorithm to converge to a solution "close" to an initial value? One way I can think of, is to adding a "distance from initial value" term to the cost ...
0
votes
2answers
234 views

Minimising variance of the workload

A professor will assign research papers to his students as a partial fulfilment of the requirements of a graduate course. There are six students enrolled in the course and each student will be ...
-1
votes
1answer
206 views

How to express $y = x\ \mathrm{mod}\ 2$ as an ILP?

Using the signed modulo operation: $(x\ \mathrm{mod}\ 2) = \begin{cases} 0\ \mathrm{if}\ x\ \mathrm{is\ even} \\ 1\ \mathrm{if}\ x > 0\ \mathrm{and}\ x\ \mathrm{is\ odd} \\ -1\ \mathrm{if}\ x ...
3
votes
1answer
164 views

Efficiently solving a special integer linear programming with simple structure and known feasible solution

Consider an ILP of the following form: Minimize $\sum_{k=1}^N s_i$ where $\sum_{k=i}^j s_i \ge c_1 (j-i) + c_2 - \sum_{k=i}^j a_i$ for given constants $c_1, c_2 > 0$ and a given sequence of ...
1
vote
1answer
751 views

What are the algorithms for integer programming in which constraints are dependent?

What are some ways to deal with dependent constraints in integer programming? For example, suppose I want to maximize $x+3y+2z$ subject to (i) $x+y<=3$ and (ii) if $y+z>=2$ then $x+z<=6$. ...
0
votes
2answers
439 views

How many different Pairs are there?

Consider, F4(y) = the number of digits 4 in decimal representation of the positive integer y and F7(y)=the number of digits '7' in decimal representation of the positive integer y. For the given ...
1
vote
0answers
162 views

Optimization via Simulation

I want to minimize and objective function $\hat{B_i}$ $i\in l$, which can be computed by a matlab code (assume $\operatorname{findB}(a, b, c)$ returns $B$. I have the following optimization problem: ...
3
votes
1answer
329 views

Connected graph solution from IP/LP

I have a problem on a graph (of maximum degree $c$) which looks for a connected subset of edges fulfilling some properties. I have problems formulating the connectedness condition in an IP/LP. The ...
2
votes
3answers
178 views

Linear inequalities to make a specific solution infeasible

Say we have a binary linear programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x}}{\text{minimize}} & & c\cdot\mathbf{x} \\ & \text{subject to} & ...
0
votes
1answer
287 views

Binary Integer Programming Problem II

I need to schedule shifts in $p$ workplaces over $T$ days for $n$ workers. And I must do it in such a way that all workers work about the same amount of time over the $T$ days, and so that each ...
0
votes
1answer
262 views

Binary Integer Programming Problem

Below I need solve for the binary variables $x_1,x_2,y_1,y_2,z_1,z_2$ that minimize the functions $f(x), f(y), f(z)$, subject to the 5 constraints that follow. By binary I mean they can only be 1 or ...
1
vote
0answers
148 views

Modeling propositional formulas in integer programming

Say I have an binary integer programming problem: \begin{equation*} \begin{aligned} & \underset{\mathbf{x,y}}{\text{minimize}} & & f_0(\mathbf{x,y}) \\ & \text{subject to} & ...
2
votes
0answers
116 views

An optimization problem involving Latin Squares

Let $C$ be a given $n \times n$ matrix of real numbers and let $p$ be a given $n$ vector of non-negative numbers such that wlog $\sum_i p_i = 1$ and wlog the $p_i$ are non-increasing. I'll write ...
1
vote
2answers
182 views

Looking for a closed form to determine whether a symbol is part of the ith combination nCr

Hi I'm new to this, feel free to correct or edit anything if I haven't done something properly. This is a programming problem I'm having and finding a closed form instead of looping would help a lot. ...
2
votes
3answers
2k views

Double summation

I'm currently solving some Operations Research exercises related to Integer Programming. In one of the solutions of the exercises the author uses the following formula for the objective function: ...
3
votes
2answers
256 views

For a fixed positive integer n, show that the determinant below is divisible by n

For a fixed positive integer n, if $D = \left|\begin{array}{ccc} n! & (n + 1)! & (n + 2)! \\ (n + 1)! & (n + 2)! & (n + 3)! \\ (n + 2)! & (n + 3)! & (n + 4)! ...
1
vote
1answer
187 views

Combinatorial Optimization Problem (can I/how do I solve this with integer programming?)

Inputs: 1) A set of M x N matrices, {A,B,C...N} containing only integers. 2) A single 1 x N matrix of floats, W (weights). I need to pull one row from each input matrix and sum values for each ...
2
votes
1answer
223 views

Solving a knapsack-type problem

I'd like a good way to solve an optimization problem I came across. It's a constrained knapsack problem: I want to find integers $$1=a_1\le a_2\le\cdots\le a_t$$ $$a_1+a_2+\cdots+a_t=N$$ with $t$ ...
1
vote
1answer
422 views

Optimizing Nonlinear Constraint Equations with Discrete Variables and Multiple Objective Functions

I have the following constraint functions: $$g_{i_{min}} \leq y_{i+1}-y_{i} \leq g_{i_{max}}$$ $$y_{i_{max}}-y_{i} \geq h_{i}$$ $$v_{i_{min}} \leq \Biggl[\frac{(y_{i+1}-y_{i})^{3} ...