Skip to main content
14 votes

Why do I get a binary solution even when I solve an LP problem with continuous variables?

Totally unimodular (see added tag) constraint matrices have this property. One common example is when the constraint matrix corresponds to a network flow problem, with one variable per arc and one ...
RobPratt's user avatar
  • 32.7k
7 votes

How to avoid similar solutions?

you can order the variables: $x_1 \le x_2 \le x_3$
Laurent Perron's user avatar
4 votes

How to linearize the following logical constraints?

Assume $0 \le x \le U$ for some constant $U$. Introduce binary decision variable $\delta$ and impose $x=y+z$ and indicator constraints: \begin{align} \delta=0 &\implies (0 \le x \le A \land y = x)...
RobPratt's user avatar
  • 32.7k
4 votes
Accepted

How to avoid similar solutions?

You can add a continuous variable $h_i$ for each bucket $i$ to contain its "hash value", then constrain the hash values to be in nondecreasing order ($h_1 \le h_2 \le \dots$). The hash ...
prubin's user avatar
  • 39.5k
3 votes

Restrict the number of non-zero variables to any constant in MILP

Define binary variable $y_i$ for each $i$. Let $\epsilon$ be a small constant close to $0$. You can enforce the desired constraints by adding the following: \begin{align} \epsilon y_i \le x_i &\le ...
Kuifje's user avatar
  • 13.5k
2 votes

Conditional binary programming

Suppose $0 \le b^n_{it} \le M^n_{it}$ for some constant $M^n_{it}$. Introduce binary decision variable $y_{it}$ to indicate whether $b^n_{it} > 0$. Now impose linear constraints \begin{align} y_{...
RobPratt's user avatar
  • 32.7k
1 vote

Multiple Travelling Salesmen - How to make the second slowest salesman matter?

You are dealing with a multi-objective problem. A common approach is to first consider your main goal, in your case that is $T_{max}$. Once you have found an optimal $T_{max}$, you adjust your ...
PeterD's user avatar
  • 1,676
1 vote
Accepted

Column Generation for non/single capacitated routing problems

For a maximization master problem whose variables correspond to matchings, the subproblem is an oracle to find a positive (not negative) reduced cost matching (not a tour) if one exists. Because your ...
RobPratt's user avatar
  • 32.7k
1 vote

Optimizing calls to a separation problem in branch and cut

As far as I understand, you have a branch-and-cut algorithm that separates valid inequalities for integer and fractional solutions. The cuts you separate are valid and improve the quality of the ...
Alberto Santini's user avatar
1 vote

Optimizing calls to a separation problem in branch and cut

Are you solving the separation problem inside a generic callback? If so, CPLEX will solve the problem once per call to the callback (or less, if the callback sometimes chooses not to solve the problem)...
prubin's user avatar
  • 39.5k
1 vote

Minimizing sum(abs(Ax-c)) for binary decision variables - terminology and methods?

I do not know of a name for this problem, and I do not think switching to constraint programming will help. If you are content with a heuristic approach (not requiring a provably optimal solution), ...
prubin's user avatar
  • 39.5k

Only top scored, non community-wiki answers of a minimum length are eligible