Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

11
votes
0answers
212 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
4
votes
0answers
87 views

How to minimize $\min_k k \frac{b^k/n}{\lfloor b^k/n \rfloor}$

This problem looks familiar, but I don't remember its solution: $$ \min_k \ \ \frac{b^k/n}{\lfloor b^k/n \rfloor}k $$ subject to $$ b^k \ge n \\ b,n,k \in \mathbb{N} $$ Does it have a name? What's ...
4
votes
0answers
163 views

On the integer feasibility of polytopes defined by idempotent integer matrices

EDIT: I realized that while writing this question, I was reasoning about orthogonal projections. Thus, I forgot to transpose when forming the projection on to the space orthogonal to the image of $P$. ...
3
votes
0answers
128 views

Binary optimization

Let me first make my background clear. I am a PhD student with not much knowledge in optimization but I need to do some optimization as a part of my research work. My problem is as follows: There are ...
2
votes
0answers
20 views

What decides the structure of the dual variables taken in designing min-max type combinatorial optimization algorithms?

There are a bunch of combinatorial optimization problems like min cost flows and min weight perfect matchings that invoke duality and complimentary slackness to improve the primal feasible solution. ...
2
votes
0answers
51 views

How to find nonnegative solutions of a linear system?

I have a $M$ equation and $N$ variables like this : $ \begin{bmatrix} 3 & 0 & 1 & 0 & -1 & -3 & 2\\ 1 & 2 & 0 & 4 & 0 & 0 & -1\\ 1 & 1 & 0 ...
2
votes
0answers
62 views

Algorithm to reduce expressions to canonical form

I'm writing a small computer algebra system that only knows rational numbers and all expressions that you can get from them by using basic arithmetic operations and powers. So the expressions are ...
2
votes
0answers
40 views

Find bounded integers $x, y$ minimizing $| t - x * y |$

