Scippy

SCIP

Solving Constraint Integer Programs

Functions | Variables
circlepacking.c File Reference

Detailed Description

Packing circles in a rectangle of minimal size.

Author
Jose Salmeron
Stefan Vigerske

This example shows how to setup quadratic constraints in SCIP when using SCIP as callable library. The example implements a model for the computation of a smallest rectangle that contains a number of given circles in the plane or the computation of the maximal number of circles that can be placed into a given rectangle.

Suppose that n circles with radii \(r_i\) are given. The task is to find coordinates \((x_i, y_i)\) for the circle midpoints and a rectangle of width \(W \geq 0\) and height \(H \geq 0\), such that

  • every circle is placed within the rectangle ( \(r_i \leq x_i \leq W-r_i\), \(r_i \leq y_i \leq H-r_i\)),
  • circles are not overlapping \(\left((x_i-x_j)^2 + (y_i-y_j)^2 \geq (r_i + r_j)^2\right)\), and
  • the area of the rectangle is minimal.

Alternatively, one may fix the size of the rectangle and maximize the number of circles that can be fit into the rectangle without being overlapping.

Definition in file circlepacking.c.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include "scip/scip.h"
#include "scip/scipdefplugins.h"

Go to the source code of this file.

Functions

static void visualizeSolutionMatplotlib (SCIP *scip, SCIP_SOL *sol)
 
static void visualizeSolutionGnuplot (SCIP *scip, SCIP_SOL *sol)
 
static SCIP_RETCODE visualizeSolutionAscii (SCIP *scip, SCIP_SOL *sol)
 
static SCIP_DECL_EVENTINIT (eventInitDispsol)
 
static SCIP_DECL_EVENTEXIT (eventExitDispsol)
 
static SCIP_DECL_EVENTEXEC (eventExecDispsol)
 
static SCIP_RETCODE includeEventHdlrDispsol (SCIP *scip)
 
static SCIP_RETCODE setupProblem (SCIP *scip, SCIP_Real fixwidth, SCIP_Real fixheight)
 
static SCIP_RETCODE runPacking (SCIP_Real fixwidth, SCIP_Real fixheight, SCIP_Bool dognuplot, SCIP_Bool domatplotlib)
 
int main (int argc, char **argv)
 

Variables

int ncircles = 0
 
SCIP_Real * r = NULL
 
int rsize = 0
 
SCIP_VAR ** x
 
SCIP_VAR ** y
 
SCIP_VAR ** b
 
SCIP_VAR * a
 
SCIP_VAR * w
 
SCIP_VAR * h
 
SCIP_Bool minarea
 

Function Documentation

◆ visualizeSolutionMatplotlib()

static void visualizeSolutionMatplotlib ( SCIP *  scip,
SCIP_SOL *  sol 
)
static

plots solution by use of Python/Matplotlib

Parameters
scipSCIP data structure
solsolution to plot

Definition at line 74 of file circlepacking.c.

References minarea, ncircles, NULL, r, SCIPerrorMessage, SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPinfoMessage(), and SCIPround().

Referenced by runPacking().

◆ visualizeSolutionGnuplot()

static void visualizeSolutionGnuplot ( SCIP *  scip,
SCIP_SOL *  sol 
)
static

plots solution by use of gnuplot

Parameters
scipSCIP data structure
solsolution to plot

Definition at line 136 of file circlepacking.c.

References MAX, minarea, ncircles, NULL, r, SCIP_Real, SCIPerrorMessage, SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPinfoMessage(), and SCIPround().

Referenced by runPacking().

◆ visualizeSolutionAscii()

static SCIP_RETCODE visualizeSolutionAscii ( SCIP *  scip,
SCIP_SOL *  sol 
)
static

plots solution by use of ascii graphics

Parameters
scipSCIP data structure
solsolution to plot

Definition at line 194 of file circlepacking.c.

References minarea, ncircles, NULL, phi(), r, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPceil(), SCIPfreeBufferArray, SCIPgetIntParam(), SCIPgetSolOrigObj(), SCIPgetSolVal(), SCIPinfoMessage(), SCIPround(), and SCIPsnprintf().

