Questions on optimization constrained to integer variables.

learn more… | top users | synonyms

13
votes
0answers
305 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
102 views

ax+by+cz<=d, find the maximum value of ax+by+cz.

I am recently calculating that kind of questions as shown in title. And of course, I use a lot of time to find the answer. Therefore I would like to know how I can calculate faster. Q.: ax + by + ...
4
votes
0answers
90 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
165 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
32 views

NP-hardness of solving congruence equations in several variables

You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): $$\beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l ...
3
votes
0answers
157 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
26 views

Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t $$ subject ...
2
votes
0answers
35 views

Approximate algorithms for integer linear programming (for optimal subset selection)

I'm trying to select an optimal subset of some items. I've tried 2 optimal approaches (branch-and-bound and integer programming) but both proved impossible for the size of the problem. I'm wondering ...
2
votes
0answers
27 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
124 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
41 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
58 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
115 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
143 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
25 views

How to interpret this integer program

I'm having problem understanding the min weight st-cut integer programming in this wiki page: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem In the min-cut dual part, it has $$d_{ij}-p_i+p_i ...
1
vote
0answers
46 views

Integer programming, system of linear inequalities.

I am woring on a problem and I got these inequalities. $t_{01}+t_{11}+t_{21}\ge 4$ $t_{02}+t_{12}+t_{22}\ge 4$ $t_{10}+t_{11}+t_{12}\ge 4$ $t_{10}+t_{01}+t_{22}\ge 4$ $t_{10}+t_{02}+t_{21}\ge 4$ ...
1
vote
0answers
25 views

Lenstra's integer programming algorithm: Finding a lattice point “near the center”

Preliminaries: As part of Lenstra's algorithm for integer programming (see here, page 4) we compute a linear transformation $\tau$ and a point $z \in \mathbb{R}^n$ which meet certain conditions (step ...
1
vote
0answers
65 views

Shadow prices in assignment problems (and their relationship to Lagrange multipliers of LP-relaxation)

Lagrange multipliers for linear programs can be interpreted as shadow prices. Shadow prices typically represent marginal/differential changes in the objective from a marginal loosening of a given ...
1
vote
0answers
23 views

Social welfare convergence in large assignment problems with random utilities

Suppose there are $N$ agents each to be assigned one of $N$ objects. The utility an agent gets for a particular object is drawn uniformly, i.i.d., from the set of integers between $0$ and $100$ ...
1
vote
0answers
17 views

Integer programming - multi-set partitioning

I'm trying to solve this question: Let S be a multi-set of n integers, can S be partitioned into two sub-multi-sets $S1$,$S2$, such that: $$ \sum_{x \in S1} x = \sum_{y \in S2} y $$ I'm trying to ...
1
vote
0answers
26 views

How to determine the smallest N such that there are X (or more) prime numbers with exactly N bits?

I understand how I can use the prime number theorem to determine how many primes exist for a given bit length: $\pi(2^n)-\pi(2^{n-1})$. However, my specific problem is that I need to approach this ...
1
vote
0answers
26 views

Understanding ILP formulations of combinatorial optimisation problems

I am having trouble understanding and producing integer linear programming formulations for combinatorial optimisation problems. I can understand basic ones like the knapsack problem: $min \quad ...
1
vote
0answers
24 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)}$ ...
1
vote
0answers
24 views

CPLEX solver on a standard vertex coloring problem

I have a very straightforward ILP model of vertex coloring that I'm trying to solve with CPLEX. With a binary variable $x_{vc}$ for every $(v,c) \in \{ V \times C\}$ there is a constraint $$ \sum_{c ...
1
vote
0answers
28 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 ...
1
vote
0answers
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 ...
1
vote
0answers
22 views

Is there any general algorithm to solve such a 3D cutting problem?

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 ...
1
vote
0answers
188 views

Global and local maxima in a weighted sum of logarithms of linear functionals?

Is is possible to describe, and locate efficiently, the maxima of the function below in the parameters $\mathbf{x}$ $$\sum_{i} p_i \log( N + \sum_j x_j[B_j +(A_j-B_j)\delta_{ij} + min(A_j,B_j) ]) ...
1
vote
0answers
20 views

Linear Integer Optimzation Problem (scheduling problem)

Does any of you know how to get this done?
1
vote
0answers
41 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
64 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
40 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
18 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
81 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
vote
0answers
41 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
71 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
46 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
177 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
111 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
34 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
119 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
115 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
24 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
402 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
51 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
59 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
42 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
226 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
85 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
44 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 ...