Questions on optimization constrained to integer variables.
1
vote
1answer
91 views
way of converting an approximate rational number of radical combination into original form
Suppose that there is a radical combination $a\sqrt{b}+c\sqrt{d} ...$. where $a,b,c,d\in \mathbb{N}$, for which each term part $\sqrt{b}$ cannot be transformed into the form of $s\sqrt{q}$.
The ...
2
votes
1answer
109 views
Determining Weights of Columns For A Prioritization Matrix
I'm trying to calculate the weight of various tasks. I have tasks that are daily, weekly, monthly, yearly. As a task gets closer to due date, I'd like it to be more important. For example, a weekly ...
1
vote
1answer
106 views
For integers $a$ and $b \gt 0$, and $n^2$ a sum of two square integers, does this strategy find the largest integer $x | x^2 \lt n^2(a^2 + b^2)$?
Here is some background information on the problem I am trying to solve. I start with the following equation:
$n^2(a^2 + b^2) = x^2 + y^2$, where $n, a, b, x, y \in \mathbb Z$, and $a \ge b \gt 0$, ...
1
vote
2answers
47 views
What's the relation between the non-convex sets and the hardness of ILP problems?
If some or all of the unknown variables are required to be integers,
then the problem is called an integer programming (IP) or integer
linear programming (ILP) problem.
If understand ...
2
votes
0answers
71 views
Branch-and-Price algorithms for IP/MIP
I'm trying to do research into Branch-and-Price algorithms, which generally rely on Branch-and-Bound and column generation (typically Dantzig-Wolfe decomposition) to solve integer and mixed-integer ...
0
votes
2answers
110 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
95 views
Is it possible to linearize the non-linear equation in this linear programming?
Have typed the question is latex format, here it is:
0
votes
1answer
81 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
1answer
200 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 ...
0
votes
0answers
37 views
A. Kaufman “Methods and Models of Operations Research”
There're 3 volumes (at least) of "Methods and Models of Operations Research" written by A. Kaufmann. So far I've found only first, called "Methods and Models of Operations Research", published in ...
5
votes
2answers
109 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
57 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
1answer
144 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
117 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
151 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 ...
0
votes
1answer
125 views
How time consuming is this integer optimization problem? [closed]
Minimize $x$ subject to:
$$\tag 1x^2 - Dy^2 =1$$
$$\tag 2 x,y>0$$
$$\tag 3 x,y\in \Bbb Z$$
$$\tag 4 2<D\leqslant 1000$$ (except when D is square)
I am playing with Project Euler and trying ...
2
votes
1answer
141 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
61 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
56 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
206 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
94 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
129 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
276 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
286 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
125 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
170 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
133 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
219 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
216 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
128 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
94 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
1answer
116 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.
...
1
vote
3answers
801 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
236 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
138 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
181 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
361 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} ...