Referenced by SCIP_DECL_EVENTEXEC().

◆ SCIP_DECL_EVENTINIT()

static SCIP_DECL_EVENTINIT ( eventInitDispsol  )
static

initialization method of event handler (called after problem was transformed)

Definition at line 286 of file circlepacking.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, and SCIPcatchEvent().

◆ SCIP_DECL_EVENTEXIT()

static SCIP_DECL_EVENTEXIT ( eventExitDispsol  )
static

deinitialization method of event handler (called before transformed problem is freed)

Definition at line 295 of file circlepacking.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, and SCIPdropEvent().

◆ SCIP_DECL_EVENTEXEC()

static SCIP_DECL_EVENTEXEC ( eventExecDispsol  )
static

execution method of event handler

Definition at line 304 of file circlepacking.c.

References NULL, SCIP_CALL, SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_OKAY, SCIPeventGetSol(), SCIPeventGetType(), and visualizeSolutionAscii().

◆ includeEventHdlrDispsol()

static SCIP_RETCODE includeEventHdlrDispsol ( SCIP *  scip)
static

creates event handler for dispsol event

Parameters
scipSCIP data structure

Definition at line 320 of file circlepacking.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeEventhdlrBasic(), SCIPsetEventhdlrExit(), and SCIPsetEventhdlrInit().

Referenced by runPacking().

◆ setupProblem()

static SCIP_RETCODE setupProblem ( SCIP *  scip,
SCIP_Real  fixwidth,
SCIP_Real  fixheight 
)
static

create problem in given SCIP and add all variables and constraints to model the circle packing problem

Parameters
scipSCIP data structure
fixwidtha given fixed width for the rectangle, or SCIP_INVALID if not fixed
fixheighta given fixed height for the rectangle, or SCIP_INVALID if not fixed

Definition at line 339 of file circlepacking.c.

References FALSE, MIN, minarea, ncircles, NULL, r, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_MAXSTRLEN, SCIP_OBJSENSE_MAXIMIZE, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIP_VARTYPE_CONTINUOUS, SCIPaddCoefLinear(), SCIPaddCons(), SCIPaddVar(), SCIPallocMemoryArray, SCIPcreateConsBasicLinear(), SCIPcreateConsQuadraticNonlinear(), SCIPcreateProbBasic(), SCIPcreateVarBasic(), SCIPfixVar(), SCIPinfinity(), SCIPisLT(), SCIPreleaseCons(), SCIPsetObjsense(), SCIPsnprintf(), SQR, and TRUE.

Referenced by runPacking().

◆ runPacking()

static SCIP_RETCODE runPacking ( SCIP_Real  fixwidth,
SCIP_Real  fixheight,
SCIP_Bool  dognuplot,
SCIP_Bool  domatplotlib 
)
static

run circle packing example

Sets up SCIP and the SCIP problem, solves the problem, and shows the solution.

Parameters
fixwidtha given fixed width for the rectangle, or SCIP_INVALID if not fixed
fixheighta given fixed height for the rectangle, or SCIP_INVALID if not fixed
dognuplotwhether to draw best solution with gnuplot
domatplotlibwhether to draw best solution with python/matplotlib

Definition at line 554 of file circlepacking.c.

References FALSE, includeEventHdlrDispsol(), minarea, ncircles, NULL, r, SCIP_CALL, SCIP_OKAY, SCIPcreate(), SCIPfree(), SCIPfreeMemoryArray, SCIPgetBestSol(), SCIPgetNSols(), SCIPincludeDefaultPlugins(), SCIPinfoMessage(), SCIPprintOrigProblem(), SCIPprintSol(), SCIPreleaseVar(), SCIPsetRealParam(), SCIPsolve(), setupProblem(), visualizeSolutionGnuplot(), and visualizeSolutionMatplotlib().

Referenced by main().

◆ main()

int main ( int  argc,
char **  argv 
)

