Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

1
vote
4answers
83 views

Procedures to find solution to $a_1x_1+\cdots+a_nx_n = 0$

Suppose that $x_1, \dots,x_n$ are given as an input. Then we want to find $a_1,\ldots,a_n$ that satisfy $a_1x_1 + a_2x_2+a_3x_3 + a_4x_4+\cdots +a_nx_n =0$. (including the case where such $a$ set does ...
2
votes
1answer
307 views

A variation of the Assignment Problem

In the following Wikipedia article about the Assignment Problem in the Example section, it says: Similar tricks can be played in order to allow more tasks than agents, tasks to which multiple ...
1
vote
1answer
87 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 ...
7
votes
5answers
3k views

Good software for linear/integer programming

I never did any linear/integer programming so I am wondering the following two things What are some efficient free linear programming solvers? What are some efficient commercial linear programming ...
0
votes
1answer
93 views

Converting loop to a closed form expression? [duplicate]

Possible Duplicate: How to convert this loop into a closed form expression? I have the following code in Python ...
2
votes
2answers
277 views

Prove or disprove a chessboard with diagonal corners removed, cannot be tiled with L shape pieces or size 2

I think this is impossible, but I don't know how to prove an integer solution doesn't exist for a given equation. Here's my approach: First, observations: The removed tile will be of the same color. ...
0
votes
1answer
26 views

Finding the solutions of $ax+by\le D$

Given parameters $a,b,D$, all integers, I want to find all the integer solutions $(x,y)$ of $ax+by\le D$ Or at least a nice way to characterize them. Also, for a given $R$, it is actually enough for ...
2
votes
1answer
314 views

Unimodular matrix definition?

I'm a bit confused. Based on Wikipedia: In mathematics, a unimodular matrix M is a square integer matrix having determinant +1, 0 or −1. Equivalently, it is an integer matrix that is invertible ...
0
votes
0answers
50 views

How to formulate or statment in integer programming

I need to formulate below statement in integer linear programming. if x+y=2 then (a+b<c or c+g<a) Can you help me please?
7
votes
2answers
276 views

Mean and Median in a Classic River Crossing Problem

Consider the following classic problem: Four people on the west side of a river wish to use their single boat to get to the east side of a river. Each boat ride can hold at most two people, and the ...
0
votes
1answer
117 views

Approximate rational number of radical combination

Suppose that there is a radical combination $a\sqrt{b}+c\sqrt{d}$ where a,b,c,d are natural. Each term part $\sqrt{b}$ cannot be transformed into the form of $s\sqrt{q}$. The question is, 1) Suppose ...
1
vote
1answer
156 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 ...
3
votes
1answer
258 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
119 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
73 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 ...
0
votes
2answers
211 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
196 views
0
votes
1answer
102 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
465 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
143 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
81 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
374 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
249 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
266 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
234 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
75 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
225 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
169 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
837 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
454 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
164 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
343 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
188 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
293 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
266 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
155 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
118 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
191 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
259 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
191 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
226 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
427 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} ...