How do I find the integers $x$ and $y$ minimizing $| t - x \cdot y |$ with $1 \leq x < N$ and $1 \leq y < M$ ? Background: A clock signal is divided by two hardware prescalers (with a limited ...
2
votes
0answers
57 views

Quadratic Integer Programming

Would anyone mind helping me solve this problem $$ \min\space f(x) = \frac12 x^\mathrm TQx + bx + c \qquad \text{s.t. } \sum_i x_i=\lambda $$ where $x$ is a vector whose entries are positive ...
2
votes
0answers
93 views

Clarification of variable values in Arithmetic Coding algorithm

I have been trying to follow this video to implement my own Arithmetic Coding algorithm in Java. I am having a bit of trouble figuring out what some of the variables in the video should be. For ...
2
votes
0answers
123 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
0answers
20 views

How do you calculate Up and Down Penalties on a Branch and Bound algorithm of a MILP?

My notes really don't explain this clearly at all, so I have no idea what to do. If I have the following MILP: In which I've been told to solve it using: (a) Rule 1 (choose the variable with the ...
1
vote
0answers
50 views

Mixed-Integer Linear Programing : get the maximum constant associated to a non null variable

Does anyone know a way get the maximum constant associated to a non null variable using Mixed-Integer Linear Programing ? I would like to get the variable $a$ in this description : $$ i = 1,\ldots,m ...
1
vote
0answers
31 views

fill up a square with rectanagles

I have a square 46*46, I want to fill this up with three types of rectangles of size 29*20, 21*5, 10*4 such that the free space can be minimized? any rectangles can't be overlapped and they can be ...
1
vote
0answers
16 views

Find relationships between events

I have a set of Events $(E_i)_i$ which have a probability $(P_i)_i$. I am able to write each event as a sum of distinct events that form a partition of the space. My goal is to find all the ...
1
vote
0answers
68 views

Traverse resultant 2d array after integer partition

I have used the solution of integer partitioning using dynamic programming explained in this post and in this article. Following is the resultant matrix when N is equal to 6: $$\begin{bmatrix} 1 ...
1
vote
0answers
39 views

Prove this statement about inequalities

Can someone help to prove this. For $n$ and $\{a_{11},\dots,a_{nn}\}$, if we know that $a_{ij}$ is either $0$ or $1$ or $-1$, and further assume that the following inequality system on $\{b_n|b_n\in ...
1
vote
0answers
46 views

Minimising waste in a cutting problem.

I have three possible board sizes: $8$, $10$ and $12$ feet long. I want to make some number of cuts to these, say, $3, 2,1,1,1,6,5,3,4,2,1$ feet cuts and I want to minimize waste. I've done a quick ...
1
vote
0answers
42 views

Program for Handling Huge Primes

I am trying to run a program with really large primes (around the $10^{20}$th prime), but Mathematica seems to only be able to handle around the first $10^{12}$ primes. Is there any software that can ...
1
vote
0answers
86 views

Help solving this linear (?) programming problem with odd integer constraints.

I would like some help writing the following linear (integer? quadratic?) programming problem in matrix form including the application of the constraints. I am drawing a dashed line around the ...
1
vote
0answers
67 views

How to minimise an objective function which is not a direct function of the decision variable?

I have a problem with partitioning a water network by closing some pipes. I use some graph theory techniques to find some candidate pipes to close; but to select which pipes among them to close (my ...
1
vote
0answers
28 views

Highest (lowest) index of positive time-indexed variable

I have a simple problem involving a variable $x_{it}$ representing the amount of a resource allotted to a task $i$ in time $t$. The quantity of the (renewable) resource is constrained at a value $R$ ...
1
vote
0answers
96 views

Is 0-1 integer programming always NP-hard?

I have the following problem. Maximize $\sum\limits_{m=1}^M\sum\limits_{n=1}^N x_{mn}$ subject to: $\sum\limits_{\substack{m^\prime=1\\ m^\prime \neq m}}^M\sum\limits_{\substack{n^\prime=1\\ ...
1
vote
0answers
76 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book ...
1
vote
0answers
33 views

integer programming with bounded dimension

We know that integer programming with bounded dimension or fixed number of variables can be solved in polynomial time by Lenstra's result(from results of the LLL algorithm). After heavy foraging i ...
1
vote
0answers
19 views

Internals of a MIP Solver

I would like to learn about the internals of a Mixed Integer Programming (MIP) solver. Which concepts shall I read about? Are there a couple of standard books which can be a good start?
1
vote
0answers
244 views

Constraints of a linear programming problem

QUESTION Sandy Arledge is the program scheduling manager for WCBN‐TV. Sandy would like to plan the schedule of television shows for next Wednesday evening. Of the nine possible one‐half hour ...
1
vote
0answers
45 views

How to express coprimality as a constraint in an optimization problem over integers?

I am currently working with an optimization problem that is defined over a a set of $D$-dimensional integer vectors where each component is bounded by $M$. Let us refer to this optimization problem ...
1
vote
0answers
49 views

Regression/compressive sensing with non-linear constrains where the coefficients are assumed to be integer or binary {0,1}

The following regression problem $$ \mathbf{y} = \mathbf{A}\mathbf{x} $$ where $\mathbf{y}$ is a $N\times 1$ column real vector, $\mathbf{A}$ is a $N\times M$ real matrix where each column ...
1
vote
0answers
39 views

How to find best set of customers

I've got a problem with getting optimized solution from this task: We have n customers, which buy articles from m suppliers. There are much more customers and suppliers on the market. We've got sales ...
1
vote
0answers
193 views

Strange but practical Bin packing problem

I am trying to solve the following MILP through LP solve. A link for the original problem is here I am re-iterating the problem as follows: I am trying to write an application that generates drawing ...
1
vote
0answers
75 views

Speeding up solution of a binary integer program

To solve the problem of making a "good" schedule for a tournament between N teams, using memories from my (long gone) student days, I expressed it as a binary integer program. With the current set of ...
1
vote
0answers
39 views

Program to determine the relationship of one variable to several possible variables

Suppose I have a system with several variables a, b, c, d, and x. I am trying to solve for the unknown x. I don't know exactly which of those variables x is dependent on, or exactly how the function ...
1
vote
0answers
105 views

Why these two problems lead to same answers?

Suppose these two problems: Problem 1: $$\min_{X,P} \quad\max_{1\leq l\leq L-1} \quad {|\sum_{1\leq i\leq N_p}^{N_p}x_ie^{\frac{2\pi l}{N}p_i}| \over {\sum_{i=1}^{N_p} x_i^2}} \quad \equiv \quad ...
1
vote
0answers
391 views

How does Microsoft Excel Solver's Simplex algorithm deal with integers?

I was wondering how the Simplex algorithm in Excel's Solver deals with integers. From what I understand, the Simplex algorithm is meant to be used for linear programming/optimizations only. Yet, Excel ...
1
vote
0answers
32 views

If the following LP has an integral solution

I know the constraints matrix A of a linear program "Min cx such that Ax>=b" is totally unimodular. So, the program has integral solutions for integral vector b. If this is also the case for the ...
1
vote
0answers
109 views

Determining if data can be fit by a continuous piecewise integer-valued polynomial

This question concerns the sequence of integers which form the solution to a particular computational problem. See the bottom for the full formulation; basically, for some value n, $G(n)$ is the ...
1
vote
0answers
84 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
0answers
272 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
280 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 ...
1
vote
0answers
173 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: ...
1
vote
0answers
159 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} & ...
0
votes
0answers
12 views

A good enough solution for the 0-1 multiple knapsack problem

Can you please explain, or point to an easy explanation of a good enough solution to the 0-1 multiple knapsack problem? This is a single constraint problem so only one-dimensional weights are to be ...
0
votes
0answers
10 views

Wrong ILP solution with LPSolve (simple example)

I added the following example into LPSolve and found a strange issue. I don't want S1 and S2 to overlap within certain margins. ...
0
votes
0answers
18 views

How is D.Knuth MMIX instruction MXOR useful for finite field multiplication?

Knuths TAOCP, Fascicle 1, exercise 37 (page 26) - http://mmix.cs.hm.edu/doc/fasc1.pdf: Explain how to use MXOR for arithmetic in a field of 256 elements; each element of the field should be ...
0
votes
0answers
7 views

Help on Binary Integer Programming

I am about to do a paper about distributing subjects to students with the constraints on: number of subjects that the student need, number of students whom these subjects will be distributed to, and ...
0
votes
0answers
11 views

Linearization bounds on 0-1 quadratic problems

What are the best linearization methods for approximating the following constrained 0-1 Quadratic problem, where $Q \in \mathbb{R}^{n\times n}$ and $k$ is an integer $1\leq k \leq n$ $$ \max ...
0
votes
0answers
42 views

Solution of a linearly constrained quadratic programming problem

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. ...
0
votes
0answers
25 views

Solution existence on $ax + by = c$

I have to produce an program which resolve the following equation: $ax + by = c$ With the following condition: $a$, $b$ and $c$ are known positive integer. $x$ and $y$ are positive ...
0
votes
0answers
10 views

Favorable probability(part 2)

After condition in Favorable probability . i should make an program in Python. I started in the next way: from random import randint import math MembersInBand = 50 ArrayOfMembers = [] for i in ...