main method starting SCIP

Parameters
argcnumber of arguments from the shell
argvarray of shell arguments

Definition at line 629 of file circlepacking.c.

References BMSallocMemoryArray, BMSreallocMemoryArray, FALSE, ncircles, r, rsize, runPacking(), SCIP_ALLOC_ABORT, SCIP_Bool, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIPprintError(), and TRUE.

Variable Documentation

◆ ncircles

int ncircles = 0

Number of possible circles

Definition at line 56 of file circlepacking.c.

Referenced by getNCircles(), main(), runPacking(), setupProblem(), solvePricingMINLP(), visualizeSolutionAscii(), visualizeSolutionGnuplot(), and visualizeSolutionMatplotlib().

◆ r

SCIP_Real* r = NULL

Radii

Definition at line 59 of file circlepacking.c.

Referenced by addFlowrowToCommodity(), addFracCounter(), addLocalRows(), addOrbitopesDynamic(), addRangeInfo(), addRelaxation(), allRowsInLP(), applyCompression(), atomic_userexpr::atomic_userexpr(), branchruledataEnsureArraySize(), checkCons(), cleanupNetwork(), computeAndConstraintInfos(), computeVarRatio(), consdataCreate(), consdataFreeRows(), constructCompression(), createCGMIPprimalsols(), createRelaxation(), createSubscip(), cutsSubstituteMIR(), deleteCommodity(), detectParallelCols(), displayReaders(), enforceExprNlhdlr(), ensureRngrowmapMem(), extractCapacities(), extractCapacityRows(), extractFlow(), extractFlowRows(), extractNodes(), fillRelationTables(), findUncapacitatedArcs(), forkAddLP(), generateAverageRay(), generateClusterCuts(), generateDisjCutSOS1(), getDualBranchscore(), getFlowrowFit(), getIncidentNodes(), getJobs(), getNActiveConsScore(), getNextFlowrow(), getNodeSimilarityScore(), getResourcesCapacities(), getResourcesNames(), getSimplexCoefficients(), getVarRank(), heurdataEnsureArraySize(), identifySourcesTargets(), improvePoint(), invertCommodity(), lpCleanupRows(), lpDelRowset(), lpFlushAddRows(), lpLexDualSimplex(), lpRemoveObsoleteRows(), main(), markRelaxsUnsolved(), markRowsXj(), mcfnetworkFill(), parseDetails(), posintpower(), ObjPricerVRP::pricing(), profilesFindEarliestFeasibleStart(), profilesFindLatestFeasibleStart(), propagateStaticOrbitope(), propVariables(), pseudoforkAddLP(), relaxVar(), runPacking(), SCIP_DECL_COMPREXIT(), SCIP_DECL_CONSGETNVARS(), SCIP_DECL_CONSGETVARS(), SCIP_DECL_HEUREXEC(), SCIP_DECL_NLHDLRENFO(), SCIP_DECL_PRESOLEXEC(), SCIP_DECL_READERREAD(), SCIPapplyLockFixings(), SCIPcolPrint(), SCIPconflictAnalyzeLP(), SCIPcreateSchedulingProblem(), SCIPdummyDebugMethodForSun(), SCIPexprintHessianSparsity(), SCIPfreeRepresentation(), SCIPgetDualProof(), SCIPgetFarkasProof(), SCIPgetRandomSubset(), SCIPgetReadingTime(), SCIPinitRepresentation(), SCIPlpEndDive(), SCIPlpGetDualDegeneracy(), SCIPlpGetDualfarkas(), SCIPlpGetSol(), SCIPlpGetUnboundedSol(), SCIPlpiAddRows(), SCIPlpiDelRows(), SCIPlpiDelRowset(), SCIPlpiGetBase(), SCIPlpiGetBasisInd(), SCIPlpiGetBInvACol(), SCIPlpiGetBInvARow(), SCIPlpiGetBInvCol(), SCIPlpiGetBInvRow(), SCIPlpiGetRows(), SCIPlpiGetSol(), SCIPlpiLoadColLP(), SCIPlpiSetBase(), SCIPlpRemoveRedundantRows(), SCIPlpShrinkRows(), SCIPlpStartDive(), SCIPlpSumRows(), SCIPlpUpdateAges(), SCIPmatrixGetParallelCols(), SCIPrandomGetSubset(), SCIPreoptApplyCompression(), SCIPreoptGetNSols(), SCIPreoptMergeVarHistory(), SCIPresetRepresentation(), SCIPrunBoundHeuristic(), SCIPsolAdjustImplicitSolVals(), SCIPsolveProbingRelax(), separateCons(), separateConsBinaryRepresentation(), separateCoverCutsCons(), separateCuts(), separateRltCuts(), setupProblem(), solveBilinearLP(), solveNodeRelax(), solveRowEchelonGF2(), storeCuts(), storeSuitableRows(), strengthenOrbitopeConstraint(), subrootConstructLP(), updateActivities(), updateLoopStatus(), updateSymInfoConflictGraphSST(), varProcessBoundChanges(), visualizeSolutionAscii(), visualizeSolutionGnuplot(), visualizeSolutionMatplotlib(), writeOpbRelevantAnds(), xmlFindNode(), and xmlFindNodeMaxdepth().

◆ rsize

int rsize = 0

Definition at line 60 of file circlepacking.c.

Referenced by main().

◆ x

SCIP_VAR** x

x coordinates

Definition at line 63 of file circlepacking.c.

Referenced by addCut(), addProductVars(), atomic_userexpr::atomic_userexpr(), bilinearTermsInsertAll(), bilinearTermsInsertEntry(), checkSystemGF2(), cleanCycle(), computeConvexEnvelopeFacet(), computeCut(), detectMinors(), drawScaledImage(), ecaggrAddBilinTerm(), ecaggrAddQuadvar(), estimateConvexSecant(), estimateUnivariateQuotient(), extractProducts(), F77_FUNC(), getBilinearBinaryTerms(), getBinaryProductExpr(), getBinaryProductExprDo(), getEigenValues(), getX(), hessLagSparsitySetNzFlagForExpr(), isPackingCons(), lpiGetBInvVec(), nlrowaggrAddRemBilinTerm(), nlrowaggrCreate(), printRow(), provedBound(), rbRotate(), read_problem(), reversePropBinarySearch(), roundFixingValue(), runBrachistochrone(), SCIP_DECL_CONSEXIT(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_NLHDLRESTIMATE(), SCIP_DECL_NLHDLRSOLLINEARIZE(), SCIP_DECL_READERREAD(), SCIP_NlpiProblem::SCIP_NlpiProblem(), SCIPaddIneqBilinear(), SCIPcalcGreComDiv(), SCIPcalcRootNewton(), SCIPerf(), SCIPgetBilinTermIdxNonlinear(), SCIPgetNlpiOracleIpopt(), SCIPintervalGetRoundingMode(), SCIPintervalQuadBivar(), SCIPintervalQuadUpperBound(), SCIPintervalSquare(), SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiChgBounds(), SCIPlpiChgObj(), SCIPlpiChgSides(), SCIPlpiClearState(), SCIPlpiGetBasisInd(), SCIPlpiGetBInvACol(), SCIPlpiGetBInvARow(), SCIPlpiGetBInvCol(), SCIPlpiGetBInvRow(), SCIPlpiGetDualfarkas(), SCIPlpiGetPrimalRay(), SCIPlpiGetSol(), SCIPlpiLoadColLP(), SCIPlpiReadLP(), SCIPlpiScaleCol(), SCIPlpiScaleRow(), SCIPlpiWriteLP(), SCIPnegateReal(), SCIPpatternAddElement(), SCIPpatternSetElementPos(), SCIPrbtreeDelete_call(), SCIPrealHashCode(), sepadataAddMinor(), separatePoint(), setupProblem(), solvePricingMINLP(), solveRowEchelonGF2(), spxSolve(), and updateBestCandidate().

◆ y

SCIP_VAR** y

y coordinates

Definition at line 64 of file circlepacking.c.

Referenced by addCut(), addProductVars(), bilinearTermsInsertAll(), bilinearTermsInsertEntry(), computeCut(), detectMinors(), drawScaledImage(), ecaggrAddBilinTerm(), errorf(), extractProducts(), getBilinearBinaryTerms(), getBinaryProductExpr(), getBinaryProductExprDo(), getEigenValues(), isPackingCons(), lpiGetBInvVec(), nlrowaggrAddRemBilinTerm(), nlrowaggrCreate(), printRow(), provedBound(), rbInsertFixup(), rbRotate(), read_problem(), runBrachistochrone(), SCIP_DECL_EVENTEXEC(), SCIP_DECL_NLHDLRESTIMATE(), SCIP_DECL_READERREAD(), SCIPaddIneqBilinear(), SCIPcalcGreComDiv(), SCIPerf(), SCIPgetBilinTermIdxNonlinear(), SCIPintervalQuadBivar(), SCIPintervalSquare(), SCIPlpiGetBInvRow(), SCIPpatternAddElement(), SCIPpatternSetElementPos(), SCIPrbtreeDelete_call(), SCIPrbtreePredecessor_call(), SCIPrbtreeSuccessor_call(), SCIPregressionAddObservation(), SCIPregressionRemoveObservation(), sepadataAddMinor(), separatePoint(), setupProblem(), solvePricingMINLP(), and updateBestCandidate().

◆ b

SCIP_VAR** b

whether circle is placed into rectangle

Definition at line 65 of file circlepacking.c.

Referenced by alnsFixMoreVariables(), analyseOnoffBounds(), cancelCol(), cancelRow(), checkBlocking(), checkCons(), checkSystemGF2(), collectBinaryVars(), computeModularity(), computeMonoidalStrengthCoef(), computePosCircleCircle(), computePosRingCircle(), computeRestrictionToLine(), computeRestrictionToRay(), computeRoot(), computeRowEchelonGF2(), consdataCreateBinvars(), consdataLinearize(), createAndSplitProblem(), createCapacityRestriction(), createCoverCutsTimepoint(), createRows(), decompHorizonGetFirstPosBestPotential(), decompHorizonInitialize(), decompHorizonMarkInterval(), detectExpr(), determineVariableFixingsDecomp(), encodeColPair(), encodeRowPair(), estimateUnivariate(), findMonoidalQuadRoot(), initCurrent(), isNeighbor(), LNSFixMoreVariables(), lockRounding(), lpiStrongbranch(), optimize(), processRealBoundChg(), projectVbd(), provedBound(), removeFixedBinvars(), reoptimize(), reuseSolution(), roundPartition(), scalePenalties(), SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_CONSLOCK(), SCIP_DECL_CONSRESPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_NLHDLRINTEVAL(), SCIP_DECL_NLHDLRREVERSEPROP(), SCIPclassifyConstraintTypesLinear(), SCIPintervalQuadUpperBound(), SCIPintervalSolveBivariateQuadExpressionAllScalar(), SCIPintervalSolveUnivariateQuadExpressionPositiveAllScalar(), SCIPlpiGetBInvCol(), SCIPlpiGetBInvRow(), SCIPrealToRational(), SCIPsetSortProps(), SCIPvisualizeConsCumulative(), selectCandidateUsingSVTS(), solveRowEchelonGF2(), solveSingleRowLP(), SORTTPL_NAME(), strengthenVarbounds(), tightenedLinkvar(), tightenWeights(), tryAggregateIntVars(), updateLambda(), and xmlFreeAttr().

◆ a

SCIP_VAR* a

area of rectangle

Definition at line 66 of file circlepacking.c.

Referenced by addRowMark(), applyOptcumulative(), buildVertexPolyhedralSeparationLP(), cancelCol(), cancelRow(), checkBlocking(), cleanCycle(), cleanupNetwork(), computeAndConstraintInfos(), computeMonoidalStrengthCoef(), computeObjWeightSize(), computePosCircleCircle(), computePosRingCircle(), computeRestrictionToLine(), computeRestrictionToRay(), computeRevPropIntervalSin(), computeRoot(), computeVarRatio(), createEdgesFromRow(), createInitialColumns(), createLP(), detectExpr(), encodeColPair(), encodeRowPair(), estimateBivariateQuotient(), F77_FUNC(), findMonoidalQuadRoot(), generateClusterCuts(), identifyComponent(), identifySourcesTargets(), integerpow(), isNeighbor(), markRowsXj(), mcfnetworkExtract(), mcfnetworkFill(), mcfnetworkFree(), nodepairqueueCreate(), nodepartitionIsConnected(), performAggregations(), printNLRow(), propagateBoundsQuadExpr(), provedBound(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_HEURFREE(), SCIPrealToRational(), SCIPwriteCcg(), selectCandidateUsingSVTS(), SORTTPL_NAME(), tryAggregateIntVars(), writeOpbObjective(), writeOpbRelevantAnds(), xmlAddAttr(), xmlFreeAttr(), xmlGetAttrval(), xmlNewAttr(), and xmlShowNode().

◆ w

SCIP_VAR* w

width of rectangle

Definition at line 67 of file circlepacking.c.

Referenced by branchBalancedCardinality(), cliqueCleanup(), collectBinaryCliqueData(), collectNonBinaryImplicationData(), collectNonBinaryVBoundData(), consdataCreateRedundant(), correctConshdlrdata(), createEdgesFromRow(), deleteRedundantVars(), detectOrbitopalSymmetries(), detectRedundantVars(), dualWeightsTightening(), enforceConssSOS1(), enforceSOS2(), extensionOperatorSOS1(), extractProducts(), getBinaryProductExprDo(), rbDeleteFixup(), removeConstraintsDueToNegCliques(), sampleWeighted(), SCIP_DECL_BANDITRESET(), SCIP_DECL_HEUREXEC(), SCIPapplyLockFixings(), SCIPcliquetableAdd(), SCIPshrinkDisjunctiveVarSet(), SCIPwriteCcg(), separateSolution(), sequentialUpAndDownLifting(), sequentialUpAndDownLiftingGUB(), solvePricingMINLP(), sortAndMergeClique(), SYMcheckGraphsAreIdentical(), tarjan(), tightenVarsBoundsSOS1(), tightenWeights(), updateConsanddataUses(), updateImplicationGraphSOS1(), and writeOpbObjective().

◆ h

SCIP_VAR* h

height of rectangle

Definition at line 68 of file circlepacking.c.

Referenced by AMPLProblemHandler::BeginSum(), calcNonZeros(), checkFeasSubtree(), checkParameters(), computePosCircleCircle(), computePosRingCircle(), computeRowEchelonGF2(), conflictAddConflictCons(), createMipCpFormulation(), createMipFormulation(), createPresoldata(), DECL_CURVCHECK(), detectNlhdlr(), enforceConstraints(), evaluateLiftingFunctionKnapsack(), findAndStoreDivesets(), hessLagAddExpr(), includeDivingHeurs(), multihashlistRetrieve(), multihashlistRetrieveNext(), SCIPdialoghdlrAddHistory(), SCIPfindNlhdlrNonlinear(), SCIPinitConssLP(), SCIPparamsetSetEmphasis(), SCIPpresolve(), SCIPprimalHeuristics(), SCIPprobFree(), SCIPprobTransform(), SCIPreadProb(), SCIPsolCheck(), SCIPsolCheckOrig(), SCIPtransformProb(), SORTTPL_NAME(), and superadditiveUpLifting().

◆ minarea

SCIP_Bool minarea

whether we minimize the area (TRUE) or maximize the number of circles in the rectangle (FALSE)

Definition at line 69 of file circlepacking.c.

Referenced by runPacking(), setupProblem(), visualizeSolutionAscii(), visualizeSolutionGnuplot(), and visualizeSolutionMatplotlib().